3-08. 栈模拟队列(25)(ZJU_PAT 模拟)

时间:2022-09-21 07:50:46

主题链接: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 模拟)的更多相关文章

  1. 剑指Offer——Java实现栈和队列的互模拟操作

    剑指Offer--Java实现栈和队列的互模拟操作 栈模拟队列   题目:JAVA实现用两个栈来实现一个队列,完成队列的Push和Pop操作.队列中的元素为int类型.   思路:其实就是把队列正常入 ...

  2. PTA笔记 堆栈模拟队列&plus;求前缀表达式的值

    基础实验 3-2.5 堆栈模拟队列 (25 分) 设已知有两个堆栈S1和S2,请用这两个堆栈模拟出一个队列Q. 所谓用堆栈模拟队列,实际上就是通过调用堆栈的下列操作函数: int IsFull(Sta ...

  3. Java数组模拟队列 &plus; 优化

    队列介绍 队列是一个有序列表,可以用数组或是链表来实现. 遵循先入先出的原则. 即:先存入队列的数据,要先取出.后存入的要后取出 示意图:(使用数组模拟队列示意图)  数组模拟队列 队列本身是有序列表 ...

  4. Python笔记&lowbar;第二篇&lowbar;面向过程&lowbar;第二部分&lowbar;2&period;路径、栈和队列、内存修改

    这一部分分三个主题进行讲解,主要为后面的模块.包.第三方库的概念补充一些相关的内容. 1. 路径(Path): 相对路径和绝对路径. 举例1:我们先导入一个os库(模块)来观察一下路径 import ...

  5. 7-3 堆栈模拟队列(25 point&lpar;s&rpar;) 【数据结构】

    7-3 堆栈模拟队列(25 point(s)) 设已知有两个堆栈S1和S2,请用这两个堆栈模拟出一个队列Q. 所谓用堆栈模拟队列,实际上就是通过调用堆栈的下列操作函数: int IsFull(Stac ...

  6. JavaScript数组模拟栈和队列

    *栈和队列:js中没有真正的栈和队列的类型              一切都是用数组对象模拟的 栈:只能从一端进出的数组,另一端封闭       FILO   何时使用:今后只要仅希望数组只能从一端进 ...

  7. 【DataStructure In Python】Python模拟栈和队列

    用Python模拟栈和队列主要是利用List,当然也可以使用collection的deque.以下内容为栈: #! /usr/bin/env python # DataStructure Stack ...

  8. python--递归(附利用栈和队列模拟递归)

    博客地址:http://www.cnblogs.com/yudanqu/ 一.递归 递归调用:一个函数,调用的自身,称为递归调用 递归函数:一个可以调用自身的函数称为递归函数 凡是循环能干的事,递归都 ...

  9. php中数组模拟队列、栈的函数以及数组指针操作

    1,数组指针,current表示当前指针,输出其指向的元素:next表示指针移动到下一个元素:prev指针移动到上一个元素:end表示指针移动到最后一个元素:reset表示指针移动到第一个元素: &l ...

随机推荐

  1. 吐槽贴:百度地图 api 封装 的实用功能 &lbrack;源码下载&rsqb;

    ZMap 类 功能介绍 ZMap 是学习百度地图 api 接口,开发基本功能后整的一个脚本类,本类方法功能大多使用 prototype 原型 实现: 包含的功能有:轨迹回放,圈画区域可编辑,判断几个坐 ...

  2. magic&lowbar;quotes&lowbar;gpc、mysql&lowbar;real&lowbar;escape&lowbar;string、addslashes的区别及用法

    本篇文章,主要先重点说明magic_quotes_gpc.mysql_real_escape_string.addslashes 三个函数方法的含义.用法,并举例说明.然后阐述下三者间的区别.关系.一 ...

  3. LINQ to SQL 建立实体类

    使用LINQ to SQL时,需要首先建立用于映射数据库对象的模型,也就是实体类.在运行时,LINQ to SQL 根据LINQ表达式或查询运算符生成SQL语句,发送到数据库进行操作.数据库返回后,L ...

  4. jQuery ajax方法在Chrome浏览器下失效问题

    最近做测试时碰到一个问题,chrome下使用ajax的一些方法(如get,load等)的时候完全失效: $(function() { $("#send").click(functi ...

  5. linux线程之pthread&lowbar;join和pthread&lowbar;detach

    在任何一个时间点上,线程是可结合的(joinable)或者是分离的(detached).一个可结合的线程能够被其他线程收回其资源和杀死.在 被其他线程回收之前,它的存储器资源(例如栈)是不释放的.相反 ...

  6. Lowest Common Ancestor of a Binary Search Tree &lpar;BST&rpar;

    Given a binary search tree(BST), find the lowest common ancestor of two given nodes in the BST. Node ...

  7. Core官方DI解析&lpar;5&rpar;-ServiceProviderEngine

    最后来看看前面一直说的Engine(工作引擎),工作引擎接口是IServiceProviderEngine在ServiceProvider的构造函数中看到了根据指定的Mode创建了不同的实现类,下面先 ...

  8. 【拓扑排序】烦人的幻灯片&lpar;slides&rpar;

    1395:烦人的幻灯片(slides) 时间限制: 1000 ms         内存限制: 65536 KB提交数: 753     通过数: 416 [题目描述] 李教授将于今天下午作一次非常重 ...

  9. python 计算机发展史&comma;线程Process使用 for循环创建 2种传参方式 jion方法 &lowbar;&lowbar;main&lowbar;&lowbar;的解释

    ########################总结################## #一 操作系统的作用: 1:隐藏丑陋复杂的硬件接口,提供良好的抽象接口 2:管理.调度进程,并且将多个进程对硬 ...

  10. &lbrack;Caffe&rsqb;&colon;关于&ast;&ast;&ast; Aborted at 1479432790 &lpar;unix time&rpar; try &quot&semi;date -d &commat;1479432790&quot&semi; 错误的另一种原因

    问题:设置solver.prototxt时,lr_policy:"step",运行时出现下面问题 *** Aborted at (unix time) try "date ...