3-9 堆栈模拟队列
2023-09-14 09:07:12 时间
设已知有两个堆栈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
思路:
这道题没有给具体的操作过程,需要我们自己想,可以分类讨论:
注意,我们要使用小的栈容量首先存放元素,因为如果满了以后,要将这些元素放入大的栈,那样才能放下。
不管大的容量比小的大多少,都只能放下小的容量的最大值。因为如果多放,大的栈里的顺序会乱。也就是说,当大容量栈里有元素时,小容量栈满了就是队列满了。同样,大容量栈为空,小容量栈满了就全放入大容量栈即可。
如果要输出,就先从大容量站里输出,如果大容量栈为空,就将小容量栈全放入大容量栈,输出一个元素后,再全还回小容量栈。因为不还回去的话,判断队列满会有问题。
代码:
#include <bits/stdc++.h>
using namespace std;
int main() {
stack<int> s1, s2;
int n1, n2, num;
cin >> n1 >> n2;
if (n1 > n2) swap(n1, n2);
char c;
while (true) {
cin >> c;
if (c == 'T') {
return 0;
}
else if (c == 'A') {
cin >> num;
if (s1.size() == n1) {
if (s2.size() != 0) {
cout << "ERROR:Full" << endl;
continue;
}
else {
while (s1.size()) {
s2.push(s1.top());
s1.pop();
}
s1.push(num);
}
}
else {
s1.push(num);
}
}
else if (c == 'D') {
if (s2.size() == 0) {
if (s1.size() == 0) {
cout << "ERROR:Empty" << endl;
continue;
}
else {
while (s1.size()) {
s2.push(s1.top());
s1.pop();
}
}
}
cout << s2.top() << endl;
s2.pop();
if (s1.size() == 0) {
while (s2.size()) {
s1.push(s2.top());
s2.pop();
}
}
}
}
}
相关文章
- 数组模拟栈和队列
- hdu1022 模拟栈
- 自己整理的模拟爬虫的user-agent
- Java 第十一届 蓝桥杯 省模拟赛 正整数的摆动序列
- Java实现蓝桥杯模拟存储转换
- Fiddler进行模拟Post提交json数据,总为null解决方式(转)
- HTML 模拟滚动条
- android脚步---数字时钟和模拟时钟
- 重新整理数据结构与算法——单双链表模拟队列[四]
- 重新整理数据结构与算法——数组模拟队列和环形队列[三]
- 720. 词典中最长的单词(模拟+排序)
- LeetCode-1823. 找出游戏的获胜者【队列,递归,数组,数学,模拟】
- 3-6 银行业务队列简单模拟
- 【C语言】详解strlen函数 | 模拟实现strlen函数的三种方法 | 写库函数的人是如何实现这个函数的