栈---类似于一个桶,遵循先进后出原则
队列---类似于一个管道,遵循先进先出的原则
题目要求分析
题目要求我们用两个栈实现队列,也就是让我们用两个桶来实现一个管道的意思。
例如:我们有向栈中加入1、2、3,那栈中的情况就是「3,2,1」,这个时候如果我们我们直接取,则取得是栈顶的3;
但是如果我们向队列中加入1、2、3,那队列中的情况就是「3,2,1」,这个时候如果我们我们直接取,则取得是队列尾的1;
具体实现:
如果我们有两个栈,我们就可以这样来实现一个队列。
- 当栈B没有值得时候,我们将栈A的值全部加入栈B,然后再从栈B顶取值,这样就实现类队列。
- 当栈B里面有值得时候,直接取栈B顶部的值;例如我们刚才取出了值1,我们向栈A中又加入了值4,这个时候我们栈B中有值,我们就可以直接从栈B中取出2,而不需要先把栈A中的值加入栈B。
代码实现:
import java.util.Stack; public class Solution { Stack<Integer> stack1 = new Stack<Integer>(); Stack<Integer> stack2 = new Stack<Integer>(); public void push(int node) { stack1.push(node); } public int pop() { if(stack2.size() <= 0){ while(stack1.size() != 0){ stack2.push(stack1.pop()); } } return stack2.pop(); } }