剑指Offer 9. 用两个栈实现队列

题目

用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。

解答1[Java]:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.Stack;

public class Solution {
Stack<Integer> in = new Stack<Integer>();
Stack<Integer> out = new Stack<Integer>();

public void push(int node) {
in.push(node);
}

public int pop() {
if (out.isEmpty())
while (!in.isEmpty())
out.push(in.pop());

if (out.isEmpty())
System.out.println("queue is empty");

return out.pop();
}
}

思路

push 的时候,直接 push 到 in 中。

pop 的时候,

①如果 out 为空,检查 in,如果 in 也为空,说明整个 queue 为空。如果 in 不为空,把 in 中的所有元素 push 到 out 中。

②如果 out 不为空,那么直接 pop。