开发者LT的博客
0%

数据结构——环形队列

发表于 分类于
本文字数： 5.4k 阅读时长 ≈ 5 分钟
环形队列的C++实现

什么是环形队列

环形队列是把数组在逻辑上首尾相接的队列：下标走到末尾时用取模运算绕回开头，把出队腾出的空间重新利用起来。物理上它还是一个数组。

队列和栈一样，不是全新的数据结构，只是给数组或链表规定了元素的进出规则：

  • 栈只开放一端，叫做栈顶，入栈和出栈都在栈顶，先进后出
  • 队列开放两端：从队尾入队、从队头出队，特点是先进先出

先看一个例子。容量 10 的队列，front 标记队首、rear 标记队尾的下一个空位：

1
2
3
4
5
6
7
8
9
10
11
12
13
入队 0、10、…、90 十个元素后：
 ┌────┬────┬────┬────┬────┬────┬────┬────┬────┬────┐
 │  0 │ 10 │ 20 │ 30 │ 40 │ 50 │ 60 │ 70 │ 80 │ 90 │
 └────┴────┴────┴────┴────┴────┴────┴────┴────┴────┘
   ↑                                                 ↑
 front=0                                          rear=10

再出队 8 个（front 涨到 8）：
 ┌────┬────┬────┬────┬────┬────┬────┬────┬────┬────┐
 │  0 │ 10 │ 20 │ 30 │ 40 │ 50 │ 60 │ 70 │ 80 │ 90 │
 └────┴────┴────┴────┴────┴────┴────┴────┴────┴────┘
                                      ↑              ↑
                                   front=8        rear=10

队列里只剩 80、90 两个元素，前面 8 个位置虽然还有数字，实际上已经处于空闲状态。但 rear 已经到头——再入队就越界了。这就是假溢出：不是真的没空间，是出队腾出来的空间永远用不上，因为 front 和 rear 都只增不减。

这里就涉及到了环形队列的核心思路：把数组看成环，rear 走到末尾后绕回下标 0，front 也一样。下标移动不用 ++，而用取模：

1
rear = (rear + 1) % cap

以 cap = 7 为例：

  • rear 在下标 0~5 时，(rear + 1) % 7 就是 rear + 1，和 ++ 没区别
  • rear 在下标 6（最后一个位置）时，(6 + 1) % 7 = 0，绕回开头
1
2
3
4
5
6
下标：   0    1    2    3    4    5    6    7    8    9
       ┌────┬────┬────┬────┬────┬────┬────┬────┬────┬────┐
       │ 30 │ 40 │    │    │    │    │    │    │ 10 │ 20 │
       └────┴────┴────┴────┴────┴────┴────┴────┴────┴────┘
          ↑                                        ↑
        rear=2                                 front=8

从 front=8 出发沿下标增大方向走：pQue[8](10) → pQue[9](20) → 绕回 pQue[0](30) → pQue[1](40) → 撞上 rear=2 停。队列内容（队首到队尾）就是 10, 20, 30, 40。

有效元素在数组里被掰成了两段（下标 8-9 一段、0-1 一段），这是环形队列后面很多细节的根源。

一、结构定义

LoopQueue/main.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class LoopQueue
{
public:
	LoopQueue(int size = 10)
		:cap(size), front(0), rear(0), size(0)
	{
		pQue = new int[cap];
	}
	~LoopQueue()
	{
		delete[]pQue;
		pQue = nullptr;
	}
	// ...
private:
	int* pQue;	// 指向堆上的数组
	int cap;	// 容量
	int front;	// 队首元素的下标
	int rear;	// 队尾下一个空位的下标
	int size;	// 元素个数
};

和顺序栈对照着看：

  • pQue、cap 的作用完全一样，指向堆上的数组和表示容量
  • front 指向队首元素
  • rear 指向下一个可写入的位置，思路和顺序栈的 mtop 一致；所以队尾元素不是 pQue[rear]，而是 rear 的前一格
  • size 单独记录元素个数

二、判空与判满

判空：

front 和 rear 重合就是空：

LoopQueue/main.cpp - empty / Size
1
2
3
4
5
6
7
8
bool empty()
{
	return front == rear;
}
int Size()
{
	return size;
}

判满：

如果允许把 cap 个位置全部用满，那么队列满的时候 rear 绕一圈也会回到 front——这样的话，**front == rear 就会同时表示空和满两种状态**，没法区分。

所以判满必须额外付出一点代价，常见做法有两种：

  1. 牺牲一个位置：队列最多存 cap - 1 个元素，rear 再走一步撞上 front 就是满
  2. 加一个变量记录元素个数，size == cap 是满

这里用的是第一种：

1
// 队列满：(rear + 1) % cap == front

举例：

1
2
3
4
5
6
7
    front
      ↓
┌────┬────┬────┬────┬────┐
│ 10 │ 20 │ 30 │ 40 │    │
└────┴────┴────┴────┴────┘
                      ↑
                     rear

cap = 5，存了 4 个元素（10 ~ 40），rear = 4。(4 + 1) % 5 = 0 == front，判定为满。下标 4 的位置空着不用，这就是”牺牲”的那一格。

三、入队与出队

3.1 入队 push

LoopQueue/main.cpp - push
1
2
3
4
5
6
7
8
9
10
11
void push(int val)
{
	// 如果队列满了，先扩容
	if ((rear + 1) % cap == front)
	{
		expand(2 * cap);
	}
	pQue[rear] = val;
	rear = (rear + 1) % cap;
	size++;
}

三步：判满（满了先扩容）→ 写入 pQue[rear] → rear 沿环后移一格。

3.2 出队 pop

LoopQueue/main.cpp - pop
1
2
3
4
5
6
7
8
9
10
void pop()
{
	// 如果队列空了，报错
	if (front == rear)
	{
		throw "queue if empty";
	}
	front = (front + 1) % cap;
	size--;
}

出队就是 front 沿环后移一格。不真的删数据——front 就是有效元素的边界，被跳过的位置会在后续入队时被覆盖。

四、取队首与队尾

LoopQueue/main.cpp - Front / Rear
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int Front() const
{
	// 如果队列空了，报错
	if (front == rear)
	{
		throw "queue if empty";
	}
	return pQue[front];
}

int Rear() const
{
	// 如果队列空了，报错
	if (front == rear)
	{
		throw "queue if empty";
	}
	return pQue[(rear - 1 + cap) % cap];
}

Front 直接取 pQue[front]，因为 front 本来就指向队首元素。

Rear 要取的是队尾元素，位置是 rear 的前一个格子。这里有个特殊情况：rear 绕回 0 的时候，rear - 1 就是 -1，直接把rear-1当下标用就错了，所以写成 (rear - 1 + cap) % cap：

rear 不在 0 时，加不加 cap 不影响结果（比如 cap = 7、rear = 5：(5 - 1 + 7) % 7 = 4，和 5 - 1 一样），所以这一行把两种情况统一处理了。

五、扩容

环形队列的扩容不能像顺序栈那样，直接申请一块更大的数组，把旧数据整块拷过去

整块拷贝的话，front 和 rear 的位置原封不动。假设扩容前队列是满的，(rear + 1) % cap == front 成立；扩容后 cap 变了，但 front、rear 还是老位置，这个条件依然成立——判满逻辑仍然认为队列是满的，后面新扩出来的大片空间根本用不上。

正确的做法：从 front 出发沿环逐个走到 rear，按顺序拷进新数组的开头。拷完之后环被”拉直”：front = 0，rear = 元素个数。

LoopQueue/main.cpp - expand
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void expand(int Size)
{
	// 开辟新空间
	int* p = new int[Size];
	// 新空间的临时索引
	int i = 0;
	// 原空间的临时索引
	int j = front;
	// 从front遍历到rear，逐个赋值
	for (; j != rear; i++, j = (j + 1) % cap)
	{
		p[i] = pQue[j];
	}
	delete[] pQue;
	pQue = p;
	cap = Size;
	front = 0;
	rear = i;
}

两个索引同步推进：i 在新数组上每次 +1，j 在旧数组上沿环绕行。j 走完一圈撞上 rear 时停下，此时 i 正好等于元素个数。

用 cap = 4 扩容到 8 的例子走一遍。扩容前 front = 2、rear = 1，环上有 3 个元素：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
扩容前（cap = 4）：
      rear=1 front=2
          ↓    ↓
  ┌────┬────┬────┬────┐
  │ 30 │    │ 10 │ 20 │
  └────┴────┴────┴────┘
    [0]  [1]  [2]  [3]

沿环读：10 → 20 → 30

扩容后（cap = 8）：
  front=0        rear=3
    ↓              ↓
  ┌────┬────┬────┬────┬────┬────┬────┬────┐
  │ 10 │ 20 │ 30 │    │    │    │    │    │
  └────┴────┴────┴────┴────┴────┴────┴────┘
    [0]  [1]  [2]  [3]  [4]  [5]  [6]  [7]

j 的走位：从 front = 2 出发 → p[0] = pQue[2](10) → j = 3 → p[1] = pQue[3](20) → j = (3+1)%4 = 0 → p[2] = pQue[0](30) → j = 1，撞上 rear，停。i = 3，所以 rear = 3。

元素个数没变，所以 size 成员在扩容里不用动

六、测试代码与运行结果

LoopQueue/main.cpp - main
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int main()
{
	LoopQueue lq;
	for (int i = 0; i < 10; i++)
	{
		lq.push(i * 10);
	}
	cout << lq.Front() << " " << lq.Rear() << endl;
	lq.push(100);
	cout << lq.Front() << " " << lq.Rear() << endl;
	while (!lq.empty())
	{
		cout << lq.Front() << " " << lq.Rear() << endl;
		lq.pop();
	}
}

默认容量 10。push 0、10、…、90 共 10 个元素——因为牺牲了一个位置，push 第 10 个（90）时队列已满，先扩容到 20 再写入。之后 push 100 不会触发扩容。

运行结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
0 90
0 100
0 100
10 100
20 100
30 100
40 100
50 100
60 100
70 100
80 100
90 100
100 100

前两行是两次主动打印：第一次队首 0、队尾 90；扩容写入 100 后，队首 0、队尾 100。后面 11 行是 while 循环，每轮打印队首和队尾再出队——队首从 0 一路涨到 100，队尾始终是 100（没有新元素入队）。

七、复杂度

操作 复杂度
push 均摊 O(1)，扩容那次 O(n)
pop O(1)
Front / Rear / Size / empty O(1)

八、常见问题

  1. 环形队列解决什么问题？ 普通数组队列出队后 front 只增不减，前面的空间永远用不上（假溢出）。环形让 front、rear 走到末尾绕回开头，把出队腾出的空间重新利用起来。
  2. 为什么判满要牺牲一个位置？ 不牺牲的话，队列满时 rear 绕回 front，front == rear 同时表示空和满，无法区分。牺牲一格后，rear 再走一步撞上 front 即满；另一种做法是额外维护 size，用 size == cap 判满。
  3. Rear() 为什么要先 + cap？ rear = 0 时 rear - 1 = -1，C++ 负数取模结果仍为负（-1 % 10 == -1），+ cap 后才是正确下标 9。
  4. 扩容为什么不能整块拷贝？ 整块拷贝后 front、rear 位置不变，判满条件仍然成立，新空间用不上；而且有效元素在数组中可能被掰成两段，必须从 front 沿环走到 rear 逐个搬到新数组开头。
  5. 元素个数除了用成员变量记，还能怎么统计？ 从 front 沿环走到 rear 数一遍。但遍历不能写 i++、也不能用 i < rear 当条件——front 和 rear 在环上的位置是任意的，必须写 i != rear 和 i = (i + 1) % cap。遍历是 O(n)，成员变量记录是 O(1)，所以这份代码选了后者。
  6. 环形队列用在哪里？ 生产者-消费者模型、任务调度队列、通信缓冲区（串口、网络收包缓冲），以及二叉树层序遍历这类需要 FIFO 的场景。