剑指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。