共计 3312 个字符，预计需要花费 9 分钟才能阅读完成。
本文已收录至 Github《小白学算法》系列：https://github.com/vipstone/algorith
之前咱们讲过《用两个栈实现一个队列》，而明天咱们要讲的是「用队列实现栈」，它们都属于常见的面试题，而咱们明天要用多种办法来实现队列到栈的“转变”。
老规矩，先来回顾一下栈（Stack）和队列（Queue）的个性和常见办法。
栈是后进先出（LIFO）的数据结构，常见办法如下：
- push()：入栈办法，向栈顶增加元素；
- pop()：出栈办法，将栈顶的元素移除并返回元素；
- peek()：查问栈顶元素，并不会移除元素。
队列是先进先出（FIFO）的数据结构，常见办法如下：
- offer()：入队办法，向队尾增加元素；
- poll()：出队办法，从队头移除并返回元素；
- peek()：查问队头元素，并不会移除元素。
晓得了这些根底内容之后，就来看明天的问题吧。
题目形容
应用队列实现栈的下列操作：
push(x) — 元素 x 入栈
pop() — 移除栈顶元素
top() — 获取栈顶元素
empty() — 返回栈是否为空
留神:
- 你只能应用队列的基本操作 – 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是非法的；
- 你所应用的语言兴许不反对队列。你能够应用 list 或者 deque（双端队列）来模仿一个队列 , 只有是规范的队列操作即可；
- 你能够假如所有操作都是无效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。
LeetCode 225：https://leetcode-cn.com/problems/implement-stack-using-queues/
题目解析
这道题的题目很好了解： 只须要将先进先出的队列，转换为后进先出的“栈”就能够了 ，咱们能够从多个方向动手来实现此性能，比方应用两个队列插入并替换的形式，或者是一个队列插入再替换的形式，或双端队列的形式来实现此性能，具体实现办法和代码如下。
实现办法 1：两个队列实现栈
之前咱们用两个栈实现了一个队列的文章中，次要应用的是「负负得正」的思维，那么当看到此道题时，首先应该想到的是用两个队列来实现一个栈，但这里的实现思路和用栈实现队列的思路又略有不同，因为队列都是先进先出的，咱们能够把它了解为「负数」，那么也就不能用「负负得正」的思维了， 咱们这里应用两个队列来实现栈，次要的操作思路是先将元素插入一个长期队列中，而后再将另一个队列的所有元素插入到长期队列的尾部，从而实现后进先出性能的 ，具体的实现步骤如下。
步骤一
增加首个元素，入列到长期队列 queue2：
步骤二
因为正式队列中无元素，因而无需将 queue1 中的元素挪动到长期队列 queue2 的尾部，间接将长期队列和正式队列调换即可：
步骤三
增加第二个元素，先入列到长期队列 queue2：
步骤四
再将 queue1 中的元素挪动到 queue2 的尾部，如下所示：
步骤五
再将 queue1 和 queue2 进行调换：
步骤六
执行出队操作：
最终成果
从最终的效果图咱们能够看出，通过两个队列曾经实现了后进先出的个性，也就是实现了从队列到栈的转换，实现代码如下：
import java.util.Queue;
class MyStack {
Queue<Integer> queue1;
Queue<Integer> queue2;
public MyStack() {queue1 = new LinkedBlockingQueue();
queue2 = new LinkedBlockingQueue();}
/**
* 入栈
*/
public void push(int x) {
// 1. 入列长期队列二
queue2.offer(x);
// 2. 将队列一的所有元素挪动到队列二
while (!queue1.isEmpty()) {queue2.offer(queue1.poll());
}
// 3. 队列一和队列二调换
Queue<Integer> temp = queue1;
queue1 = queue2;
queue2 = temp;
}
/**
* 出栈并返回此元素
*/
public int pop() {return queue1.poll();
}
/**
* 查问栈顶元素
*/
public int top() {return queue1.peek();
}
/**
* 判断是否为空
*/
public boolean empty() {return queue1.isEmpty();
}
} 咱们在 LeetCode 中提交以上测试代码，执行后果如下：
此办法很稳，居然击败了 100% 的用户。
实现办法 2：一个队列实现栈
那咱们能够不能够用一个队列来实现栈呢？答案是必定的。
咱们只须要执行以下两个步骤就能够实现将队列转换为栈了，具体实现步骤如下：
- 将元素入列到队尾；
- 再将除队尾之外的所有元素移除并重写入列。
这样操作之后，最初进入的队尾元素反而变成了队头元素，也就实现了后进先出的性能了，如下图所示。
步骤一
元素 1 入列：
步骤二
元素 2 入列：
步骤三
将最初一个元素之前的所有元素，也就是元素 1，出列从新入列：
步骤四
执行出队操作：
最终成果
以上思路的实现代码如下：
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();
}
} 咱们把以上代码在 LeetCode 中提交，执行后果如下：
总结
本文咱们用 3 种办法实现了将队列转换为栈，其中最简略的办法是用 Java 中自带的双端队列 ArrayDeque 从队尾入并从队尾出就实现了栈，其余两个办法应用的是一般队列，通过入队之后再挪动元素到入队元素之后的办法，从而实现了栈的性能。
小伙伴们，你学会了吗？
文末福利：搜寻公众号「Java 中文社群」发送“面试”，支付最新的面试材料。
