LeetCode.232. 用栈实现队列

题目

232. 用栈实现队列

分析

先了解一下栈和队列的特点：

• 栈：先进后出
• 队列：先进先出

想用栈实现队列的特点，就需要使用两个栈。因为两个栈就可以将列表倒序。
假设第一个栈 s1 = [1,2,3]，第二个栈 s2 = [] 。若循环执行 s1元素出栈并且添加到栈 s2直到栈 s1为空，则s1 = []，s2 = [3,2,1]，即栈s2元素为栈s1元素倒序。

最终方法：

1. 加入元素的时候，只往栈s1里面加入。
2. 弹出元素的时候，先弹出栈s2里面的元素，如果s2为空，则把s1里面的元素放入s2，然后弹出s2的元素。
3. 判断是否为空，s1和s2同时为空，才为空

代码

class MyQueue {Stack<Integer> s1;Stack<Integer> s2;public MyQueue() {s1 = new Stack<>();s2 = new Stack<>();}public void push(int x) {s1.push(x);}public int pop() {if(!s2.isEmpty()) return s2.pop();if(!s1.isEmpty()) {while(!s1.isEmpty()) {s2.push(s1.pop());}return s2.pop();}return -1;}public int peek() {if(!s2.isEmpty()) return s2.peek();if(!s1.isEmpty()) {while(!s1.isEmpty()) {s2.push(s1.pop());}return s2.peek();}return -1;}public boolean empty() {return s2.isEmpty() && s1.isEmpty();}
}/*** Your MyQueue object will be instantiated and called as such:* MyQueue obj = new MyQueue();* obj.push(x);* int param_2 = obj.pop();* int param_3 = obj.peek();* boolean param_4 = obj.empty();*/