Logo

顺序队列

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

答案与解析

答案：A

解析： 循环队列中，由于指针可能循环（rear可能小于front），所以需要加上m再取模来保证结果为正。

元素个数 = (rear - front + m) % m

  • 当 rear >= front 时，结果为 rear - front
  • 当 rear < front 时，结果为 rear - front + m（绕了一圈）

习题 2

设循环队列的存储空间为Q[1..35]，初始状态为front=rear=35。现经过一系列入队与退队运算后，front=15，rear=15，则循环队列中的元素个数为（ ）

A. 15 B. 16 C. 20 D. 0或35

答案与解析

答案：D

解析： 在循环队列中，当 front == rear 时，可能是队空（0个元素），也可能是队满（35个元素，因为牺牲了一个空间来区分队空和队满，所以最多35个元素）。

仅根据 front == rear 无法判断是队空还是队满，所以元素个数可能是0或35。

习题 3

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

答案与解析

什么是循环队列： 循环队列是将顺序队列的数组首尾相连，形成一个环。当队头或队尾指针到达数组末尾时，下一个位置回到数组开头。通过取模运算（%）实现指针的循环移动。

为什么要使用循环队列： 普通顺序队列存在”假溢出”问题：随着入队和出队操作，front和rear指针都不断后移，当rear到达数组末尾时，即使数组前面还有空闲空间（因为出队操作释放了前面的空间），也无法再入队。循环队列通过将数组首尾相连，重复利用前面的空闲空间，解决了假溢出问题，提高了空间利用率。

如何区分队空和队满： 循环队列中，队空和队满时都可能出现 front == rear 的情况，需要额外的方法来区分：

  1. 牺牲一个存储单元（最常用）：约定队尾指针的下一个位置是队头时为队满。

    • 队空条件：front == rear
    • 队满条件：(rear + 1) % MaxSize == front
    • 队列最多存放 MaxSize-1 个元素

  2. 增设size成员：记录队列中元素的个数。

    • 队空条件：size == 0
    • 队满条件：size == MaxSize

  3. 增设tag成员：记录最近一次操作的类型。

    • tag=0表示最近一次是删除操作，tag=1表示最近一次是插入操作
    • 队空条件：front == rear && tag == 0
    • 队满条件：front == rear && tag == 1
上一章节基本概念队列的定义、特点与基本操作。
下一章节链式队列链式队列的存储结构与基本操作实现。
数据结构