队列

队列

定义

队列，是一种「先进先出」的线性数据结构。

理解

一般情况下，元素从一端进入队列，从另一端离开队列。元素进入的一端称为队尾，元素离开的一端称为队首。
添加元素时，只能将其插入到队尾（即入队操作）；删除元素时，只能将队首元素从队列中取出（即出队操作）。

代码模板

涉及到队列的操作，可以方便地利用标准模板库 STL 中的 queue 实现。

1
2
3
4
5
6
7
8
9
10
11
12
queue<int> que; // 定义一个队列
int num;

que.push(num); // 入队

int ft = que.front(); // 取队首元素
int bk = que.back(); // 取队尾元素

que.pop(); // 出队

bool flag = que.empty(); // 判断队列是否为空
int sz = que.size(); // 查询队列中元素数量

具体应用

约瑟夫环问题

n 个人围成一个圈玩游戏，按照顺时针顺序从 1 到 n 编号。也就是说，从第 i 个人顺时针数一位是第 i + 1 个人，从第 n 个人顺时针数一位是第 1 个人。
游戏规则如下：

  1. 从第 1 个人的位置开始。每次沿着顺时针方向数 k 个人，数的时候要包含开始数的那个人。数到的第 k 个人需要离开圈子，意味着输掉游戏。
  2. 如果圈子里剩余的人不止一个，那么从刚刚输掉游戏的人的下一位开始继续数 k 个，并进行淘汰。
  3. 如果圈子里只剩一个人，那么他获得最终的胜利。

最直观的方法是模拟游戏过程。使用队列存储圈子中人的编号，初始时将 1 到 n 的所有编号依次加入队列，队首元素即为第 1 个人的编号。
每一轮游戏中，从当前编号开始数 k 个，数到的第 k 个人离开圈子。模拟这个过程的做法是，将队首元素取出并将该元素在队尾处重新加入队列（模拟绕圈），重复该操作 k − 1 次，则在 k − 1 次操作之后，队首元素即为这一轮中数到的第 k 个人的编号，将队首元素取出并且不放回队尾，即为数到的第 k 个人离开圈子。上述操作之后，新的队首元素即为下一轮游戏开始数的起始编号。每一轮游戏之后，圈子中减少一个人，队列中减少一个元素。
重复上述过程，直到队列中只剩下 1 个元素，该元素即为获胜者的编号。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
queue<int> que;
for(int i = 1; i <= n; i++){ // 初始时将 1 到 n 的所有编号依次加入队列
    que.push(i);
}
while(que.size() > 1){
    // 每次数前 k - 1 个人时，把对应编号从队首拿出并放回队尾
    for(int i = 1; i <= k - 1; i++){
        que.push(que.front());
        que.pop();
    }
    // 每次数到第 k 个人时，把对应编号从队首拿出（即输掉比赛）
    que.pop();
}
// 最终队列中剩下的那个元素即为获胜者的编号
cout << que.front() << endl;

集合的前 N 个元素

有这样一个集合 M，定义如下：

  1. 数 1 属于 M。
  2. 如果 X 属于 M，则 Y = 2 * X + 1和 Z = 3 * X + 1 也属于 M。
  3. 此外再没有别的数属于 M。

按递增次序生成集合 M 中最小的 N 个数，输出第 N 小的数。

可以用两个队列 a 和 b 分别来存放 Y 和 Z 中的数，然后递推求出最小的第 N 项，方法如下：

  1. 初始时 M 中只有 1，队列 a 和 b 为空。
  2. 从 M 中取出最大的数 x，将 2 * x + 1 和 3 * x + 1 分别放入队列 a 和队列 b 的队尾。
  3. 将队列 a 和队列 b 的队首元素进行比较，可能有三种情况：
    a. a.front() > b.front()
    b. a.front() = b.front()
    c. a.front() < b.front()
    将比较的小者取出送入 M（会成为 M 中新的最大值），取出数的那个队列删除队首元素。
  4. 重复步骤 2 和 3 直至取出第 N 项为止。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<int> M(n + 1);
queue<int> a, b;
M[1] = 1;
for(int i = 2; i <= n;  i++){
    int x = M[i - 1]; // 从 M 中取出最大的数 x
    // 将 2 * x + 1 和 3 * x + 1 分别放入队列 a 和 b 的队尾，拓展备用
    a.push(2 * x + 1);
    b.push(3 * x + 1);
    // 分类讨论三种情况
    if(a.front() < b.front()){
        M[i] = a.front();
        a.pop();
    }
    else if(a.front() > b.front()){
        M[i] = b.front();
        b.pop();
    }
    else{ // 队首元素相等，两个队列的队首元素都要删除
        M[i] = a.front();
        a.pop();
        b.pop();
    }
}
cout << M[n] << endl;

双端队列

定义

双端队列，是一种线性数据结构，可以在队首和队尾进行元素的插入和删除。

理解

双端队列可以视为栈和队列功能的结合。一般情况下，双端队列支持四个操作：

  1. 在队首插入一个元素
  2. 在队首删除一个元素
  3. 在队尾插入一个元素
  4. 在队尾删除一个元素

代码模板

涉及到双端队列的操作，可以方便地利用标准模板库 STL 中的 deque 实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
deque<int> dq; // 定义一个队列
int num;

dq.push_front(num); // 插入元素到队首
dq.pop_front(); // 删除队首元素
dq.push_back(num); // 插入元素到队尾
dq.pop_back(); // 删除队尾元素


int ft = dq.front(); // 取队首元素
int bk = dq.back(); // 取队尾元素

bool flag = que.empty(); // 判断双端队列是否为空
int sz = que.size(); // 查询双端队列中元素数量

dq.clear(); // 清空双端队列