用栈实现队列(面试常考)

超、凢脫俗 2022-10-23 09:59 127阅读 0赞

# 一、题目描述 #

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

*  void push(int x) 将元素 x 推到队列的末尾
 *  int pop() 从队列的开头移除并返回元素
 *  int peek() 返回队列开头的元素
 *  boolean empty() 如果队列为空，返回 true ；否则，返回 false

**示例：**

输入：
    ["MyQueue", "push", "push", "peek", "pop", "empty"]
    [[], [1], [2], [], [], []]
    输出：
    [null, null, null, 1, 1, false]
    
    解释：
    MyQueue myQueue = new MyQueue();
    myQueue.push(1); // queue is: [1]
    myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
    myQueue.peek(); // return 1
    myQueue.pop(); // return 1, queue is [2]
    myQueue.empty(); // return false

**提示：**

*  1 <= x <= 9
 *  最多调用 100 次 push、pop、peek 和 empty
 *  假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）

# 二、思路分析 #

首先看栈和队列的区别：

*  栈：**先进后出（后进先出）**
 *  队列：**先进先出**
 *  **push**：都是加到末尾，依次加入1、2、3
 *  **pop**：栈是删除并返回末尾元素3，队列是删除并返回开头元素1

![750f9b2d07961c6424afb28cec918537.png][]

这一顿比较后发现，用栈实现队列的难度就在于如何将栈底的元素取出。

每次取元素都是需要从栈底开始取，那这刚好就是出栈操作的逆序。

我们再用一个栈来存储逆序元素，每次取出时去这个栈里正常出栈即可：

![0d274ef813b55a25eaf4440798254aec.png][]

维持这样一个**逆序栈**：

*  正常入元素时push到stack1
 *  取元素时先检查stack2是否为空：
    
     *  stack2为空时，先将stack1中的元素逆序到stack2中，再从stack2中pop
     *  stack2不为空时，直接从stack2中pop

**peek()**：pop()实现了之后peek()的实现也就简单了：

peek()与pop()的区别就是 peek没有将值出栈。

**empty**：检查两个栈是否为空即可。

# 三、AC 代码 #

/**
     * Initialize your data structure here.
     */
    var MyQueue = function() {
        this.stack1 = [];
        this.stack2 = [];
    };
    
    /**
     * Push element x to the back of queue. 
     * @param {number} x
     * @return {void}
     */
    MyQueue.prototype.push = function(x) {
        this.stack1.push(x);
    };
    
    /**
     * Removes the element from in front of queue and returns that element.
     * @return {number}
     */
    MyQueue.prototype.pop = function() {
        if(this.stack2.length <= 0){//如果stack2为空则先将stack1中的元素放进来
            while(this.stack1.length > 0){
                //将 stack1 出栈的元素再推入 stack2，实现逆序
                this.stack2.push(this.stack1.pop());
            }
        }
        return this.stack2.pop();//出栈
    };
    
    /**
     * Get the front element.
     * @return {number}
     */
    MyQueue.prototype.peek = function() {
        if(this.stack2.length <= 0){//如果stack2为空则先将stack1中的元素放进来
            while(this.stack1.length > 0){
                //将 stack1 出栈的元素再推入 stack2，实现逆序
                this.stack2.push(this.stack1.pop());
            }
        }
        return this.stack2.length && this.stack2[this.stack2.length - 1];//返回栈顶元素
    };
    
    /**
     * Returns whether the queue is empty.
     * @return {boolean}
     */
    MyQueue.prototype.empty = function() {
        return !this.stack1.length && !this.stack2.length;
    };
    
    /**
     * Your MyQueue object will be instantiated and called as such:
     * var obj = new MyQueue()
     * obj.push(x)
     * var param_2 = obj.pop()
     * var param_3 = obj.peek()
     * var param_4 = obj.empty()
     */

# 四、总结 #

*  栈：先进后出、队列：先进先出；队列取出元素的顺序是栈的**逆序**,所以维持一个逆序栈。

[750f9b2d07961c6424afb28cec918537.png]: /images/20221023/2c3260d541e14af1ad23abd4fc443ef3.png
[0d274ef813b55a25eaf4440798254aec.png]: /images/20221023/3ad8acf1098446f9938faa9620a79bb5.png