栈（stack）是很简单的⼀种数据结构，先进后出的逻辑顺序，符合某些问题的特点，⽐如说函数调⽤栈。
⽤队列实现栈
只需要⼀个队列作为底层数据结构。⾸先看下栈的 API：
1
2
3
4
5
6
7
8
9
10
class MyStack {
/** 添加元素到栈顶 */
public void push(int x);
/** 删除栈顶的元素并返回 */
public int pop();
/** 返回栈顶元素 */
public int top();
/** 判断栈是否为空 */
public boolean empty();
}
先说 push API，直接将元素加⼊队列，同时记录队尾元素，因为队尾元素相当于栈顶元素，如果要 top 查看栈顶元素的话可以直接返回：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class MyStack {
Queue<Integer> q = new LinkedList<>();
int top_elem = 0;
/** 添加元素到栈顶 */
public void push(int x) {
// x 是队列的队尾，是栈的栈顶
q.offer(x);
top_elem = x;
}
/** 返回栈顶元素 */
public int top() {
return top_elem;
}
/** 删除栈顶的元素并返回 */
public int pop() {
int size = q.size();
// 留下队尾 2 个元素
while (size > 2) {
q.offer(q.poll());
size--;
}
// 记录新的队尾元素
top_elem = q.peek();
q.offer(q.poll());
// 删除之前的队尾元素
return q.poll();
}
底层数据结构是先进先出的队列，每次 pop 只能从队头取元素；但是栈是后进先出，也就是说 pop API 要从队尾取元素。
最后，API empty 就很容易实现了，只要看底层的队列是否为空即可：
1
2
3
4
/** 判断栈是否为空 */
public boolean empty() {
return q.isEmpty();
}
很明显，⽤队列实现栈的话， pop 操作时间复杂度是 O(N)，其他操作都是 O(1) 。
