Problem Description
- 使用队列实现栈的下列操作：
- push(x) — 元素 x 入栈
- pop() — 移除栈顶元素
- top() — 获取栈顶元素
- empty() — 返回栈是否为空
note
- 你只能使用队列的基本操作— 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
- 你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
- 你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。
Solution
1. 双向队列Deque实现
利用双端队列Deque接口的实现类LinkedList可以很简洁的完成，Deque拥有一个boolean offerFirst(E e);方法。因为底层是双向链表，prev和next指针可以很好帮你实现头尾乱♂插。
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
| class MyStack {
Deque<Integer> deque;
public MyStack() {
deque = new LinkedList<>();
}
public void push(int x) {
deque.offerFirst(x);
}
public int pop() {
return deque.remove() ;
}
public int top() {
return deque.element();
}
public boolean empty() {
return deque.isEmpty();
}
}
|
2. 双队列形成一个闭环
- 2个单向队列queue和reverseQueue；
- queue初次push时，判断是否为空，为空直接调用offer方法；
- 当queue不为空时，将所有的元素从头部出队，入队到reverseQueue。queue入队新的元素；
- 这时两个队列，queue只有新的元素在队列中，reverseQueue拥有queue刚刚出队的元素；
- 再次将reverseQueue的元素循环出队到queue，保证每次调用push方法时，该队列是空的；
- 两个单项队列变成闭环。
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
29
30
31
32
33
34
35
36
37
| class MyStack {
Queue<Integer> queue;
Queue<Integer> reverseQueue;
public MyStack() {
queue = new LinkedList<>();
reverseQueue = new LinkedList<>();
}
public void push(int x) {
if (queue.isEmpty()) {
queue.offer(x);
} else {
reverseQueue.addAll(queue);
queue.clear();
queue.offer(x);
queue.addAll(reverseQueue);
reverseQueue.clear();
}
}
public int pop() {
return queue.remove();
}
public int top() {
return queue.element();
}
public boolean empty() {
return queue.isEmpty();
}
}
|
3. 单个单向队列
其中注意：不要使用自身的forEach方法，根据队列的长度搞个循环即可。
push方法核心代码：
1
2
3
4
5
6
7
8
9
|
public void push(int x) {
singleQueue.add(x);
for (int i = 0; i < singleQueue.size() - 1; i++) {
singleQueue.add(singleQueue.poll());
}
}
|
注意是size - 1。因为最新add的那个元素不需要执行poll方法。