文章目录
- 1.用队列实现栈
- 2.用栈实现队列
1.用队列实现栈
这个类使用两个队列来模拟栈的行为，其中一个队列用于主要操作（queue1），另一个队列作为辅助（queue2）。通过这种方式，我们可以确保栈的后进先出（LIFO）特性。
java">class MyStack {// 用于存储元素的主要队列private Queue<Integer> queue1;// 用于辅助操作的队列private Queue<Integer> queue2;// 构造函数，初始化两个队列public MyStack() {queue1 = new LinkedList<>();queue2 = new LinkedList<>();}// 将元素压入栈顶public void push(int x) {// 将新元素添加到辅助队列 queue2 中queue2.offer(x);// 将 queue1 中的所有元素转移到 queue2 中while (!queue1.isEmpty()) {queue2.offer(queue1.poll());}// 交换 queue1 和 queue2 的引用，使得 queue1 总是包含所有元素Queue<Integer> temp = queue1;queue1 = queue2;queue2 = temp;}// 移除并返回栈顶元素public int pop() {// 从 queue1 中移除并返回顶部元素return queue1.poll();}// 返回栈顶元素但不移除public int top() {// 返回 queue1 的第一个元素，即栈顶元素return queue1.peek();}// 检查栈是否为空public boolean empty() {// 栈为空当且仅当 queue1 为空return queue1.isEmpty();}
}
代码解释
- 构造函数 (MyStack): 初始化两个队列 queue1 和 queue2。这两个队列将被用来模拟栈的行为。
- push 方法:
新元素首先被添加到 queue2 中。
然后，queue1 中的所有元素被逐个移动到 queue2 中。
最后，交换 queue1 和 queue2 的引用。这样做的目的是确保 queue1 总是包含所有的元素，并且新加入的元素总是在 queue1 的前端，从而模拟了栈的 LIFO 行为。 - pop 方法:
直接从 queue1 中移除并返回队头元素。由于 queue1 中的元素顺序已经被调整，队头元素就是栈顶元素。 - top 方法:
返回 queue1 的第一个元素，但不移除它。这是当前栈顶的元素。 - empty 方法:
判断栈是否为空，只需要检查 queue1 是否为空即可，因为 queue1 始终保存着所有元素。
这种设计利用了队列的先进先出（FIFO）特性来模拟栈的后进先出（LIFO）行为。通过在每次插入时将所有元素转移到另一个队列中，可以保证新插入的元素始终位于队列的前端，从而实现了栈的功能。
2.用栈实现队列
这个类使用两个栈来模拟队列的行为，其中一个栈用于入队操作（inStack），另一个栈用于出队操作（outStack）。通过这种方式，我们可以确保队列的先进先出（FIFO）特性。
java">class MyQueue {// 用于处理入队操作的栈private Stack<Integer> inStack;// 用于处理出队操作的栈private Stack<Integer> outStack;// 构造函数，初始化两个栈public MyQueue() {inStack = new Stack<>();outStack = new Stack<>();}// 将元素添加到队尾public void push(int x) {// 元素直接加入到 inStack 中inStack.push(x);}// 移除并返回队头元素public int pop() {// 如果 outStack 为空，则将 inStack 的所有元素转移到 outStack 中if (outStack.isEmpty()) {while (!inStack.isEmpty()) {outStack.push(inStack.pop());}}// 从 outStack 弹出并返回顶部元素return outStack.pop();}// 返回队头元素但不移除public int peek() {// 如果 outStack 为空，则将 inStack 的所有元素转移到 outStack 中if (outStack.isEmpty()) {while (!inStack.isEmpty()) {outStack.push(inStack.pop());}}// 返回 outStack 的顶部元素，但不移除return outStack.peek();}// 检查队列是否为空public boolean empty() {// 队列为空当且仅当 inStack 和 outStack 都为空return inStack.isEmpty() && outStack.isEmpty();}
}
代码解释
- 构造函数 (MyQueue): 初始化两个栈，一个用于入队操作，另一个用于出队操作。
- push 方法: 直接将新元素压入 inStack 中。这是因为在入队时，我们不需要关心队列的顺序，只需简单地把元素放入栈中即可。
- pop 方法: 当需要出队时，如果 outStack 为空，则将 inStack 中的所有元素转移到 outStack 中。这样做的目的是反转这些元素的顺序，以满足队列的FIFO特性。然后，从 outStack 中弹出顶部元素作为结果。
- peek 方法: 与 pop 方法类似，但如果 outStack 为空，则同样会进行元素转移。不过，peek 只是查看而不移除 outStack 的顶部元素。
- empty 方法: 判断队列是否为空，即两个栈都必须为空时才认为队列为空。
这种设计利用了栈的后进先出（LIFO）特性来实现队列的FIFO行为。通过在需要时将 inStack 中的元素移动到 outStack 中，可以有效地维持正确的出队顺序。
