PTA（栈和队列）2-8 用两个栈实现队列

2-8 用两个栈实现队列

分数 6

作者 陈越

单位 浙江大学

一个队列（先进先出结构）可以用两个堆栈（后进先出结构）来实现，方法如下：

  1. 从两个空堆栈 s1 和 s2 开始。
  2. 当元素 e 入队时，它实际上是被推入到 s1。
  3. 当我们需要出队时，首先检查 s2。如果 s2 是空的，则把 s1 中的元素全部导入 s2，即将每个元素从 s1 弹出后马上推入 s2。然后从 s2 中弹出元素 —— s2 顶端元素一定是第一个进入 s1 的，所以是应该出列的第一个元素。

假设每个堆栈的推入和弹出操作都用 1 个单位时间，请你给出每个出队操作所花的时间。

输入格式：

输入首先在一行中给出一个正整数 N（≤103），是操作数量。随后 N 行，每行按以下格式给出一个操作：

1
操作 元素

其中 操作 或者是 I 表示入队，或者是 O 表示出队。每个 I 后面跟的 元素 是一个不超过 106 的正整数。O 操作后面不跟任何元素。
题目保证至少有一个 O 操作。

输出格式：

对每个出队操作，在一行中输出出队的那个元素和这出队操作所花费的单位时间数量，其间以 1 个空格分隔，行首尾不得有多余空格。
若出队操作被调用时队列是空的，则在对应行中输出 ERROR。

输入样例：

1
2
3
4
5
6
7
8
9
10
11
10
I 20
I 32
O
I 11
O
O
O
I 100
I 66
O

输出样例：

1
2
3
4
5
20 5
32 1
11 3
ERROR
100 5

题目引用自攀拓考试真题（2023年夏季）。

答案

一遍过

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <stack>

using namespace std;

int main() {
    int N;
    cin >> N;
    stack<int> stack1; // 对应s1
    stack<int> stack2; // 对应s2
    char c; // c是操作，I是入队，O是出队
    int num; // 用于读取入栈的数
    for (int i = 0; i < N; ++i) {
        cin >> c;
        if (c == 'O') { // 出队操作
            int count = 0; // 计算出队时间
            if (stack1.empty() && stack2.empty()) { // 如果是都是空，直接返回ERROR
                cout << "ERROR" << endl;
                continue;
            } else if (!stack2.empty()){ // 如果s2还没出栈完，先出栈
                cout << stack2.top();
                stack2.pop();
                count++;
                cout << " " << count << endl;
            } else { // s2里面没有，但是s1里面还有
                while (!stack1.empty()) { // 把1中的全部放入2中
                    stack2.push(stack1.top()); // 把1中的放入2中
                    stack1.pop();
                    count += 2; // 一出一进是两步
                }
                // 再拿出2的栈顶
                cout << stack2.top();
                stack2.pop();
                count++;
                cout << " " << count << endl;
            }
        } else { // 如果是入队操作
            cin >> num;
            stack1.push(num);
        }
    }
}