请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、pop 和 empty)。java
时间: 2024-09-14 12:06:19 浏览: 46
循环队列的出队-栈和队列学习课件
要使用两个队列实现一个后入先出(LIFO)的栈,我们需要维护两个队列,我们称它们为`queue1`和`queue2`。`queue1`用于存储栈中的所有元素,而`queue2`则用于在执行`push`操作时暂存元素,以便我们能够将新加入的元素放置到栈顶。
以下是具体实现步骤:
1. 初始化两个队列:`queue1`和`queue2`。
2. `push`操作:当执行`push`操作时,将元素加入到`queue2`中,然后将`queue1`中的所有元素依次加入到`queue2`中,最后交换`queue1`和`queue2`。这样,最新加入的元素就位于`queue1`的前端,相当于栈顶。
3. `pop`操作:当执行`pop`操作时,将`queue1`中的所有元素(除了最后一个元素)依次加入到`queue2`中,然后返回并移除`queue1`的最后一个元素(即栈顶元素)。之后交换`queue1`和`queue2`,以便于下一个`push`或`pop`操作。
4. `top`操作:`top`操作与`pop`操作类似,但是我们不需要移除最后一个元素,只需要返回它即可。
5. `empty`操作:检查`queue1`是否为空,如果为空,则栈为空。
现在让我们用Java代码表示上述逻辑:
```java
import java.util.LinkedList;
import java.util.Queue;
class MyStack {
private Queue<Integer> queue1;
private Queue<Integer> queue2;
public MyStack() {
queue1 = new LinkedList<>();
queue2 = new LinkedList<>();
}
public void push(int x) {
queue2.add(x);
while (!queue1.isEmpty()) {
queue2.add(queue1.remove());
}
Queue<Integer> temp = queue1;
queue1 = queue2;
queue2 = temp;
}
public int pop() {
int top = peek(); // peek方法和top一样,因为top不会移除元素
queue1.remove(); // 移除顶部元素,因为pop操作需要返回并移除栈顶元素
return top;
}
public int top() {
return peek();
}
public boolean empty() {
return queue1.isEmpty();
}
private int peek() {
while (queue1.size() > 1) {
queue2.add(queue1.remove());
}
int top = queue1.peek(); // 保存栈顶元素
queue2.add(queue1.remove()); // 移除栈顶元素
Queue<Integer> temp = queue1;
queue1 = queue2;
queue2 = temp;
return top;
}
}
// 测试代码
public class Main {
public static void main(String[] args) {
MyStack stack = new MyStack();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(stack.top()); // 返回 3
System.out.println(stack.pop()); // 返回 3
System.out.println(stack.empty()); // 返回 false
}
}
```
阅读全文