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

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

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

分析

• 本题的考点：设计。

• 可以使用两个栈stk1、stk2实现队列，stk1用于存储元素，stk2是缓存栈。

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

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

• 返回队首元素的 *** 作和删除类似，只不过不需要删除stk1中的最后一个元素了；

• 队列是否为空只需要看stk1是否为空即可。

• 对上述过程的优化：每次pop *** 作，将stk1中的元素转移到stk2中之后，其实没有必要再将stk2中的元素转移到stk1中了。之后的 *** 作只要stk2不空，返回stk2的栈顶元素即可；如果stk2为空的话，怎么办返回栈顶元素？我们可以使用一个变量front记录第一个插入stk1的元素，如果stk2为空，直接返回front即可。这个优化就对应题目中的进阶。

• 用C++实现未优化的版本，用Java实现优化后的版本。

代码

• C++

class MyQueue {
public:
    stack stk1, stk2;

    
    MyQueue() {

    }

    
    void push(int x) {
        stk1.push(x);
    }

    
    int pop() {
        while (stk1.size() > 1) stk2.push(stk1.top()), stk1.pop();
        int t = stk1.top();
        stk1.pop();
        while (stk2.size()) stk1.push(stk2.top()), stk2.pop();
        return t;
    }

    
    int peek() {
        while (stk1.size() > 1) stk2.push(stk1.top()), stk1.pop();
        int t = stk1.top();
        while (stk2.size()) stk1.push(stk2.top()), stk2.pop();
        return t;
    }

    
    bool empty() {
        return stk1.empty();
    }
};

• Java

class MyQueue {

    private Deque stk1 = new ArrayDeque<>(), stk2 = new ArrayDeque<>();
    int front;

    public MyQueue() {

    }

    public void push(int x) {
        if (stk1.isEmpty()) front = x;
        stk1.push(x);
    }

    public int pop() {  // 优化之后不需要再将stk2中的元素转移到stk1中了
        if (!stk2.isEmpty()) return stk2.pop();

        while (stk1.size() > 1) stk2.push(stk1.pop());
        return stk1.pop();
    }

    public int peek() {
        if (!stk2.isEmpty()) return stk2.peek();  // stk2非空，返回stk2栈顶元素
        return front;  // stk2空，返回stk1中栈底的元素front
    }

    public boolean empty() {
        return stk1.isEmpty() && stk2.isEmpty();
    }
}

时空复杂度分析

• 时间复杂度：top和pop *** 作和栈中元素个数成正比，其余 *** 作是 O ( 1 ) O(1) O(1)的。优化后所有 *** 作均摊时间复杂度都是 O ( 1 ) O(1) O(1)的。

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