队列的数组模拟与 STL queue 实战：从原理到代码实现

注意，队头元素不是 h 所指的位置，而是 h 所指的下一个位置。

// 队头元素
int front() {
    return q[h + 1];
}

时间复杂度：O(1)

4. 获取队尾 (back)

直接返回 t 指向的元素。

// 队尾元素
int back() {
    return q[t];
}

时间复杂度：O(1)

5. 判空 (empty)

当队头指针和队尾指针重合时，说明队列为空。

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

时间复杂度：O(1)

6. 有效元素个数 (size)

通过两个指针的差值计算。

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

时间复杂度：O(1)

完整测试代码

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

#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;
}

运行结果验证了 FIFO 特性，依次输出 1 到 10。

三、STL queue 容器

在实际开发中，C++ 标准库提供了现成的 queue 容器，封装了上述底层逻辑。

1. 创建方式

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

2. 常用接口

3. 测试示例

这里演示如何使用 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;
}

总结

队列作为一种先进先出的线性数据结构，在算法竞赛和工程实践中应用广泛。文章详细讲解了如何用数组模拟实现队列，包括入队、出队、获取队头/队尾元素、判空和计算元素个数等操作，重点分析了底层指针移动逻辑与时间复杂度。同时，对比介绍了 C++ 标准库 queue 容器的基本用法和接口函数。在实际使用中，若追求极致效率或需要自定义行为，数组模拟是常见选择；若注重开发效率，STL 容器则是更优解。