两个栈实现队列

题目链接

• 牛客网

题目描述

用两个栈来实现一个队列，使用n个元素来完成 n 次在队列尾部插入整数(push)和n次在队列头部删除整数(pop)的功能。 队列中的元素为int类型。保证操作合法，即保证pop操作时队列内已有元素。

数据范围：n≤1000 要求：存储n个元素的空间复杂度为O(n) ，插入与删除的时间复杂度都是O(1)

示例：

#输入：
#["PSH1","PSH2","POP","POP"]
#返回值：
#1,2
#说明：
#"PSH1":代表将1插入队列尾部
#"PSH2":代表将2插入队列尾部
#"POP“:代表删除一个元素，先进先出=>返回1
#"POP“:代表删除一个元素，先进先出=>返回2

刷题思路

这个题目只需要理解栈和队列的基础特性，即：

• 栈：先进后出，普通栈进、出栈都在栈顶完成
• 队列： 先进先出，普通队列，队尾进入、队首出栈

可用通过操作全局数组来实现栈、队列的相关操作

代码实现

/*
 * @Description: 【简单】用两个栈实现队列
 * @Version: Beta1.0
 * @Author: 微信公众号：储凡
 * @Date: 2021-04-29 22:06:51
 * @LastEditors: 微信公众号：储凡
 * @LastEditTime: 2021-04-29 22:07:22
 */

const result = []

/**
 * 模拟进队列操作
 */
function push(node) {
  // 尾部进栈
  result.push(node)
  return result
}

/**
 * 模拟出队列操作
 */
function pop() {
  // 队列 先进先出 头部出去
  return result.shift()
}

console.log(push(1), push(2))
console.log(pop(), pop())

一些建议

• 理解栈、队列的基本特性
• 熟练使用数组的api接口，例如：push、pop、unshift、shift等