队列的C++实现（数组）——创建-进队-出队-返回队首元素-清空队列栈-处理队列 ...

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› C++›C++教程

队列的C++实现（数组）——创建-进队-出队-返回队首元素-清空队列栈-处理队列 ...

原作者: [db:作者] 来自: [db:来源] 收藏邀请

队列的数组实现，从队尾进入，对头删除。

队列长度用标志变量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 }