做金融服务网站赚钱,黑马程序员怎么样,共享的网站备案,如何自己做众筹网站【刷题-PTA】堆栈模拟队列(代码动态图解) 文章目录 【刷题-PTA】堆栈模拟队列(代码动态图解)题目输入格式:输出格式:输入样例:输出样例: 分析题目区分两栈解题思路伪代码动图演示代码测试 题目 题目描述 : 设已知有两个堆栈S1和S2#xff0c;请用这两个堆栈模拟出一个队列Q。 …【刷题-PTA】堆栈模拟队列(代码动态图解) 文章目录 【刷题-PTA】堆栈模拟队列(代码动态图解)题目输入格式:输出格式:输入样例:输出样例: 分析题目区分两栈解题思路伪代码动图演示代码测试 题目 题目描述 : 设已知有两个堆栈S1和S2请用这两个堆栈模拟出一个队列Q。 所谓用堆栈模拟队列实际上就是通过调用堆栈的下列操作函数: int IsFull(Stack S)判断堆栈S是否已满返回1或0int IsEmpty (Stack S )判断堆栈S是否为空返回1或0void Push(Stack S, ElementType item )将元素item压入堆栈SElementType 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分析题目
题目要求我们通过 栈数据 结构来模拟实现 队列 , 我们首先可以从两种数据结构的特点进行分析,然后找到解题的切入点.栈数据结构的特点是先进后出(FILO) , 队列数据结构的特点是先进先出(FIFO) , 现在要实现 用栈模拟队列的 增删(CR) .如果我们使用一个栈来实现队列是无法完成要求的,因为二者的结构特点完全不同,但是如果我们把栈的数量增加,也就是使用两个栈来模拟,一个负责出队的栈s1,另一个负责入队的栈s2,两个栈通过互相倒数据 ,来模拟出队和入队的操作.具体实现的时候,我们要时刻保证 负责出队的栈s1 不为空的情况下,栈帧位置的元素(即栈顶元素)始终是最先插入的元素(也就是可以出队的元素) , 负责入队的栈 s2 不为空的情况下, 栈帧位置的元素(即栈顶元素始)终是最后插入的元素(也就是刚入队的元素) -- **简单总结就是 : 负责出队的 s1 栈顶只能存放队头的元素, 负责入队的 s2 栈顶只能存放队尾的元素 , 具体怎么让这两个栈始终维持这样的状态就需要两个栈相辅相成 ** 区分两栈
我们需要考虑两种情况
如果两个栈的容量相同,那么哪个栈负责出队,哪个栈负责入队,就不用区分了,可以任选一个作为出队剩下的就作为入队。如果两个栈的容量不相同, 那么只能容量小的栈负责入队,容量大的负责出队。 问 :为什么当两个栈的容量不相同时,必须让容量小的负责入队,容量大的负责出队呢 ? 答 : 如果一个栈的容量小于另一个栈将容量小的栈负责入队容量大的栈负责出队在特定情况下可能会导致无法完全倒出元素的问题。这是因为当负责入队的栈装满后向负责出队的栈(必须为空)中倒元素时负责出队的栈由于容量更小则无法容纳负责入队的栈中所有的元素从而导致负责出队的栈的栈顶元素一定不是应该出队的元素(两栈中现存的所有元素中最先进来). 所以通常情况下该元素依旧在负责入队的栈中,那么当你进行出队操作的时候,就会出队错误。所以通常情况下,队列的实现要求队头和队尾的栈具有相同的容量以确保操作的一致性。但是如果题目指定了两个栈的容量不同那么此时我们就需要特别处理以避免出现上述问题。 解题思路
封装了三个方法,键盘输入,如果输入A 表示 入队 Push , D 表示 出队 Pop ,T 表示 操作结束.
那么我们就应该写一个输入的循环,如果输入 A 就进行入队操作, 输入D就进行出队操作, 输入T就结束操作 入队操作 : s2 没有满 只要s2 没有满就往s2中添加元素 s2满了 如果s2满了且s1为空,就把s2中所有的元素全部倒给s1 如果s2满了且s1不为空,那么插入失败 ,打印 ERROR:Full 出队操作 : s1不为空 只要s1不为空就出队s1为空 s1为空就出队失败,打印 ERROR:Empty 结束操作 : 直接 break 伪代码
我们在真正上手去写具体的代码之前可以事先按照解题的流程写出伪代码,写完之后,我们再按照伪代码走一遍,看看是否符合解题的逻辑,这个时候就相当于是在把正确答案的框架先体现测试出来.
(动态演示图太大,不能传过来,如果需要动动态演示图,可以评论区冒泡,我发你.)
动图演示
输入样例:
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代码
import java.util.Scanner;
import java.util.Stack;public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);// 辅助栈1, 用来入队StackInteger s1 new Stack();// 辅助栈2, 用来出队StackInteger s2 new Stack();// 栈1的容量int N1 scanner.nextInt();// 栈2的容量int r2 scanner.nextInt();while (scanner.hasNextLine()) {String opr scanner.next();if (opr.equals(A)) {int val scanner.nextInt();if (s2.size() r2) {Push(s2, val);} else{if (s1.isEmpty()) {// s2满了但s1是空的那么就把s2的全部都移动到s1中去while (!s2.empty()) {Push(s1, s2.pop());}Push(s2, val);} else {System.out.println(ERROR:Full);}}} else if (opr.equals(D)) {if (!s1.isEmpty()) {int front Pop(s1);System.out.println(front);} else if (!s2.isEmpty()) {// 如果s1为空但s2不为空可以从s2中pop一个元素int front Pop(s2);System.out.println(front);} else {System.out.println(ERROR:Empty);}} else if (opr.equals(T)) {break;}}}/*** 判断堆栈S是否已满返回1或0* param s 栈* return 返回 1 表示满,返回 0 表示没有满*/public static int IsFull(StackInteger s,int r){if(s.size() r){return 1;}return 0;}/*** 判断堆栈S是否为空返回1或0* param s 栈* return 返回 1 表示空,返回 0 表示不为空*/public static int IsEmpty (StackInteger s ){if(s.empty()){return 1;}return 0;}/*** 将元素item压入堆栈S* param s 栈* param value 准备压入的数据*/public static void Push(StackInteger s, int value ){s.push(value);}/*** 删除并返回S的栈顶元素。* param s 栈* return 返回的栈顶元素*/public static int Pop(StackInteger s ){return s.pop();}
} 测试
