0225-用队列实现栈

题目链接

题目描述

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：

• void push(int x) 将元素 x 压入栈顶。
• int pop() 移除并返回栈顶元素。
• int top() 返回栈顶元素。
• boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

  示例

  示例1：

  输入： [“MyStack”, “push”, “push”, “top”, “pop”, “empty”] [[], [1], [2], [], [], []] 输出： [null, null, null, 2, 2, false]

  解释： MyStack myStack = new MyStack(); myStack.push(1); myStack.push(2); myStack.top(); // 返回 2

myStack.pop(); // 返回 2

myStack.empty(); // 返回 False

提示

• 1 <= x <= 9
• 最多调用100 次 push、pop、top 和 empty

• 每次调用 pop 和 top 都保证栈不为空

  思路

  思路1：双栈

  维护两个栈 que1 和 que2 ，其中 que2 是辅助队列，只有 que1 是真正储存数据的。实现如下：

• void push(int x) ，直接入队 que1 。

• int pop() ，将 que1 元素出队，然后一次入队到 que2 中，直到 que1 中只剩下一个元素，该元素就是我们要返回的元素，将该元素出队后， que1 为空，交换 que1 和 que2 即可。
• int top() 返回 que1 队尾。

• boolean empty() 如果 que1 是空的，返回 true ；否则，返回 false 。

  思路2：单栈

  在思路1中， que2 只在弹出中使用过，它是可以被优化的，方法如下：

• int pop() ，将 que1 的元素出队后接着入队，直到最后一个元素，弹出该元素即可。

其他方法不变。

题解

思路1：双栈

class MyStack {
   private:
    queue<int> que1;
    queue<int> que2;
   public:
    /** Initialize your data structure here. */
    MyStack() {
    }
    /** Push element x onto stack. */
    void push(int x) {
        que1.push(x);
    }
    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        int size = que1.size() - 1;
        while (size--) {
            que2.push(que1.front());
            que1.pop();
        }
        int ret = que1.front();
        que1.pop();
        swap(que1, que2);
        return ret;
    }
    /** Get the top element. */
    int top() {
        return que1.back();
    }
    /** Returns whether the stack is empty. */
    bool empty() {
        return que1.empty();
    }
};
/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */

思路2：单栈

class MyStack {
   private:
    queue<int> que1;
   public:
    /** Initialize your data structure here. */
    MyStack() {
    }
    /** Push element x onto stack. */
    void push(int x) {
        que1.push(x);
    }
    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        int size = que1.size() - 1;
        while (size--) {
            que1.push(que1.front());
            que1.pop();
        }
        int ret = que1.front();
        que1.pop();
        return ret;
    }
    /** Get the top element. */
    int top() {
        return que1.back();
    }
    /** Returns whether the stack is empty. */
    bool empty() {
        return que1.empty();
    }
};
/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */

复杂度分析

思路1：双栈

• 时间复杂度：除了弹出为 外，其余操作都为

• 空间复杂度：

  思路2：单栈

• 时间复杂度：除了弹出为 外，其余操作都为

• 空间复杂度：