本文主要是介绍leetcode刷题笔记-232. 用栈实现队列（java实现），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：
你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
进阶：
你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。
示例：
输入：
["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
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/implement-queue-using-stacks
解题思路
我们使用两个栈 s1, s2 就能实现一个队列的功能（这样放置栈可能更容易理解）：
当调用 push 让元素入队时，只要把元素压入 s1 即可，比如说 push 进 3 个元素分别是 1,2,3，那么底层结构就是这样：
那么如果这时候使用 peek 查看队头的元素怎么办呢？按道理队头元素应该是 1，但是在 s1 中 1 被压在栈底，现在就要轮到 s2 起到一个中转的作用了：当 s2 为空时，可以把 s1 的所有元素取出再添加进 s2，这时候 s2 中元素就是先进先出顺序了。
思路参考：https://labuladong.gitbook.io/algo/shu-ju-jie-gou-xi-lie/shou-ba-shou-she-ji-shu-ju-jie-gou/dui-lie-shi-xian-zhan-zhan-shi-xian-dui-lie
解题代码
class MyQueue {private Stack<Integer> s1, s2;/** Initialize your data structure here. */public MyQueue() {s1 = new Stack<>();s2 = new Stack<>();}/** Push element x to the back of queue. */public void push(int x) {s1.push(x);}/** Removes the element from in front of queue and returns that element. */public int pop() {// 先调整栈中的数据peek();return s2.pop();}/** Get the front element. */public int peek() {if (s2.isEmpty()) {while(!s1.isEmpty()) {s2.push(s1.pop());}}return s2.peek();}/** Returns whether the queue is empty. */public boolean empty() {return s2.isEmpty() && s1.isEmpty();}
}/*** Your MyQueue object will be instantiated and called as such:* MyQueue obj = new MyQueue();* obj.push(x);* int param_2 = obj.pop();* int param_3 = obj.peek();* boolean param_4 = obj.empty();*/
这篇关于leetcode刷题笔记-232. 用栈实现队列（java实现）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
