Skip to content

Files

Latest commit

 

History

History
174 lines (134 loc) · 5.12 KB

05.implement-queue-using-stacks.md

File metadata and controls

174 lines (134 loc) · 5.12 KB

232.用栈实现队列

https://leetcode-cn.com/problems/implement-queue-using-stacks/

题目描述

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

push(x) -- 将一个元素放入队列的尾部。
pop() -- 从队列首部移除元素。
peek() -- 返回队列首部的元素。
empty() -- 返回队列是否为空。
示例:

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);
queue.peek();  // 返回 1
queue.pop();   // 返回 1
queue.empty(); // 返回 false
说明:

你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。


来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/implement-queue-using-stacks
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法 1

思路

由于队列是 FIFI (先进先出)，而栈是 FILO (先进后出)，如果要用栈来模拟队列，那么每次往队列尾端增加元素的时候，这个元素需要放在栈底，因为它是最后才会出列。

方法之一是，每次往队列尾端 push 一个新元素时，我们都先把栈中的元素尽数清空，然后把新元素入栈，再把刚刚清出来的元素放回栈中，所以还需要一个辅助栈来暂存清出来的元素。

复杂度

  • 时间复杂度：入列操作是 O ( n ) ，每次入列时，除新增元素外，每个元素都需要分别出栈入栈 2 次 (从模拟队列的栈中弹出，压入辅助栈，再从辅助栈弹出，压入队列模拟栈)。压入、弹出操作的时间复杂度都是 O ( 1 ) ，所以总的时间复杂度差不多是 O ( 4 n ) ，忽略掉常数，最后得到 O ( n ) 。出列操作是 O ( 1 ) 。
  • 空间复杂度：$O(n)$，n 是队列的大小，需要一个大小为 n 的栈来模拟队列，还需要一个大小为 n 的辅助空间，但总的空间复杂度还是 O ( n ) 。

代码

JavaScript Code

class MyQueue {
    constructor() {
        this.stack = [];
    }

    push(x) {
        const helper = [];
        while (!this.empty()) {
            helper.push(this.stack.pop());
        }
        this.stack.push(x);
        while (helper.length) {
            this.stack.push(helper.pop());
        }
    }

    peek() {
        return this.stack[this.stack.length - 1];
    }

    pop() {
        return this.stack.pop();
    }

    empty() {
        return this.stack.length === 0;
    }
}

方法 2

思路

方法 1 是在元素入列的时候，就考虑好了它出列的顺序，但我们还可以在元素需要出列的时候再来考虑这个问题。这样的话：

  1. 入列时直接 push 到模拟栈中；
  2. 出列时，由于先入列的元素在栈底，需要先把其他元素弹出，依次压入辅助栈；
  3. 栈底元素弹出，出列；
  4. 刚才出栈的其他元素依次从辅助栈弹出，重新压入模拟栈。

再仔细想想的话：

  • 第 2 步中，辅助栈中的元素出栈顺序刚好就是队列的出列顺序；
  • 所以到第 4 步的时候，我们根本没必要把元素再从辅助栈转移到模拟栈；
  • 下一次 pop 操作时，直接从辅助栈弹出元素就可以了；
  • 如果辅助栈中没有元素了，我们再重复第 2 步。

这样的话，我们的队列元素其实是用了两个栈来储存，所以在判断队列是否为空的时候，两个栈都要考虑进去。

复杂度

  • 时间复杂度：入列是 O ( 1 ) ，出列最差的情况就是每个元素都要从模拟栈中弹出，压入辅助栈，再从辅助栈中弹出，所以是 O ( n ) 。
  • 空间复杂度：$O(n)$，n 为队列大小。

代码

JavaScript Code

class MyQueue {
    constructor() {
        this.stack = new MyStack();
        this.helper = new MyStack();
    }

    push(x) {
        this.stack.push(x);
    }

    peek() {
        if (this.helper.empty()) {
            while (!this.stack.empty()) {
                this.helper.push(this.stack.pop());
            }
        }
        return this.helper.peek();
    }

    pop() {
        if (this.helper.empty()) {
            while (!this.stack.empty()) {
                this.helper.push(this.stack.pop());
            }
        }
        return this.helper.pop();
    }

    empty() {
        return this.stack.empty() && this.helper.empty();
    }
}

class MyStack {
    constructor() {
        this.stack = [];
    }
    push(x) {
        this.stack.push(x);
    }
    pop() {
        return this.stack.pop();
    }
    peek() {
        return this.stack[this.stack.length - 1];
    }
    empty() {
        return this.stack.length === 0;
    }
}