排队叫号——题解

解题思路

题目中的人员按照到达顺序排队，先到达的人先离开，正好符合队列“先进先出”的特点，因此可以使用 C++ STL 的 queue<int>。

根据操作编号分别处理：

• 操作 1 x：使用 q.push(x) 将编号加入队尾；
• 操作 2：先用 q.empty() 判断是否为空。非空时先输出 q.front()，再执行 q.pop()；
• 操作 3：非空时输出 q.front()，但不删除；
• 操作 4：非空时输出 q.back()；
• 操作 5：输出 q.size()。

易错点

1. pop() 没有返回值

不能写成：

int x = q.pop();

应该先读取，再删除：

int x = q.front();
q.pop();

2. 空队列不能调用 front()、back() 和 pop()

调用这些函数前必须先判断：

if (!q.empty()) {
    // 可以安全访问队头、队尾或删除队头
}

3. 查询队头不会删除元素

操作 3 只读取 front()，不能调用 pop()。

复杂度分析

每次队列操作的时间复杂度都是 $O(1)$，总时间复杂度为 $O(m)$。

队列最多保存 $m$ 个编号，空间复杂度为 $O(m)$。

参考代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int m;
    cin >> m;

    queue<int> q;

    while (m--) {
        int op;
        cin >> op;

        if (op == 1) {
            int x;
            cin >> x;
            q.push(x);
        } else if (op == 2) {
            if (q.empty()) {
                cout << -1 << "\n";
            } else {
                cout << q.front() << "\n";
                q.pop();
            }
        } else if (op == 3) {
            if (q.empty()) cout << -1 << "\n";
            else cout << q.front() << "\n";
        } else if (op == 4) {
            if (q.empty()) cout << -1 << "\n";
            else cout << q.back() << "\n";
        } else {
            cout << q.size() << "\n";
        }
    }

    return 0;
}