顺序队列

顺序队列是用一组地址连续的存储单元存放队列中的元素,并附设两个指针: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;
}

入队

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;
}

时间复杂度:所有操作均为 O(1)O(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 取模,使结果落到合法区间。

详细步骤:

  1. 循环队列中 rear 可能因为指针回绕而小于 front,所以不能用 rear - front 直接作为答案。
  2. 正确公式为元素个数 = (rear - front + m) % m,即先加上数组长度 m 保证非负,再对 m 取模把结果限制在 0 到 m-1 之间。
  3. 当 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 这一条件同时表示队空和队满,因此仅凭这一条件无法区分两种状态。

详细步骤:

  1. 在循环队列中,当 front == rear 时,既可能是队空(0 个元素),也可能是队满。
  2. 采用牺牲一个存储单元来区分队空与队满的约定下,队列最多存放 35 个元素,因此队满时 front 与 rear 也相等。
  3. 仅根据 front == rear 无法判断究竟是队空还是队满,所以元素个数可能是 0,也可能是 35。

最终答案:

D(0 或 35)。

习题 3

什么是循环队列?为什么要使用循环队列?如何区分循环队列的队空和队满?

循环队列假溢出队空与队满取模运算

解题思路:

本题要求解释循环队列的定义、动机与实现细节。答题时先说明循环队列是把顺序队列首尾相连形成的环,再指出它要解决普通顺序队列的假溢出问题,最后列出区分队空与队满的三种常见做法。

详细步骤:

  1. 什么是循环队列:把顺序队列的数组首尾相连形成一个环,队头或队尾指针到达数组末尾时下一个位置回到数组开头,通过取模运算(%)实现指针的循环移动。
  2. 为什么要使用:普通顺序队列存在“假溢出”问题——front 和 rear 不断后移,rear 到达数组末尾时即使数组前面还有空闲空间也无法再入队;循环队列把数组首尾相连、重复利用前面的空闲空间,解决了假溢出并提高了空间利用率。
  3. 区分方法一(最常用):牺牲一个存储单元,约定队尾指针的下一个位置是队头时为队满——队空条件为 front == rear,队满条件为 (rear + 1) % MaxSize == front,队列最多存放 MaxSize-1 个元素。
  4. 区分方法二:增设 size 成员记录队列中元素个数——队空条件为 size == 0,队满条件为 size == MaxSize。
  5. 区分方法三:增设 tag 成员记录最近一次操作的类型,tag=0 表示最近一次是删除操作、tag=1 表示最近一次是插入操作——队空条件为 front == rear && tag == 0,队满条件为 front == rear && tag == 1。

最终答案:

循环队列是把顺序队列的数组首尾相连形成的环,用取模运算(%)实现指针循环移动,用于解决普通顺序队列的假溢出问题、提高空间利用率。区分队空与队满常用三种方法:牺牲一个存储单元(队空 front == rear,队满 (rear + 1) % MaxSize == front)、增设 size 成员、或增设 tag 成员记录最近一次操作类型。

发现内容有问题?

告诉我们哪里需要改进。