C++中队列queue的用法实例详解

什么是队列

队列是一种线性数据结构，具有“先进先出”的特点。队列只允许在队尾插入元素，在队头删除元素。队列的常见操作包括入队（enqueue）、出队（dequeue）、获取队头元素（front）和获取队尾元素（back）。队列的实现可以使用数组或链表等数据结构。

C++中队列queue的使用

在C++ STL中，队列（queue）是一种容器适配器。它基于deque实现，提供了队列的常见操作。使用queue需要包含头文件<queue>。

创建一个空队列

可以使用默认构造函数创建一个空队列：

queue<int> q;

这将创建一个空的int类型的队列。

将元素入队

可以使用push方法将元素加入队列的尾部：

q.push(1); // 将1加入队尾
q.push(2);
q.push(3);

获取队头元素

可以使用front方法获取队列头部元素的值，但是不会将其从队列中删除：

int x = q.front(); // 获取队头元素的值

将元素出队

可以使用pop方法将队头元素删除：

q.pop(); // 删除队头元素

获取队列的长度

可以使用size方法获取队列的长度：

int size = q.size(); // 获取队列的长度

判断队列是否为空

可以使用empty方法判断队列是否为空：

bool is_empty = q.empty(); // 判断队列是否为空

队列实例演示

以下是两个队列的实例：

实例1：使用队列求解迷宫问题

迷宫问题是一类经典的搜索问题，可以使用队列进行求解。假设有一个$n\times m$的迷宫，用二维数组表示，0表示墙，1表示路。现在给定起点和终点的坐标，求从起点到终点的最短距离。

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;

int n, m, sx, sy, ex, ey; // n是行数，m是列数

int g[N][N], d[N][N]; // g存储迷宫，d记录到起点的步数

int bfs() {
    queue<pair<int, int>> q;
    q.push({sx, sy}); // 将起点入队
    memset(d, -1, sizeof d);
    d[sx][sy] = 0;
    while (!q.empty()) {
        auto t = q.front(); q.pop();
        int x = t.first, y = t.second;
        if (x == ex && y == ey) return d[x][y];
        for (int i = -1; i <= 1; ++ i)
            for (int j = -1; j <= 1; ++ j) {
                if (i != 0 && j != 0) continue; // 只考虑上下左右四个方向
                int nx = x + i, ny = y + j;
                if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && g[nx][ny] && d[nx][ny] == -1) {
                    d[nx][ny] = d[x][y] + 1; // 更新步数
                    q.push({nx, ny}); // 将相邻的合法点入队
                }
            }
    }
    return -1; // 无解
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= m; ++ j) {
            cin >> g[i][j];
            if (g[i][j] == 1) g[i][j] = 1; // 路
            else if (g[i][j] == 0) g[i][j] = 0; // 墙
            else if (g[i][j] == 2) { // 起点
                sx = i, sy = j;
                g[i][j] = 1;
            } else if (g[i][j] == 3) { // 终点
                ex = i, ey = j;
                g[i][j] = 1;
            }
        }
    cout << bfs() << endl; // 输出最短步数
    return 0;
}

在上述实例中，我们使用了一个pair类型的元素表示坐标，将坐标存储在队列中，实现了迷宫问题的求解。

实例2：使用队列实现栈

虽然队列和栈是两种不同的数据结构，但是我们可以利用队列实现栈。具体实现方式是利用两个队列，一个队列存储栈中的元素，另一个队列用于辅助操作。

#include <bits/stdc++.h>
using namespace std;

class MyStack {
public:
    queue<int> q1, q2;

    void push(int x) {
        q1.push(x); // 将元素加入队列1
    }

    int pop() {
        while (q1.size() > 1) { // 将队列1中前n-1个元素转移到队列2中
            int x = q1.front(); q1.pop();
            q2.push(x);
        }
        int x = q1.front(); q1.pop(); // 取出队列1中的最后一个元素
        swap(q1, q2); // 交换队列1和队列2
        return x; // 返回出队元素的值
    }

    int top() {
        int x = pop(); // 先将出队元素取出
        push(x); // 再将出队元素加回队列
        return x; // 返回出队元素的值
    }

    bool empty() {
        return q1.empty(); // 判断队列1是否为空
    }
};

int main() {
    MyStack s;
    s.push(1);
    s.push(2);
    s.push(3);
    cout << s.top() << endl; // 输出3
    cout << s.pop() << endl; // 输出3
    cout << s.top() << endl; // 输出2
    cout << s.empty() << endl; // 输出0
    return 0;
}

在上述实例中，我们使用两个队列实现了一个栈，其关键是将队列1中前$n-1$个元素转移到队列2中，并取出队列1中的最后一个元素，从而实现出栈。同时，我们在出栈完成后将元素重新加入到队列1中，保证队列中元素的顺序不变。