首页 > 代码库 > 3-08. 堆栈模拟队列(25)(ZJU_PAT 模拟)
3-08. 堆栈模拟队列(25)(ZJU_PAT 模拟)
题目链接:http://pat.zju.edu.cn/contests/ds/3-08
设已知有两个堆栈S1和S2,请用这两个堆栈模拟出一个队列Q。
所谓用堆栈模拟队列,实际上就是通过调用堆栈的下列操作函数:
(1) int IsFull(Stack S):判断堆栈S是否已满,返回1或0;
(2) int IsEmpty (Stack S ):判断堆栈S是否为空,返回1或0;
(3) void Push(Stack S, ElementType item ):将元素item压入堆栈S;
(4) 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行。
样例输入与输出:
序号 | 输入 | 输出 |
1 | 2 2 A 1 A 2 D D T | 1 2 |
2 | 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 |
PS:
个人觉得题意有点难理解!反正我是理解了好久!
代码如下:
#include <cstdio> #include <cstring> #include <iostream> #include <queue> #include <stack> using namespace std; stack<int>s1;//容量小的栈 stack<int>s2;//容量大的栈 int main() { int n1, n2; char c; while(~scanf("%d%d",&n1,&n2)) { if(n1 > n2) { int t = n1; n1 = n2; n2 = n1; } getchar(); int tt; int flag = 0; for(int i = 0; ; i++) { scanf("%c",&c); if(c == 'T')//结束输入 break; if(c == 'A') { scanf("%d",&tt); if(s1.size()==n1 && s2.size()!=0)//如果栈s1满且栈s2不为空,则队满 { printf("ERROR:Full\n"); continue; } if(s1.size()!=n1)//如果栈s1没有满,直接压入 s1.push(tt); else { int len = s1.size();//如果栈s1满,把栈s1的所有元素弹出压入s2 for(int i = 0; i < len; i++) { int t = s1.top(); s1.pop(); s2.push(t); } s1.push(tt);//压入s1 } } else if(c == 'D') { if(s1.size()==0 && s2.size()==0) { printf("ERROR:Empty\n"); continue; } if(s2.size() == 0)//若栈s2空就将s1中的所有元素弹出到栈s2中,然后出栈 { int len = s1.size(); for(int i = 0; i < len; i++) { int t = s1.top(); s1.pop(); s2.push(t); } } printf("%d\n",s2.top()); s2.pop(); } } } return 0; }
3-08. 堆栈模拟队列(25)(ZJU_PAT 模拟)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。