1. 题目
牛客网 面试笔试 TOP101 | LeetCode 232. 用栈实现队列
描述
用两个栈来实现一个队列，使用n个元素来完成 n 次在队列尾部插入整数(push)和n次在队列头部删除整数(pop)的功能。 队列中的元素为int类型。保证操作合法，即保证pop操作时队列内已有元素。
数据范围：n≤1000
要求：存储n个元素的空间复杂度为 O(n) ，插入与删除的时间复杂度都是 O(1)
示例1
输入：
["PSH1","PSH2","POP","POP"]
返回值：
1,2
说明：
"PSH1":代表将1插入队列尾部
"PSH2":代表将2插入队列尾部
"POP“:代表删除一个元素，先进先出=>返回1
"POP“:代表删除一个元素，先进先出=>返回2
示例2
输入：
["PSH2","POP","PSH1","POP"]
返回值：
2,1
2. 解题思路
首先我们需要明确什么时候栈，什么是队列，以及对应的特点。
本题有一个小技巧，需要特别留意：
如果文字描述的不太清楚，你可以参考视频的详细讲解。
Java版本：哔哩哔哩_bilibili
https://www.bilibili.com/cheese/play/ep1367848Golang版本：哔哩哔哩_bilibili
https://www.bilibili.com/cheese/play/ep1364846
3. 编码实现
核心代码如下：
var stack1 []int
var stack2 []int
func Push(node int) {
//1. push：直接将数据加入到stack1
stack1 = append([]int{node}, stack1...)
}
func Pop() int {
//2. pop：从stack2中取数据。如果stack2为空，则一次性将stack1中的数据加入到stack2中再从stack2取数据。
//2.1. 如果stack2为空，则将stack1的所有数据依次取出，入栈stack2
if len(stack2) <= 0 {
for len(stack1) != 0 {
tmp := stack1[0]
stack2 = append([]int{tmp}, stack2...)
stack1 = stack1[1:]
}
}
//2.2 返回栈stack2的栈顶数据
v := stack2[0]
stack2 = stack2[1:]
return v
}具体完整代码你可以参考下面视频的详细讲解。
Java版本：哔哩哔哩_bilibili
https://www.bilibili.com/cheese/play/ep1367848Golang版本：哔哩哔哩_bilibili
https://www.bilibili.com/cheese/play/ep1364846
4.小结
两个栈实现队列有一个技巧：①入队列的时候，将数据加入到stack1中；②出队列的时候，如果stack2中没有数据，则先将stack1中的所有数据加入到stack2中，之后从stack2中取数据。
《数据结构与算法》深度精讲课程正式上线啦！7 大核心算法模块全解析：
✅ 链表
✅ 二叉树
✅ 二分查找、排序
✅ 堆、栈、队列
✅ 回溯算法
✅ 哈希算法
✅ 动态规划
无论你是备战笔试面试、提升代码效率，还是突破技术瓶颈，这套课程都将为你构建扎实的算法思维底座。🔥立即加入学习打卡，与千名开发者共同进阶！
Java编码实现：哔哩哔哩_bilibili
https://www.bilibili.com/cheese/play/ss161443488Golang编码实现：哔哩哔哩_bilibili
https://www.bilibili.com/cheese/play/ss63997
对于数据结构与算法，我们总结了一套【可视化+图解】方法，依据此方法来解决相关问题，算法变得易于理解，写出来的代码可读性高也不容易出错。具体也可以参考视频详细讲解。
今日佳句：路虽远行则将至，事虽难做则必成。