题目
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（
push、top、pop和empty）。实现
MyStack类：
void push(int x)将元素 x 压入栈顶。int pop()移除并返回栈顶元素。int top()返回栈顶元素。boolean empty()如果栈是空的，返回true；否则，返回false。注意：
- 你只能使用队列的基本操作 —— 也就是
push to back、peek/pop from front、size和is empty这些操作。- 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
解题思路一
- 队列是先进先出而栈是先进后出，所以需要在队列添加数据时对队列进行倒置；
代码展示
class MyStack { Queue<Integer> queue1 = null; Queue<Integer> queue2 = null; public MyStack() { queue1 = new LinkedList<>(); queue2 = new LinkedList<>(); } public void push(int x) { queue2.offer(x); while (!queue1.isEmpty()){ queue2.offer(queue1.poll()); } queue1 = queue2; queue2 = new LinkedList<>(); } public int pop() { return queue1.poll(); } public int top() { return queue1.peek(); } public boolean empty() { return queue1.isEmpty(); } }
解题思路二
- 利用ArrayDeque双向队列，可以利用自带的读取和删除末尾的值的方法实现队列的先进后出。
代码展示
class MyStack { ArrayDeque<Integer> queue = null; public MyStack() { queue = new ArrayDeque<>(); } public void push(int x) { queue.addLast(x); } public int pop() { return queue.pollLast(); } public int top() { return queue.peekLast(); } public boolean empty() { return queue.isEmpty(); } }
