LeetCode 用队列实现栈

使用队列实现栈的下列操作：

1、push(x) -- 元素 x 入栈

2、pop() -- 移除栈顶元素

3、top() -- 获取栈顶元素

4、empty() -- 返回栈是否为空

注意:

1、你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。

2、你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

3、你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。

题解1(两个队列，压入O(1)， 弹出 O(n))

维护一个队列 q2，这个队列用作临时存储 q1 中出队的元素。q2 中最后入队的元素将作为新的栈顶元素。接着将 q1 中最后剩下的元素出队。我们通过把 q1 和 q2 互相交换的方式来避免把 q2 中的元素往 q1 中拷贝。

public class MyStack {

    private Queue<Integer> q1;
    private Queue<Integer> q2;
    private int top;

    public MyStack() {
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();
    }

    public void push(int x) {
        q1.add(x);
        top = x;
    }

    public int pop() {
        while (q1.size() > 1) {
            top = q1.remove();
            q2.add(top);
        }
        int popValue = q1.remove();
        Queue<Integer> temp = q1;
        q1 = q2;
        q2 = temp;
        return popValue;
    }

    public int top() {
        return top;
    }

    public boolean empty() {
        return q1.isEmpty();
    }
}

执行用时 :0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗 :37 MB, 在所有 Java 提交中击败了(木有看到)的用户

题解2(两个队列，压入O(n)， 弹出 O(1))

让每一个新元素从 q2 入队，同时把这个元素作为栈顶元素保存。当 q1 非空（也就是栈非空），我们让 q1 中所有的元素全部出队，再将出队的元素从 q2 入队。通过这样的方式，新元素（栈中的栈顶元素）将会在 q2 的前端。我们通过将 q1， q2 互相交换的方式来避免把 q2 中的元素往 q1 中拷贝。

public class MyStack {

    private Queue<Integer> q1;
    private Queue<Integer> q2;
    private int top;

    public MyStack() {
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();
    }

    public void push(int x) {
        q2.add(x);
        top = x;
        while (!q1.isEmpty()) {
            q2.add(q1.remove());
        }
        Queue<Integer> temp = q1;
        q1 = q2;
        q2 = temp;
    }

    public int pop() {
        int temp = q1.remove();
        while (!q1.isEmpty()) {
            top = q1.peek();
        }
        return temp;
    }

    public int top() {
        return top;
    }

    public boolean empty() {
        return q1.isEmpty();
    }
}

超时了！

题解3(一个队列， 压入O(n)， 弹出O(1))

每当入队一个新元素的时候，我们可以把队列的顺序反转过来。

public class MyStack {

    private Queue<Integer> q1;

    public MyStack() {
        q1 = new LinkedList<>();
    }

    public void push(int x) {
        q1.add(x);
        int len = q1.size();
        while (len > 1) {
            q1.add(q1.remove());
            len--;
        }
    }

    public int pop() {
        return q1.remove();
    }

    public int top() {
        return q1.peek();
    }

    public boolean empty() {
        return q1.isEmpty();
    }
}