队列的数组模拟实现与 STL queue 容器实战

判空与大小

当队头指针和队尾指针重合时，说明队列为空。元素个数即为两者的差值。

// 队列是否为空
bool empty() {
    return t == h;
}

// 队列的大小
int size() {
    return t - h;
}

完整测试示例

下面是一个完整的测试代码，演示了如何初始化、入队、遍历并出队。

#include <iostream>
using namespace std;

const int N = 1e6 + 10;
int h, t;
int q[N];

void push(int x) { q[++t] = x; }
void pop() { h++; }
int front() { return q[h + 1]; }
int back() { return q[t]; }
bool empty() { return t == h; }
int size() { return t - h; }

int main() {
    // 测试入队
    for (int i = 1; i <= 10; i++) {
        push(i);
    }
    
    // 循环输出直到队列为空
    while (size()) {
        cout << front() << " " << back() << endl;
        pop();
    }
    return 0;
}

STL queue 容器

在实际工程开发中，直接使用 C++ 标准库提供的 std::queue 更为便捷。它底层通常基于双端队列（deque）实现，封装好了所有接口。

基本用法

创建非常简单，指定数据类型即可。

queue<T> q; // T 可以是任意类型

常用接口

• size / empty：返回元素个数或判断是否为空，均为 O(1)。
• push / pop：入队和出队操作，O(1)。
• front / back：获取队头或队尾元素，但不删除，O(1)。

综合示例

我们可以利用 pair 类型来存储更复杂的数据，比如坐标或状态对。

#include <iostream>
#include <queue>
using namespace std;

typedef pair<int, int> PII;

int main() {
    queue<PII> q;
    
    // 入队
    for (int i = 1; i <= 10; i++) {
        q.push({i, i * 10});
    }
    
    // 遍历处理
    while (q.size()) {
        auto t = q.front();
        q.pop();
        cout << t.first << " " << t.second << endl;
    }
    return 0;
}

总结

队列是算法中的基础数据结构，核心在于 FIFO 特性。在需要频繁操作且对性能要求极高的场景下，手写数组模拟往往比 STL 容器更快，因为它省去了动态扩容和内存管理的开销。而在常规业务开发中，STL queue 提供了更好的安全性和易用性。掌握这两种实现方式，能帮你根据实际需求灵活选择。