数据结构与算法学习笔记 (10):图解数据结构与算法-栈和队列（七）& （八）+大厂面试真题：由两个栈组成的队列...

立即学习:https://edu.csdn.net/course/play/29510/420451?utm_source=blogtoedu

栈和队列（七）&（八）由两个栈组成的队列

 

题目：编写一个类，用两个栈实现队列，支持队列的基本操作(add、poll、peek)。

 

【方法思路】

栈的特点是先进后出，而队列的特点是先进先出。

我们用两个栈，正好能把顺序反过来，即可实现队列的功能。

具体实现上是一个栈作为压入栈，在压入数据时只往这个栈中压入，记为stackPush;

另一个栈只作为弹出栈，在弹出数据时只从这个栈弹出， 记为stackPop.

因为数据压入栈的时候， 顺序是先进后出的。

那么只要把stackPush的数据再压入stackPop中， 顺序就变回来了。

例如， 将1~5依次压入stackPush,那么从stackPush的栈顶到栈底为5~1, 此时依次再将5~1倒入 stackPop,那么从stackPop的栈顶到栈底就变成了1~5。再从stackPop弹出时， 顺序就像队列一样。  

 

【两个栈组成队列常见设计错误】支撑理论步骤的两个必要点： 1.如果stackPush要往stackPop中压入数据， 那么必须一次性把stackPush中的数据全部压入。

2.如果stackPop不为空， stackPush 绝对不能向stackPop中压入数据。

违反1的情况举例:  1~5依次压入stackPush, stackPush的栈顶到栈底为5~1,从stackPush压入 stackPop时， 只将5和4压入了stackPop, stackPush 还剩下1、 2、 3没有压入。 此时如果用户想进 行弹出操作， 那么4将最先弹出， 与预想的队列顺序就不一致。

违反2的情况举例:  1~5 依次压入stackPush, stackPush将所有的数据压入了stackPop,此时从 stackPop的栈项到栈底就变成了1~5。 此时又有6-10依次压入stackPush, stackPop不为空， stackPush 不能向其中压入数据。 如果违反2压入了stackPop, 从stackPop的栈顶到栈底就变成了 6~10、 1~5。 那么此时如果用户想进行弹出操作， 6将最先弹出， 与预想的队列顺序就不一致。

 

【代码】

public class TwoStackToQueue { private Stack<Integer> stackPush; private Stack<Integer> stackPop; public TwoStackToQueue(Stack<Integer> stackPush, Stack<Integer> stackPop) { this.stackPush = stackPush; this.stackPop = stackPop; } public TwoStackToQueue() { super(); } public void add(int pushInt){ stackPush.push(pushInt); } public int poll(){ if(stackPop.empty() && stackPush.empty()){ throw new RuntimeException("队列已空！"); }else if (stackPop.empty()){ while (!stackPush.empty()){ stackPop.push(stackPush.pop()); } } return stackPop.pop(); } public int peek(){ if (stackPop.empty() && stackPush.empty()){ throw new RuntimeException("队列已空！"); }else if (stackPop.empty()){ while (!stackPush.empty()){ stackPop.push(stackPush.pop()); } } return stackPop.peek(); } public static void main(String[] args) { TwoStackToQueue twoStackToQueue = new TwoStackToQueue(new Stack<Integer>(),new Stack<Integer>()); twoStackToQueue.add(1); twoStackToQueue.add(2); twoStackToQueue.add(3); twoStackToQueue.add(4); twoStackToQueue.add(5); System.out.println(twoStackToQueue.stackPush.toString()); System.out.println(twoStackToQueue.peek()); System.out.println(twoStackToQueue.stackPush.toString()); System.out.println(twoStackToQueue.stackPop.toString()); } }