队列(Quene)的特征就是“先进先出”，队列把所有操作限制在"只能在线性结构的两端"进行，更具体一点：添加元素必须在线性表尾部进行，而删除元素只能在线性表头部进行。
先抽象接口IQuene<T>
下面是基于数组实现的示意图：
实现思路：用一个数组存放所有元素，同时设置二个关键变量front与rear用于记录队列“头”与“尾”的元素下标，当有元素入列时rear加1，当有元素出队时front+1，而rear-front即为队列实际元素的总数.
但有一种“队列伪满”的特殊情况要注意，如下图：
这张图上面的部分：假设经过入队、出队一番折腾后，rear已经指向数组的下标最大值，而front指向在中间(即front之间的元素已经出队不用考虑了，相当于front下标前面的内存区域空闲)，如果这时再有一个元素入列，rear+1就超出数组下标的最大值了，但是从图上一眼就能看出，实际上front前面还空着一堆位置可以重复利用，队列并非真正的“满”--这种情况称为伪满，为了解决这个问题，我们可以把数组想象为首尾相接的循环结构，即图中下面部分，这时候可以让rear重新指向到0，以便重复利用空闲的位置。
所以：入列时rear++的操作，应该稍做修正，当rear到数组下标最大值时，让它置0，以便能循环利用 (见后面的代码)
另外还有一个问题：最开始时front与rear都为-1，即front==rear时表示队列为空，改成循环以后，有可能会出现rear在循环过程中碰到front的情况，即真正意义的上"满"状态，这时rear也同样等于front，这样就无法单纯的用rear==front来判断是满，还是空？这时可以浪费一个元素的位置，认为当rear+1==front时，队列就已经满了，虽然牺牲了一个元素的空间，但却换来了逻辑的正确性，还是值得的。
完整实现如下：
测试代码片段：
当然，队列也可以用链表来实现，相对要容易很多。
先定义链表中的节点Node.cs
为了方便，定义了很多构造函数的重载版本，当然这些只是浮云，重点是理解结构：data用来保存数据，next指出下一个节点是谁
链式队列的完整实现LinkQueue.cs
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 | using System; using System.Text; namespace 栈与队列 { public class LinkQueue:IQueue { private Node front; //队列头 private Node rear; //队列尾 private int num; //队列元素个数 /// /// 构造器 /// public LinkQueue() { //初始时front,rear置为null，num置0 front = rear = null ; num = 0; } public int Count() { return this .num; } public void Clear() { front = rear = null ; num = 0; } public bool IsEmpty() { return (front == rear && num == 0); } //入队 public void Enqueue(T item) { Node q = new Node(item); if (rear == null ) //第一个元素入列时 { front = rear = q; } else { //把新元素挂到链尾 rear.Next = q; //修正rear指向为最后一个元素 rear = q; } //元素总数+1 num++; } //出队 public T Dequeue() { if (IsEmpty()) { Console.WriteLine( "Queue is empty!" ); return default (T); } //取链首元素 Node p = front; //链头指向后移一位 front = front.Next; //如果此时链表为空，则同步修正rear if (front == null ) { rear = null ; } num--; //个数-1 return p.Data; } public T Peek() { if (IsEmpty()) { Console.WriteLine( "Queue is empty!" ); return default (T); } return front.Data; } public override string ToString() { if (IsEmpty()) { Console.WriteLine( "Queue is empty!" ); } StringBuilder sb = new StringBuilder(); Node node = front; sb.Append(node.Data.ToString()); while (node.Next!= null ) { sb.Append( "," + node.Next.Data.ToString()); node = node.Next; } return sb.ToString().Trim( ',' ); } } } |