【转】数据结构C#版笔记--队列(Quene)
转自：http://www.cnblogs.com/yjmyzz/archive/2010/11/04/1865733.html
队列(Quene)的特征就是“先进先出”，队列把所有操作限制在"只能在线性结构的两端"进行，更具体一点：添加元素必须在线性表尾部进行，而删除元素只能在线性表头部进行。
先抽象接口IQuene
下面是基于数组实现的示意图：
实现思路：用一个数组存放所有元素，同时设置二个关键变量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时，队列就已经满了，虽然牺牲了一个元素的空间，但却换来了逻辑的正确性，还是值得的。
完整实现如下：
| 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 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 | using System; using System.Text; namespace 栈与队列 { /// /// 循环顺序队列 /// /// public class CSeqQueue { private int maxsize; private T[] data; private int front; private int rear; public CSeqQueue( int size) { data = new T[size]; maxsize = size; front = rear = -1; } public int Count() { if (rear > front) { return rear - front; } else { return (rear - front + maxsize) % maxsize; } } public void Clear() { front = rear = -1; } public bool IsEmpty() { return front == rear; } public bool IsFull() { if (front != -1) //如果已经有元素出队过 { return (rear + 1) % maxsize == front; //为了区分与IsEmpty的区别，有元素出队过以后，就只有浪费一个位置来保持逻辑正确性. } else { return rear == maxsize - 1; } } public void Enqueue(T item) { if (IsFull()) { Console.WriteLine( "Queue is full" ); return ; } if (rear == maxsize - 1) //如果rear到头了，则循环重来（即解决伪满问题） { rear = 0; } else { rear++; } data[rear] = item; } public T Dequeue() { if (IsEmpty()) { Console.WriteLine( "Queue is empty" ); return default (T); } if (front == maxsize - 1) //如果front到头了，则重新置0 { front = 0; } else { front++; } return data[front]; } public T Peek() { if (IsEmpty()) { Console.WriteLine( "Queue is empty!" ); return default (T); } return data[(front + 1) % maxsize]; } public override string ToString() { if (IsEmpty()) { return "queue is empty." ; } StringBuilder sb = new StringBuilder(); if (rear > front) { for ( int i = front + 1; i <= rear; i++) { sb.Append( this .data[i].ToString() + "," ); } } else { for ( int i = front + 1; i < maxsize; i++) { sb.Append( this .data[i].ToString() + "," ); } for ( int i = 0; i <= rear; i++) { sb.Append( this .data[i].ToString() + "," ); } } return "front = " + this .front + " \t rear = " + this .rear + "\t count = " + this .Count() + "\t data = " + sb.ToString().Trim( ',' ); } } } |
测试代码片段：
| 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 | CSeqQueue< int > queue = new CSeqQueue< int >(5); queue.Enqueue(1); queue.Enqueue(2); queue.Enqueue(3); queue.Enqueue(4); Console.WriteLine(queue); //front = -1 rear = 3 count = 4 data = 1,2,3,4 queue.Dequeue(); Console.WriteLine(queue); //front = 0 rear = 3 count = 3 data = 2,3,4 queue.Dequeue(); Console.WriteLine(queue); //front = 1 rear = 3 count = 2 data = 3,4 queue.Enqueue(5); Console.WriteLine(queue); //front = 1 rear = 4 count = 3 data = 3,4,5 queue.Enqueue(6); Console.WriteLine(queue); //front = 1 rear = 0 count = 4 data = 3,4,5,6 queue.Enqueue(7); //Queue is full Console.WriteLine(queue); //front = 1 rear = 0 count = 4 data = 3,4,5,6 queue.Dequeue(); queue.Enqueue(7); Console.WriteLine(queue); //front = 2 rear = 1 count = 4 data = 4,5,6,7 queue.Clear(); Console.WriteLine(queue); //queue is empty. queue.Enqueue(1); queue.Enqueue(2); queue.Enqueue(3); queue.Enqueue(4); Console.WriteLine(queue); //front = -1 rear = 3 count = 4 data = 1,2,3,4 queue.Enqueue(5); Console.WriteLine(queue); //front = -1 rear = 4 count = 5 data = 1,2,3,4,5 queue.Enqueue(6); //Queue is full Console.WriteLine(queue); //front = -1 rear = 4 count = 5 data = 1,2,3,4,5 queue.Dequeue(); queue.Dequeue(); queue.Dequeue(); queue.Dequeue(); Console.WriteLine(queue); //front = 3 rear = 4 count = 1 data = 5 queue.Dequeue(); Console.WriteLine(queue); //queue is empty. queue.Enqueue(0); queue.Enqueue(1); queue.Enqueue(2); queue.Enqueue(3); queue.Enqueue(4); //Queue is full Console.WriteLine(queue); //front = 4 rear = 3 count = 4 data = 0,1,2,3 Console.WriteLine(queue.Peek()); //0 queue.Dequeue(); Console.WriteLine(queue); //front = 0 rear = 3 count = 3 data = 1,2,3 queue.Dequeue(); Console.WriteLine(queue); //front = 1 rear = 3 count = 2 data = 2,3 queue.Dequeue(); Console.WriteLine(queue); //front = 2 rear = 3 count = 1 data = 3 queue.Dequeue(); Console.WriteLine(queue); //queue is empty. queue.Enqueue(9); Console.WriteLine(queue); //front = 3 rear = 4 count = 1 data = 9 Console.ReadLine(); |
当然，队列也可以用链表来实现，相对要容易很多。
先定义链表中的节点Node.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 | namespace 栈与队列 { public class Node { private T data; private Node public Node(T data, Node { this .data = data; this .next = next; } public Node(Node { this .next = next; this .data = default (T); } public Node(T data) { this .data = data; this .next = null ; } public Node() { this .data = default (T); this .next = null ; } public T Data { get { return this .data; } set { this .data = value; } } public Node { get { return next; } set { next = value; } } } } |
为了方便，定义了很多构造函数的重载版本，当然这些只是浮云，重点是理解结构：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( ',' ); } } } |
作者： 菩提树下的杨过
出处： http://yjmyzz.cnblogs.com
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！