基础实验3-2.5 堆栈模拟队列 (25分)
题目
设已知有两个堆栈S1和S2，请用这两个堆栈模拟出一个队列Q。
所谓用堆栈模拟队列，实际上就是通过调用堆栈的下列操作函数:
int IsFull(Stack S)：判断堆栈S是否已满，返回1或0；int IsEmpty (Stack S )：判断堆栈S是否为空，返回1或0；void Push(Stack S, ElementType item )：将元素item压入堆栈S；ElementType Pop(Stack S )：删除并返回S的栈顶元素。
实现队列的操作，即入队void AddQ(ElementType item)和出队ElementType DeleteQ()。
输入格式:
输入首先给出两个正整数N1和N2，表示堆栈S1和S2的最大容量。随后给出一系列的队列操作：A item表示将item入列（这里假设item为整型数字）；D表示出队操作；T表示输入结束。
输出格式:
对输入中的每个D操作，输出相应出队的数字，或者错误信息ERROR:Empty。如果入队操作无法执行，也需要输出ERROR:Full。每个输出占1行。
输入样例:
3 2
A 1 A 2 A 3 A 4 A 5 D A 6 D A 7 D A 8 D D D D T
输出样例:
ERROR:Full
1
ERROR:Full
2
3
4
7
8
ERROR:Empty
解题思路：
- 堆栈是把输入的顺序倒序，队列则不改变输入的顺序，所以，通过两次应用堆栈也就是把输入顺序连倒两次，就回到了 原来的输入顺序，也就是队列的顺序。
- 用容量较小的栈用来存放输入的顺序，用容量较大的栈来存放输出顺序（队列顺序）。（设容量较小的栈为st1，容量较 大的栈为st2）
原因：如果用st2来存放输入顺序，此时如果出现st2存放的数的数目要大于容量较小的栈且要进行出队操作，st1无法存储st2除栈底以外的元素，从而无法完成出队操作，所以要用st1存输入的顺序，st2用来存输出顺序。 - 如果st1已经存满，且st2不为空，则不可以再入队元素。
原因：如果此时入队元素，则必然要把st1的元素弹出压入st2中，这样会导致输出顺序不满足队列的顺序（可手动模拟下）。
代码实现：
#include<bits/stdc++.h>
using namespace std;
stack<int> st1, st2;
int n1, n2;
int main() {
cin >> n1 >> n2;
if(n1 > n2) swap(n1, n2);
char op;
while(cin >> op, op != 'T') {
if(op == 'A') {
int x;
cin >> x;
if(st1.size() < n1) st1.push(x);
else if(st1.size() == n1 && st2.size() != 0) puts("ERROR:Full"); //思路3
else {
while(st1.size()) {
st2.push(st1.top()), st1.pop();
}
st1.push(x);
}
}
else {
if(st1.empty() && st2.empty()) puts("ERROR:Empty");
else if(st2.size()) {
cout << st2.top() << endl;
st2.pop();
} else {
while(st1.size()) {
st2.push(st1.top()), st1.pop();
}
cout << st2.top() << endl;
st2.pop();
}
}
}
return 0;
}
测试用例：
用例1：
输入：
3 2
A 1 A 2 A 3 A 4 A 5 D A 6 D A 7 D A 8 D D D D T
输出：
ERROR:Full
1
ERROR:Full
2
3
4
7
8
ERROR:Empty
说明：两栈不等容，测试错误信息。
用例2：
输入：
2 2
A 1 A 2 D D T
输出：
1
2
说明：等容量
用例3：
输入：略
输出：略
说明：随机测试最大容量
参考资料：
[1] 数据结构学习与实验指导/陈越主编；何钦铭等编著.–2版.–北京：高等教育出版社，2019.7
