Leetcode原题
思路
我们都知道栈是”先入后出”,队列是先入先出。 而题目要求使用2个栈去实现一个队列的特性。那么怎么操作呢。
我们可以定义一个入栈,一个出栈。 添加元素时,我们放入inStack中,但是因为栈的特殊先入后出。比如 1 2 3.入栈以后变为 3 2 1 。这个时候是 反向的,而队列应该是 1 2 3才对。 所以我们在出栈的时候操作。判断outStatck是否有值,若没值,则先将inStack的值出栈添加到outStatck。此时 outStatck内元素则是正向的。
class MyQueue { private static Stack<Integer> inStack; private static Stack<Integer> outStack; public MyQueue() { inStack = new Stack(); outStack= new Stack(); } public void push(int x) { inStack.push(x); } public int pop() { if(outStack.isEmpty()){ in2out(); } return outStack.pop(); } public int peek() { if(outStack.isEmpty()){ in2out(); } return outStack.peek(); } public boolean empty() { return inStack.isEmpty() && outStack.isEmpty(); } public void in2out(){ while (!inStack.isEmpty()){ outStack.push(inStack.pop()); } } }
有兴趣的老爷,还可以关注我的公众号【一起收破烂】,回复【006】获取 最新java面试资料以及简历模型120套哦~