【HBU】3-9 堆栈模拟队列 (20分)

矫情吗；* 2022-11-21 01:17 160阅读 0赞

**题目描述**  
设已知有两个堆栈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

## 答案有参考，[参考链接][Link 1]：https://blog.csdn.net/qq\_41608020/article/details/81032310 ##

> 记容量小的栈为s1，容量大的栈为s2
> 
> 输入时
> 
> 1.  s1没满，s2为空，输入到s1中。
> 2.  s1满了，s2为空，将s1中的数据倒入s2中，再输入到s1中。
> 3.  s1满了，s2不为空，输出ERROR:Full。
> 
> 输出时
> 
> 1.  s2不是空的，直接输出s2.top()。
> 2.  s2是空的，s1不是空的，将s1中的元素倒入s2中，再输出s2.top()。
> 3.  s2是空的，s1也是空的，输出ERROR:Empty。

通过两个栈之间的来回倒腾来模拟一个队列。设容量小的栈为s1，输入数据时优先存放在s1中，输出是则将s1中的数据全部导入到s2中，此时s1中的数据就翻了个，进而实现了队列的功能。

#include <iostream>
    #include <stack>
    using namespace std;
    int main() {
        
    	stack<int> s1, s2;
    	int v1, v2;
    	cin >> v1 >> v2;
    	if(v1 > v2){
        
    		int t = v1;
    		v1 = v2;
    		v2 = t;
    	}
    	int num;
    	char c;
    	while(1){
        
    		cin >> c;
    		if(c == 'T')
    			return 0;
    		else if(c == 'A'){
        
    			cin >> num;
    			if(s1.size() == v1){
        
    				if(s2.size() == 0){
        
    					while(s1.size()){
        
    						s2.push(s1.top());
    						s1.pop();
    					}
    					s1.push(num);
    				}else{
        
    					cout << "ERROR:Full\n";
    					continue;
    				}
    			}else{
        
    				s1.push(num);
    			}
    		}
    		else if(c == 'D'){
        
    			if(s2.size() == 0){
        
    				if(s1.size() == 0){
        
    					cout << "ERROR:Empty\n";
    					continue;
    				}else{
        
    					while(s1.size()){
        
    						s2.push(s1.top());
    						s1.pop();
    					}
    					cout << s2.top() << endl;
    					s2.pop();
    				}
    			}else{
        
    				cout << s2.top() << endl;
    				s2.pop();
    			}
    		}
    	}
    }

[Link 1]: https://blog.csdn.net/qq_41608020/article/details/81032310

发表评论取消回复

表情：

评论列表（有 0 条评论，160人围观）

还没有评论，来说两句吧...

相关阅读

相关栈模拟队列的思想

栈的特点是:后进先出队列的特点是:先进先出栈模拟队列，就要求元素先进先出，可是栈的特点是后进先出，这就需要两个栈才能模拟队列(符合先进先出的特点)1.先创建两个栈(栈1:...

﹏ヽ暗。殇╰゛Y/ 2024年05月07日 17:12/ 0 赞/ 74 阅读

相关 java循环队列的模拟实现

java循环队列的模拟实现设计你的循环队列实现。循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为

淩亂°似流年/ 2024年03月17日 11:37/ 0 赞/ 52 阅读

相关【HBU】7-1 二分查找 (20分)

题目描述利用二分查找找出所给出的数在数组中的下标输入格式: 第一行输入n和m表示数组有n个数据，m表示要对m个数进行查找输出格式: 所有输出在一行完成，行

川长思鸟来/ 2022年12月30日 15:56/ 0 赞/ 258 阅读

相关【HBU】7-2 树种统计 (20分)

题目描述随着卫星成像技术的应用，自然资源研究机构可以识别每一棵树的种类。请编写程序帮助研究人员统计每种树的数量，计算每种树占总数的百分比。输入格式: 输入首先给出

ゞ浴缸里的玫瑰/ 2022年12月22日 04:56/ 0 赞/ 185 阅读

相关【HBU】7-4 数组循环左移 (20分)

题目描述本题要求实现一个对数组进行循环左移的简单函数：一个数组a中存有n（>0）个整数，在不允许使用另外数组的前提下，将每个整数循环向左移m（≥0）个位置，即将a中的数据

深藏阁楼爱情的钟/ 2022年12月22日 04:55/ 0 赞/ 164 阅读

相关【HBU】3-9 堆栈模拟队列 (20分)

题目描述设已知有两个堆栈S1和S2，请用这两个堆栈模拟出一个队列Q。所谓用堆栈模拟队列，实际上就是通过调用堆栈的下列操作函数: `int IsFull(Stack

矫情吗；*/ 2022年11月21日 01:17/ 0 赞/ 161 阅读

相关堆、栈、堆栈、队列的区别

如果你学过数据结构，就一定会遇到“堆”,"栈","堆栈","队列"，而最关键的是这些到底是什么意思？最关键的是即使你去面试，这些都还会问到，所以如果你不懂对你是损失很大的。

迷南。/ 2022年09月05日 00:04/ 0 赞/ 163 阅读

相关栈和队列的相互模拟

队列是先进先出的数据结构，栈时先进后出的数据结构，可以使用栈和队列模拟彼此。两个队列模拟栈使用C++泛型编程，队列使用STL的queue容器适配器。主要思

深藏阁楼爱情的钟/ 2022年08月01日 02:55/ 0 赞/ 180 阅读

相关使用栈来模拟队列的操作

使用A和B两个栈来模拟队列，一个为入栈一个为出栈，这样来实现队列这里我们直接使用Java类库提供的Stack来实现。首先我们定义连个栈，一个放数据，一个出数据

╰半夏微凉°/ 2022年06月16日 13:12/ 0 赞/ 167 阅读

相关 7-22 堆栈模拟队列（25 分）

设已知有两个堆栈S1和S2，请用这两个堆栈模拟出一个队列Q。所谓用堆栈模拟队列，实际上就是通过调用堆栈的下列操作函数: int IsFull(Stack S)：判

柔光的暖阳◎/ 2022年05月11日 14:58/ 0 赞/ 185 阅读