题目
用栈来实现队列
思路1
入队直接入，出队用两个栈来回倒腾。
static class StackToQueue{Stack<Integer> stack = new Stack<>();Stack<Integer> tmpStack = new Stack<>(); //临时栈public StackToQueue(){}//入队 直接入public void enqueue(Integer val){stack.push(val);}//出队public Integer dequeue(){if (stack.isEmpty()) return null;while (!stack.isEmpty()){tmpStack.push(stack.pop());}Integer pop = tmpStack.pop();while (!tmpStack.isEmpty()){stack.push(tmpStack.pop());}return pop;}
}
思路2
入队来回倒腾，出队直接出。
static class StackToQueue2{Stack<Integer> stack = new Stack<>();Stack<Integer> tmpStack = new Stack<>(); //临时栈public StackToQueue2(){}//入队 两个栈倒腾public void enqueue(Integer val){//新元素进来时，把stack里面的元素倒腾到tmp里去while (!stack.isEmpty()){tmpStack.push(stack.pop());}stack.push(val);while (!tmpStack.isEmpty()){stack.push(tmpStack.pop());}}//出队public Integer dequeue(){if (stack.isEmpty()) return null;return stack.pop();}
}
思路3
倒腾到tmpStack后，不用再倒腾回去了；当tmpStack不为空的时候，直接从tmpStack出队。
static class StackToQueue3{Stack<Integer> stack = new Stack<>();Stack<Integer> tmpStack = new Stack<>(); //临时栈public StackToQueue3(){}//入队 直接入public void enqueue(Integer val){stack.push(val);}//出队 优化一下public Integer dequeue(){if (stack.isEmpty() && tmpStack.isEmpty()) return -1;int r;if (!tmpStack.isEmpty()){r = tmpStack.pop();} else {while (!stack.isEmpty()){tmpStack.push(stack.pop());}r = tmpStack.pop();}return r;}
}
