队列实现栈的3种方法，全都击败了100%的用户！ (3)

执行出队操作：

最终效果

以上思路的实现代码如下：

import java.util.Queue; class MyStack { Queue<Integer> queue1; public MyStack() { queue1 = new LinkedBlockingQueue(); } /** * 入栈 */ public void push(int x) { // 获取原队列长度（要移动的次数） int count = queue1.size(); // 将元素放入队尾 queue1.offer(x); // 将除最后一个元素外，其他的元素重新入队 for (int i = 0; i < count; i++) { System.out.println("for"); queue1.offer(queue1.poll()); } } /** * 出栈并返回此元素 */ public int pop() { return queue1.poll(); } /** * 查询栈顶元素 */ public int top() { return queue1.peek(); } /** * 判断是否为空 */ public boolean empty() { return queue1.isEmpty(); } }

我们把以上代码在 LeetCode 中提交，执行结果如下：

此方法依旧很稳，也是同样的击败了 100% 的用户，只不过此方法在内存方面有更好的表现。

实现方法 3：双端队列实现栈

如果觉得以上方法比较难的话，最后我们还有一个更简单的实现方法，我们可以使用 Java 中的双端队列 ArrayDeque 来实现将元素可以插入队头或队尾，同样移除也是，那么这样我们就可以从队尾入再从队尾出，从而就实现了栈的功能了。

双端队列结构如下：

我们来演示一下用双端队列实现栈的具体步骤。

步骤一

元素 1 入队：

步骤二

元素 2 入队（队尾）：

步骤三

再从队尾出队：

最终效果

以上思路的实现代码如下：

import java.util.ArrayDeque; class MyStack { ArrayDeque<Integer> deque; public MyStack() { deque = new ArrayDeque<>(); } /** * 入栈 */ public void push(int x) { deque.offer(x); } /** * 出栈并返回此元素 */ public int pop() { return deque.pollLast(); } /** * 查询栈顶元素 */ public int top() { return empty() ? -1 : deque.peekLast(); } /** * 判断是否为空 */ public boolean empty() { return deque.isEmpty(); } }