- 循环顺序队列的描述与表示
- 循环顺序队列的操作接口定义
- 循环顺序队列的操作实现
循环顺序队列的描述与表示
队列
队列(Queue)是一种只允许在序列两端进行操作的线性结构。和日常生活中排队等待买票的法则相似,排在队头的人先买到票并离开队列,而新来的人则加入队尾等候。因此很容易理解队列仅允许在队头出队,在队尾入队。
循环顺序队列
采用顺序存储结构的队列成为顺序队列,和顺序栈相同,我们也采用动态分配空间的方式来获取这个存储空间。那么何为循环队列呢?为什么我们需要循环队列呢?试想,我们在排队等候买票的时候是不是有这样的场景,前面的人买完票就离开队列,而这时后面的人是不是每个人都要往前挪动一个位置呢?那么如果我们以同样的方法来处理我们的队列,每当一个元素出队的时候,就必须把后面所有的元素往前挪动一个位置,这样必然导致算法效率变低。因此,我们想到了将队列的首位相连,构成了一个循环队列。
循环队列类型定义如下: 1 2 3 4 5 6
| typedef struct { ElemType* base; int front; int rear; int maxSize; } SqQueue;
|
我们采用循环队列解决了元素出队时需要移动全部元素的问题,但是出现了一个新问题,在我们判空的时候我们采用的是判断队头位标和队尾位标是否一致的方式,而放在循环队列里,因为队列已经首尾相接,于是我们会发现这时候如果队列满了,队头位标和队尾位标也是一致的,解决方式有很多,比如:
1. 设置标志域标识队列的空或满,使用标志域数组同步记录 2.
设置长度域记录队列中元素个数,判断长度域即可 3.
少用一个元素空间,采用循环加一的方式,如果发现Q.front == (Q.rear + 1) % Q.maxSize
则认为队满。
以下的实现中我们采用了第三种方式。
本文中预定义的说明
预定义常量和类型
1 2 3 4 5 6 7 8
| #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -1
typedef int Status;
|
数据结构(存储结构)的表示
数据结构的表示用类型定义(typedef
)描述。数据元素类型约定为ElemType,读者在使用该数据类型时自行定义,如int
、char
等简单类型。
扩展引用调用
为了便于算法描述,我们使用了 C++ 语言中的引用调用参数传递方式。
循环队列操作接口定义
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| Status InitQueue_Sq(SqQueue &Q, int size);
void DestroyQueue_Sq(SqQueue &Q);
void ClearQueue_Sq(SqQueue &Q);
Status QueueEmpty_Sq(Squeue Q);
int QueueLength_Sq(SqQueue Q);
Status GetHead_Sq(SqQueue Q, ElemType &e);
Status EnQueue_Sq(SqQueue &Q, ElemType &e);
Status DeQueue_Sq(SqQueue &Q, ElemType &e);
|
循环队列接口实现
初始化循环队列
1 2 3 4 5 6 7 8 9 10 11
| Status InitQueue_Sq(SqQueue &Q, int size) { Q.base = (ElemType*)malloc(size * sizeof(ElemType)); if (NULL == Q.base) return OVERFLOW; Q.maxSize = size; Q.front = 0; Q.rear = 0;
return OK; }
|
销毁队列
1 2 3 4
| void DestroyQueue_Sq(SqQueue &Q) { free(Q.base); }
|
将队列置空
1 2 3 4 5
| void ClearQueue_Sq(SqQueue &Q) { Q.front = 0; Q.rear = 0; }
|
判断队列是否为空
1 2 3 4 5 6 7
| Status QueueEmpty_Sq(SqQueue Q) { if (Q.front == Q.rear) return TRUE; else return FALSE; }
|
返回队列长度
1 2 3 4
| int QueueLength_Sq(Squeue Q) { return (Q.rear - Q.front + Q.maxSize) % Q.maxSize; }
|
取队头元素
1 2 3 4 5 6 7 8
| Status GetHead_Sq(SqQueue Q, ElemType &e) { if (QueueEmpty_Sq(Q)) return ERROR; e = Q.base[Q.front];
return OK; }
|
入队
1 2 3 4 5 6 7 8 9
| Status EnQueue_Sq(SqQueue &Q, ElemType e) { if ((Q.rear + 1) % Q.maxSize == Q.front) return ERROR; Q.base[Q.rear] = e; Q.rear = (Q.rear + 1) % Q.maxSize;
return OK; }
|
出队
1 2 3 4 5 6 7 8 9
| Status DeQueue_Sq(SqQueue &Q, ElemType &e) { if (Q.front == Q.rear) return ERROR; e = Q.base[Q.front]; Q.front = (Q.front + 1) % Q.maxSize;
return OK; }
|
小结
队列的方式也成为排队。我们前面举例了排队排票的例子,而队列的产生实际上是由于随机前来的购票乘客数量和售票处的处理速度不相符,通过排队起到缓冲作用。程序中也是类似的,为了协调好数据输入和处理时间的关系,采用类似于排队的机制。再内从上,实现这种机制的方式就是队列。当我们需要处理通讯中发送的数据时,或由同时运行的多个程序所发送过来的数据时,会使用这种对队列中存储的不规则数据进行处理的方法。队列一般以环状缓冲区(ring
buffer)也就是我们说的循环队列的方式来实现。
参考资料
《数据结构》(吴伟民,李小妹)
《程序是怎样跑起来的》