队列 queue

引言

队列（queue）是一种线性的数据结构，和栈一样是一种运算受限制的线性表。其限制只允许从表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。一般允许进行插入的一端我们称为队尾，允许删除的一端称为队首。队列的插入操作又叫入队，队列的删除操作又叫出队。

可以把队列想象成购物时排队结账的时候的队伍，先排队的人会先结账，后排队的人会后结账，并且不允许有插队的行为，只能在队伍的末尾进行排队。这就是队列的特点，具有先进先出（FIFO——First In First Out）的性质。

实现

由于队列和栈都是线性表，所以队列也同样可以用数组模拟来手动实现。但是由于队列的出队与入队在不同的两端，所以我们要引入一个循环队列的概念。

如果单纯地用数组进行模拟，那么当有元素出队的时候，我们有两种办法处理剩余的元素：第一种是保持队首（front）位置不变，其余所有的元素顺序往前移动一位；第二种是让队首（front）向后移动一位，其余每个元素的位置不变，也就是使现在的位置成为新的队首位置。

第一种方法需要移动队列的所有元素，时间效率非常低，第二种只需要移动队头则变得非常简单，但第二种会导致之前队头所在的位置以后不会再被用到，造成空间的浪费。循环队列就解决了这个问题。

在实际使用队列中，为了使队列的空间能重复使用，一旦队列的头（front）或者尾（rear）超出了所分配的队列空间，则让它指向队列的起始位置，从 MaxSize-1 增加 1 变成 0

当元素装满整个队列之后就会造成溢出，所以如果要手动实现队列的话，最好提前预估队列的最大容量。

手动实现队列：

#define maxsize 10000
class queue {
    int q[maxsize];
    int front, rear, count;
    queue() {
        front = 0;
        rear = 0;
        count = 0;
    }
    void push(int x) {
        count++;
        if (count == maxsize) {
            // 溢出
        }
        q[rear] = x;
        rear = (rear + 1) % maxsize;
    }
    int pop() {
        count--;
        front = (front + 1) % maxsize;
        return q[front];
    }
    int front_val() {
        return q[front];
    }
    bool empty() {
        if (count == 0) {
            return true;
        }
        return false;
    }
};

STL 中的队列

在日常使用中，往往不需要手动实现队列，在 C++ 中有已经写好的队列，供我们使用。下面是使用 C++ 队列的示例代码。

#include <queue>
#include <iostream>
using namespace std;
int main() {
    queue<int> q; // 声明一个装 int 类型数据的队列
    q.push(1); // 入队
    q.push(2);
    q.push(3);
    cout << q.size() << endl; // 输出队列元素个数
    while (!q.empty()) { // 判断队列是否为空
        cout << q.front() << endl; // 访问队首元素
        q.pop(); // 出队
    }
    return 0;
}

总结

方法	功能
push	入队
pop	出队
front	访问队首元素
size	大小
empty	是否为空

C++ queue 官方文档