本文实例讲述了C#数据结构之队列(Quene)。分享给大家供大家参考,具体如下:
队列(Quene)的特征就是“先进先出”,队列把所有操作限制在"只能在线性结构的两端"进行,更具体一点:添加元素必须在线性表尾部进行,而删除元素只能在线性表头部进行。
先抽象接口IQuene<T>
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
|
namespace 栈与队列
{
public interface IQuene<T>
{
/// <summary>
/// 取得队列实际元素的个数
/// </summary>
/// <returns></returns>
public int Count();
/// <summary>
/// 判断队列是否为空
/// </summary>
/// <returns></returns>
public bool IsEmpty();
/// <summary>
/// 清空队列
/// </summary>
public void Clear();
/// <summary>
/// 入队(即向队列尾部添加一个元素)
/// </summary>
/// <param name="item"></param>
public void Enquene(T item);
/// <summary>
/// 出队(即从队列头部删除一个元素)
/// </summary>
/// <returns></returns>
public T Dequene();
/// <summary>
/// 取得队列头部第一元素
/// </summary>
/// <returns></returns>
public T Peek();
}
}
|
下面是基于数组实现的示意图:
实现思路:用一个数组存放所有元素,同时设置二个关键变量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
|
using System;
using System.Text;
namespace 栈与队列
{
/// <summary>
/// 循环顺序队列
/// </summary>
/// <typeparam name="T"></typeparam>
public class CSeqQueue<T>:IQueue<T>
{
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
|
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
|
namespace 栈与队列
{
public class Node<T>
{
private T data;
private Node<T> next;
public Node(T data, Node<T> next)
{
this .data = data;
this .next = next;
}
public Node(Node<T> next)
{
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<T> Next
{
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
|
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( ',' );
}
}
}
|
希望本文所述对大家C#程序设计有所帮助。