数据结构-循环顺序队列&链队列
队列接口实现：
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace _003_队列 { interface IQueue<T> { int Count { get; } int GetLength(); bool IsEmpty(); void Clear(); void Enqueue(T item); T Dequeue(); T Peek(); } }
顺序循环队列实现：
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace _003_队列 { /// <summary> /// 顺序队列 /// </summary> /// <typeparam name="T"></typeparam> class SeqQueue<T> : IQueue<T> { private T[] data; private int count;//当前元素数量 private int front;//队首 (队首元素索引-1) private int rear;//队尾 （队尾元素索引） public SeqQueue(int size) { data = new T[size]; count = 0; front = -1; rear = -1; } public SeqQueue() : this(10) { } public int Count { get { return count; } } public void Clear() { count = 0; front = rear = -1; } public int GetLength() { return count; } public bool IsEmpty() { return count == 0; } /// <summary> /// 出队,并删除数据 /// </summary> /// <returns></returns> public T Dequeue() { if (!IsEmpty()) { T temp = data[front + 1]; front++; count--; return temp; } else { Console.WriteLine("队列为空"); return default(T); } } /// <summary> /// 入队 /// </summary> /// <param name="item"></param> public void Enqueue(T item) { if (count == data.Length) { Console.WriteLine("队列已满，不可以再添加新的数据"); } else { if (rear == data.Length - 1) //判断是否在尾部，是就把元素放在0位置 { data[0] = item; rear = 0; } else//不是就继续添加 { data[rear + 1] = item; rear++; } count++; } } //取得队首数据 public T Peek() { if (IsEmpty()) { return default(T); } else { return data[front + 1]; } } } }
链结点：
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace _003_队列 { class Node<T> { private T data; private Node<T> next; public Node(T data) { this.data = data; } public T Data { get { return data; } set { data = value; } } public Node<T> Next { get { return next; } set { next = value; } } } }
链队列实现：
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace _003_队列 { /// <summary> /// 链队列 /// </summary> /// <typeparam name="T"></typeparam> class LinkQueue<T> : IQueue<T> { private Node<T> front; private Node<T> rear; private int count; //元素个数 public LinkQueue() { front = null; rear = null; count = 0; } public int Count { get { return count; } } public int GetLength() { return count; } public bool IsEmpty() { return count == 0; } public void Clear() { count = 0; front = null; rear = null; } /// <summary> /// 出队 /// </summary> /// <returns></returns> public T Dequeue() { if (IsEmpty()) { Console.WriteLine("队列为空,无法出队"); return default(T); } else if (count == 1) //等于1 说明 头和尾一样 { T temp = front.Data; front = rear = null; count = 0; return temp; } else //直接删除头 头变成下一个结点 { T temp = front.Data; front = front.Next; count--; return temp; } } /// <summary> /// 入队 /// </summary> /// <param name="item"></param> public void Enqueue(T item) { Node<T> newNode = new Node<T>(item); if (IsEmpty()) { front =rear = newNode; } else { rear.Next = newNode; rear = newNode; } count++; } public T Peek() { if (front!=null) { return front.Data; } else { return default(T); } } } }
栈和队列的应用
/// <summary> /// 使用栈和队列 判断是否为回文 /// </summary> /// <returns></returns> public static bool IsPalindrome(string temp) { Stack<char> stack = new Stack<char>();//先进后出 LinkQueue<char> queue = new LinkQueue<char>();//先进先出 string str = temp; //进栈 进队 for (int i = 0; i < str.Length; i++) { stack.Push(str[i]); queue.Enqueue(str[i]); } //判断前后是否一样 bool flag = false; for (int i = 0; i < str.Length/2; i++) { if (queue.Dequeue() == stack.Pop()) { flag = true; } else { flag = false; } } return flag; }
/// <summary> /// 变大写 /// </summary> /// <param name="s"></param> public static void ToUpper(string s) { Queue<char> que = new Queue<char>(); char w; for (int i = 0; i < s.Length; i++) { if(s[i] > 96 && s[i] < 123) { w = Convert.ToChar(s[i] - 32); } else { w = s[i]; } que.Enqueue(w); } for (int i = 0; i < s.Length; i++) { Console.Write(que.Dequeue()); } } /// <summary> /// 变小写 /// </summary> /// <param name="s"></param> public static void ToLower(string s) { Queue<char> que = new Queue<char>(); char w; for (int i = 0; i < s.Length; i++) { if (s[i] > 64 && s[i] < 91) { w = Convert.ToChar(s[i] + 32); } else { w = s[i]; } que.Enqueue(w); } for (int i = 0; i < s.Length; i++) { Console.Write(que.Dequeue()); } }