队列的数组实现,从队尾进入,对头删除。
队列长度用标志变量size,它是独立于front和rear的一个变量。size == 0,队列为空。size == capacity,满队列。
一、结点声明
1 struct Node{
2 int Capacity;
3 int Front;
4 int Rear;
5 int Size;
6 int *Array;
7 };
8 typedef struct Node Queue;
Capacity队列容量;Front,Rear为队列首元素和尾元素的数组下标;Size为当前队列大小;Array指向整形数组的指针,存放队列元素。
二、非空判断
1 int queue::isEmpty(Queue *Q)
2 {
3 return Q->Size == 0; //独立于Q->Rear和Q->Front存在的一个标志
4 }
三、满队列判断
1 int queue::isFull(Queue *Q)
2 {
3 return (Q->Size == Q->Capacity );
4 }
四、创建队列
1 queue::Queue *queue::createQueue(int maxElements)
2 {
3 cout << "Please input the value of maxElements: " << endl;
4 scanf_s("%d", &maxElements);
5 if (maxElements < minQueueSize)
6 {
7 cout << "The size of queue is too small!" << endl;
8 return 0;
9 }
10 else
11 {
12 Queue *Q;
13 Q = (Queue *)new(Queue);
14 if (Q == NULL)
15 cout << "Out of space!" << endl;
16 Q->Array = new int[maxElements];
17 if (Q->Array == NULL)
18 cout << "Out of space!" << endl;
19
20 Q->Capacity = maxElements;
21 Q->Front = 1;
22 Q->Rear = 1; // Rear预初始化为1
23 Q->Size = 0; // 空队列标志
24 makeEmpty(Q);
25 return Q;
26 }
27 }
五、清空队列
1 void queue::makeEmpty(Queue *Q)
2 {
3 if (isEmpty(Q))
4 cout << "Donnot need to makeEmpty the queue!" << endl;
5 Q->Size = 0; // 空队列标志,初始状态下标如下
6 Q->Front = 1;
7 Q->Rear = 0;
8 }
六、循环队列实现
1 int queue::isCycle(int value, Queue *Q)
2 {
3 if (++value == Q->Capacity) //下标从0开始,故下标为Capacity,表示循环队列的第一个元素,即下标为0
4 return 0;
5 return value; 下标小于Capacity,可正常自增
6 }
七、进队列
1 queue::Queue *queue::enQueue(Queue *Q)
2 {
3 if (isFull(Q))
4 cout << " Full queue! " << endl;
5 else
6 {
7 int x = 0;
8 cout << "Please input the number to enQueue!" << endl;
9 scanf_s("%d", &x); // 取地址符
10 Q->Size++;
11 Q->Rear = isCycle(Q->Rear,Q); // 循环队列自增
12 Q->Array[Q->Rear] = x;
13 }
14 return Q; // 满队列则返回原队列,未满则进入队列后返回该队列
15 }
八、返回队首元素
1 int queue::front(Queue *Q)
2 {
3 return Q->Array[Q->Front]; //只返回队首元素,不出队列
4 }
九、出队列
1 queue::Queue *queue::deQueue(Queue *Q)
2 {
3 if (isEmpty(Q))
4 cout << "Empty queue! " << endl;
5 else
6 {
7 cout << "The front element of queue is :" << Q->Array[Q->Front] << endl;
8 Q->Front++;
9 Q->Size--;
10 }
11 return Q;
12 }
十、处理队列
1 void queue::disposeQueue(Queue *Q)
2 {
3 while (!isEmpty(Q))
4 {
5 Q->Size = 0; //循环终止条件
6 free(Q->Array);
7 free(Q);
8 }
9 }
原文链接: https://www.cnblogs.com/Lunais/p/5487593.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/233321
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!