一、队列
一种先进先出的数据结构
二、API
public class Queue<T> : IEnumerable
public Queue() 构造函数
public int Size() 队列大小
public Boolean IsEmpty() 队列判空
public void EnQueue(T item) 入队
public T DeQueue() 出队
三、实现
3.1 数组实现
using System; using System.Collections; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace AlgorithmPartI { public class ArrayQueue<T> : IEnumerable { private T[] items; private int N; private int first; private int last; public ArrayQueue() { this.items = new T[2]; this.N = 0; this.first = 0; this.last = -1; } public void Resize(int capacity) { if (capacity <= N) throw new ArgumentException(); T[] temp = new T[capacity]; for (int i = 0; i < N; i++) { temp[i] = items[(i + first) % items.Length]; } items = temp; first = 0; last = N-1; } public int Size { get { return N; } } public Boolean IsEmpty() { return N == 0; } public void EnQueue(T item) { last = ++last % items.Length; items[last] = item; N++; if (N == items.Length) Resize(items.Length * 2); } public T DeQueue() { if (IsEmpty()) throw new InvalidOperationException(); T item = items[first++]; first = first % items.Length; N--; if (N == items.Length/4) Resize(items.Length / 2); return item; } public T Peek() { if (IsEmpty()) throw new InvalidOperationException(); return items[first]; } public IEnumerator GetEnumerator() { for (int i = 0; i < N; i++) { yield return items[(i + first) % items.Length]; } } public override String ToString() { StringBuilder builder = new StringBuilder(); foreach (var q in this) { builder.AppendFormat("{0} ", q); } return builder.ToString(); } public static void main() { #region 队列测试 ArrayQueue<int> queue = new ArrayQueue<int>(); queue.EnQueue(1); queue.EnQueue(2); Console.WriteLine(queue.DeQueue()); queue.EnQueue(3); Console.WriteLine(queue.DeQueue()); Console.WriteLine(queue.DeQueue()); queue.EnQueue(4); queue.EnQueue(5); Console.WriteLine(queue.DeQueue()); queue.EnQueue(6); Console.WriteLine(queue.DeQueue()); Console.WriteLine(queue.DeQueue()); #endregion Console.ReadKey(); } } }
3.2 链表实现
using System; using System.Collections; using System.Collections.Generic; using System.Diagnostics; using System.Linq; using System.Text; using System.Threading.Tasks; namespace AlgorithmPartI { public class LinkNodeQueue<T> : IEnumerable { private int N; private Node first; private Node last; public LinkNodeQueue() { this.N = 0; this.first = this.last = null; } private class Node { public T item; public Node next; } public int Size { get { return N; } } public Boolean IsEmpty() { return N == 0; } private Boolean IsCorrect() { if (N == 0) { if (first != null || first != last) return false; } else if (N == 1) { if (first == null || first != last || first.next != null) return false; } else { if (first == null || first.next == null || last.next != null) return false; } return true; } public void EnQueue(T item) { Node oldLast = last; last = new Node(); last.item = item; last.next = null; if (IsEmpty()) first = last; else oldLast.next = last; N++; Debug.Assert(IsCorrect()); } public T DeQueue() { if (IsEmpty()) throw new InvalidOperationException(); T item = first.item; Node oldFirst = first; first = first.next; oldFirst = null; N--; if (IsEmpty()) last = null; Debug.Assert(IsCorrect()); return item; } public T Peek() { if (IsEmpty()) throw new InvalidOperationException(); return first.item; } public IEnumerator GetEnumerator() { throw new NotImplementedException(); } static void main() { #region 队列测试 LinkNodeQueue<int> queue = new LinkNodeQueue<int>(); queue.EnQueue(1); queue.EnQueue(2); Console.WriteLine(queue.DeQueue()); queue.EnQueue(3); Console.WriteLine(queue.DeQueue()); Console.WriteLine(queue.DeQueue()); queue.EnQueue(4); queue.EnQueue(5); Console.WriteLine(queue.DeQueue()); queue.EnQueue(6); Console.WriteLine(queue.DeQueue()); Console.WriteLine(queue.DeQueue()); #endregion } } }