本文内容来自于代码随想录
栈
用栈实现队列
两个栈实现队列。思路：两个栈分别表示入栈和出栈。
- 入队：直接入栈
- 出队：
a. 出栈为空，先把入栈中的元素全部放到出栈中（相当于反过来，这样在出栈的时候先进的元素就变成先出了），然后弹出栈顶
（2）出栈不为空，那么栈顶就是要出队的元素，直接弹出栈顶
说明：当出栈入栈都有元素的时候，出栈中的元素一定是先入队的，要弹栈优先弹出栈中的元素。出栈空了，再把入栈的元素放到出栈中，再弹栈。
/**
两个栈分别表示入栈和出栈
1. 入队：直接入栈
2. 出队：
（1）出栈为空，先把入栈中的元素全部放到出栈中（相当于反过来，这样在出栈的时候先进的元素就变成先出了），然后弹出栈顶
（2）出栈不为空，那么栈顶就是要出队的元素，直接弹出栈顶
说明：当出栈入栈都有元素的时候，出栈中的元素一定是先入队的，要弹栈优先弹出栈中的元素。出栈空了，再把入栈的元素放到出栈中，再弹栈
*/
class MyQueue {
Stack<Integer> in;
Stack<Integer> out;
public MyQueue() {
in = new Stack<>();
out = new Stack<>();
}
public void push(int x) {
in.push(x);
}
public int pop() {
if (out.empty()) {
inToOut();
}
return out.pop();
}
public int peek() {
if (out.empty()) {
inToOut();
}
return out.peek();
}
public boolean empty() {
return in.empty() && out.empty();
}
public void inToOut() {
// 把入栈中的元素全部放到出栈中
while (!in.empty()) {
int x = in.pop();
out.push(x);
}
}
}
/**
* 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();
*/
队列
用队列实现栈
两个队列实现栈。用栈模拟队列相对就容易一点，用两个队列。区别在于：另外一个队列只是用来备份数据。在弹栈的时候
- 先将 q1 中的数据出队到只剩一个，保存在 q2 中
- 将 q1 中最后一个数据出队。最后一个数据就是栈顶
- 将 q2 中的数据再出队，保存到 q1 中
class MyStack {
Queue<Integer> q1;
Queue<Integer> q2;
public MyStack() {
q1 = new LinkedList<>();
q2 = new LinkedList<>();
}
public void push(int x) {
q1.offer(x);
}
public int pop() {
oneToTwo();
int x = q1.poll();
TwoToOne();
return x;
}
public int top() {
oneToTwo();
int x = q1.poll();
q2.offer(x);
TwoToOne();
return x;
}
public boolean empty() {
return q1.isEmpty();
}
public void oneToTwo() {
while (q1.size() > 1) {
int x = q1.poll();
q2.offer(x);
}
}
public void TwoToOne() {
while (!q2.isEmpty()) {
int x = q2.poll();
q1.offer(x);
}
}
}
/**
* Your MyStack object will be instantiated and called as such:
* MyStack obj = new MyStack();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.top();
* boolean param_4 = obj.empty();
*/
![[<span style='color:red;'>Leetcode</span>]用<span style='color:red;'>栈</span>实现<span style='color:red;'>队列</span>](https://img-blog.csdnimg.cn/direct/52fabee278f54153a9d72aa18e2c4192.png)
