代码随想录算法训练营第10天 232.用栈实现队列、225. 用队列实现栈

用栈实现队列

力扣题目链接(opens new window)

使用栈实现队列的下列操作：

push(x) – 将一个元素放入队列的尾部。
pop() – 从队列首部移除元素。
peek() – 返回队列首部的元素。
empty() – 返回队列是否为空。

使用栈来模式队列的行为，如果仅仅用一个栈，是一定不行的，所以需要两个栈一个输入栈，一个输出栈，这里要注意输入栈和输出栈的关系。

在push数据的时候，只要数据放进输入栈就好，但在pop的时候，操作就复杂一些，输出栈如果为空，就把进栈数据全部导入进来（注意是全部导入），再从出栈弹出数据，如果输出栈不为空，则直接从出栈弹出数据就可以了。

/*** @description: 用栈实现队列* @author: 刘宇浩* @date: 2023/1/12 1:00*/
public class MyQueue {public Stack in;public Stack out;public MyQueue() {in = new Stack<>();out = new Stack<>();}public void push(int x) {in.push(x);}public int pop() {while (!in.empty()) {out.push(in.pop());}Integer res = out.pop();while (!out.empty()) {in.push(out.pop());}return res;}public int peek() {while (!in.empty()) {out.push(in.pop());}Integer res = out.pop();out.push(res);while (!out.empty()) {in.push(out.pop());}return res;}public boolean empty() {return in.empty();}
}

用队列实现栈

力扣题目链接(opens new window)

使用队列实现栈的下列操作：

• push(x) – 元素 x 入栈
• pop() – 移除栈顶元素
• top() – 获取栈顶元素
• empty() – 返回栈是否为空

一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部，此时再去弹出元素就是栈的顺序了。

/*** @description: 用队列实现栈* @author: 刘宇浩* @date: 2023/1/12 1:07*/
public class MyStack {public Deque queue;public MyStack() {queue = new ArrayDeque<>();}public void push(int x) {queue.addLast(x);}public int pop() {int size = queue.size();size--;while (size-- > 0) {queue.addLast(queue.peekFirst());queue.pollFirst();}return queue.pollFirst();}public int top() {return queue.peekLast();}public boolean empty() {return queue.isEmpty();}
}