刷leetcode-用两个栈实现队列 | 刷题打卡

一、题目描述：

原题地址

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

提示：

1 <= values <= 10000 最多会对 appendTail、deleteHead 进行 10000 次调用

示例 1：

输入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出：[null,null,3,-1]

示例 2：

输入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]

二、思路分析：

• js没有队列和栈，但是可以用数组模拟

• 栈的话，先进后出，就只使用数组的push和pop

• 队列的话，先进先出，就只使用数组的push和shift

• 这边用两个栈模拟队列

• 进队的话，就去进栈

• 出队的话

  • 若出栈有元素的话，直接扔出顶上那个
  • 若出栈没元素的话，将进栈的的元素一个个扔进来，然后在扔出顶上那个。要是这样还没元素就说明真的没元素了，返回-1

• 出栈说白了就是维护待删除的元素

时间复杂度：对于插入和删除操作，时间复杂度均为 O(1)。插入不多说，对于删除操作，虽然看起来是 O(n) 的时间复杂度，但是仔细考虑下每个元素只会「至多被插入和弹出 stack2 一次」，因此均摊下来每个元素被删除的时间复杂度仍为 O(1)。

空间复杂度：O(n)。需要使用两个栈存储已有的元素

三、AC 代码：

var CQueue = function() {
    this.inStack = []
    this.outStack = []
};

/** 
 * @param {number} value
 * @return {void}
 */
CQueue.prototype.appendTail = function(value) {
     this.inStack.push(value)
};

/**
 * @return {number}
 */
CQueue.prototype.deleteHead = function() {
    // 出栈里没元素的话，将进栈的元素扔进来
    if(!this.outStack.length){
        for(let i=0;i<this.inStack.length;i++){
            this.outStack.push(this.inStack.pop())
            i--
        }
    }
    // 还是没元素的话，表示就是没元素了，-1
    if(!this.outStack.length){
        return -1
    }
    // 有元素的话，扔出第一个
    return this.outStack.pop()
};

四、总结：

• 栈的特点：先进后出
• 队列的特点：先进先出
• 可用栈的特点，制作特定功能的栈，比如维护待删除的元素