顺序队列
顺序队列是用一组地址连续的存储单元存放队列中的元素,并附设两个指针:front(队头指针)和rear(队尾指针)。
#define MaxSize 100
typedef struct {
int data[MaxSize];
int front; // 队头指针
int rear; // 队尾指针
} SqQueue;
初始化:front = rear = 0
入队:data[rear++] = x
出队:x = data[front++]
循环队列将数组的首尾相连,形成一个环。当指针到达数组末尾时,下一个位置回到数组开头。这样可以重复利用数组空间,避免假溢出。
存储结构
#define MaxSize 100
typedef struct {
int data[MaxSize];
int front; // 队头指针,指向队头元素
int rear; // 队尾指针,指向队尾元素的下一个位置
} CirQueue;
初始化
void InitQueue(CirQueue &Q) {
Q.front = Q.rear = 0;
}
判空
bool QueueEmpty(CirQueue Q) {
return Q.front == Q.rear;
}
判满
bool QueueFull(CirQueue Q) {
return (Q.rear + 1) % MaxSize == Q.front;
}
(rear + 1) % MaxSize == front,而不是 rear == front!因为 rear == front 同时也是队空条件。为了区分队空和队满,循环队列牺牲一个存储单元,当队尾指针的下一个位置是队头时,认为队列已满。入队
bool EnQueue(CirQueue &Q, int x) {
if (QueueFull(Q)) return false; // 队满
Q.data[Q.rear] = x;
Q.rear = (Q.rear + 1) % MaxSize; // rear后移,取模实现循环
return true;
}
出队
bool DeQueue(CirQueue &Q, int &x) {
if (QueueEmpty(Q)) return false; // 队空
x = Q.data[Q.front];
Q.front = (Q.front + 1) % MaxSize; // front后移,取模实现循环
return true;
}
求队列长度
int QueueLength(CirQueue Q) {
return (Q.rear - Q.front + MaxSize) % MaxSize;
}
时间复杂度:所有操作均为 。
区分循环队列队空和队满的三种方法:
- 牺牲一个存储单元(本文采用):队满条件
(rear+1)%MaxSize == front - 增设size成员:记录队列中元素的个数,队满时 size == MaxSize
- 增设tag成员:tag=0表示最近一次操作是删除,tag=1表示最近一次操作是插入。当 front==rear 且 tag==0 时队空,当 front==rear 且 tag==1 时队满
习题 1
循环队列用数组A[0..m-1]存放元素,已知其队头指针front和队尾指针rear(rear指向队尾元素的下一个位置),则当前队列中的元素个数是( )
A. (rear - front + m) % m
B. rear - front + 1
C. rear - front
D. (rear - front) % m
解题思路:
本题考查循环队列中元素个数的计算。关键是注意 rear 可能因循环而小于 front,直接相减会得到负数,因此必须先加上数组长度 m 再对 m 取模,使结果落到合法区间。
详细步骤:
- 循环队列中 rear 可能因为指针回绕而小于 front,所以不能用 rear - front 直接作为答案。
- 正确公式为元素个数 =
(rear - front + m) % m,即先加上数组长度 m 保证非负,再对 m 取模把结果限制在 0 到 m-1 之间。 - 当 rear >= front 时,结果为 rear - front;当 rear < front 时,说明指针绕了一圈,结果为 rear - front + m。
最终答案:
A。
习题 2
设循环队列的存储空间为Q[1..35],初始状态为front=rear=35。现经过一系列入队与退队运算后,front=15,rear=15,则循环队列中的元素个数为( )
A. 15 B. 16 C. 20 D. 0或35
解题思路:
本题考查 front 等于 rear 时的状态判定。思路是回忆循环队列用 front == rear 这一条件同时表示队空和队满,因此仅凭这一条件无法区分两种状态。
详细步骤:
- 在循环队列中,当 front == rear 时,既可能是队空(0 个元素),也可能是队满。
- 采用牺牲一个存储单元来区分队空与队满的约定下,队列最多存放 35 个元素,因此队满时 front 与 rear 也相等。
- 仅根据 front == rear 无法判断究竟是队空还是队满,所以元素个数可能是 0,也可能是 35。
最终答案:
D(0 或 35)。
习题 3
什么是循环队列?为什么要使用循环队列?如何区分循环队列的队空和队满?
解题思路:
本题要求解释循环队列的定义、动机与实现细节。答题时先说明循环队列是把顺序队列首尾相连形成的环,再指出它要解决普通顺序队列的假溢出问题,最后列出区分队空与队满的三种常见做法。
详细步骤:
- 什么是循环队列:把顺序队列的数组首尾相连形成一个环,队头或队尾指针到达数组末尾时下一个位置回到数组开头,通过取模运算(%)实现指针的循环移动。
- 为什么要使用:普通顺序队列存在“假溢出”问题——front 和 rear 不断后移,rear 到达数组末尾时即使数组前面还有空闲空间也无法再入队;循环队列把数组首尾相连、重复利用前面的空闲空间,解决了假溢出并提高了空间利用率。
- 区分方法一(最常用):牺牲一个存储单元,约定队尾指针的下一个位置是队头时为队满——队空条件为
front == rear,队满条件为(rear + 1) % MaxSize == front,队列最多存放 MaxSize-1 个元素。 - 区分方法二:增设 size 成员记录队列中元素个数——队空条件为
size == 0,队满条件为size == MaxSize。 - 区分方法三:增设 tag 成员记录最近一次操作的类型,tag=0 表示最近一次是删除操作、tag=1 表示最近一次是插入操作——队空条件为
front == rear && tag == 0,队满条件为front == rear && tag == 1。
最终答案:
循环队列是把顺序队列的数组首尾相连形成的环,用取模运算(%)实现指针循环移动,用于解决普通顺序队列的假溢出问题、提高空间利用率。区分队空与队满常用三种方法:牺牲一个存储单元(队空 front == rear,队满 (rear + 1) % MaxSize == front)、增设 size 成员、或增设 tag 成员记录最近一次操作类型。
