用两个栈实现队列

题目描述

示例

代码

代码1 两个数组模拟，一个用来push，另一个用来pop

let stack1 = [] // push到这里
let stack2 = [] // 从这里pop出去，先把 stack2.push(stack1.pop()) 反着来一遍
function push(node)
{
    stack1.push(node)
}
function pop()
{
    if(stack2.length === 0){
        while(stack1.length > 0){
            stack2.push(stack1.pop())
        }
    }
    
    return stack2.pop()
}

时间复杂度O(1)

空间复杂度O(n)

代码2 利用js的shift操作

let q = []
function push(node)
{
    q.push(node)
}
function pop()
{
    return q.shift()
}

时间复杂度O(1)

空间复杂度O(n)

题目来源

JZ9 用两个栈实现队列