【经典算法题】用队列实现栈

题目描述：Leetcode 0225 用队列实现栈

分析

• 本题的考点：设计。

• 使用两个队列q, w，q用于存储元素，w是缓存队列。

• 每次插入元素时，向q中插入元素；

• 删除栈顶元素时，可以先将队列中前q.size()-1个元素存储到缓存队列w中，最后将q中剩余的一个元素缓存到临时变量t中，然后删除q中最后一个元素，最后将w中的元素再次放入q中即可；

• 返回栈顶元素的操作和删除类似；

• 栈是否为空只需要看q是否为空即可。

代码

• C++

class MyStack {
public:

    queue q, w;

    
    MyStack() {

    }
    
    
    void push(int x) {
        q.push(x);
    }
    
    
    int pop() {
        while (q.size() > 1) w.push(q.front()), q.pop();
        int t = q.front(); q.pop();
        while (w.size()) q.push(w.front()), w.pop();
        return t;
    }
    
    
    int top() {
        while (q.size() > 1) w.push(q.front()), q.pop();
        int t = q.front(); q.pop();
        while (w.size()) q.push(w.front()), w.pop();
        q.push(t);
        return t;
    }
    
    
    bool empty() {
        return q.empty();
    }
};

• Java

class MyStack {

    Queue q = new linkedList<>(), w = new linkedList<>();

    
    public MyStack() {

    }
    
    
    public void push(int x) {
        q.add(x);
    }
    
    
    public int pop() {
        while (q.size() > 1) w.add(q.remove());
        int t = q.remove();
        while(w.size() != 0) q.add(w.remove());
        return t;
    }
    
    
    public int top() {
        while (q.size() > 1) w.add(q.remove());
        int t = q.remove();
        while(w.size() != 0) q.add(w.remove());
        q.add(t);
        return t;
    }
    
    
    public boolean empty() {
        return q.isEmpty();
    }
}

时空复杂度分析

• 时间复杂度：top和pop操作和栈中元素个数成正比，其余操作是 O ( 1 ) O(1) O(1)的。

• 空间复杂度： O ( n ) O(n) O(n)，n为栈中元素个数。