队列的数组模拟实现与 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++ 标准库提供了 queue 容器适配器，封装了底层实现细节，方便直接使用。

创建与接口

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

常用接口包括：

1. size / empty：返回队列实际元素个数或判断是否为空，时间复杂度均为 O(1)。
2. push / pop：分别用于入队和出队，时间复杂度均为 O(1)。
3. 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;
}

运行结果：

结语

队列是算法竞赛和工程实践中非常基础且重要的数据结构。通过数组模拟可以深入理解其内存布局与指针移动机制，而 STL queue 则提供了更安全的封装。在实际开发中，建议优先使用标准库，但在需要优化性能或处理特定边界条件时，手动实现往往能带来更大的灵活性。