当前位置：首页 > news >正文

使用两个队列实现栈

news 2025/9/13 23:50:37

在计算机科学中，栈是一种数据结构，它遵循后进先出（LIFO）的原则。这意味着最后一个被添加到栈的元素将是第一个被移除的元素。然而，Java的标准库并没有提供栈的实现，但我们可以使用两个队列来模拟一个栈的行为。

首先，我们需要创建一个名为MyStack的类，该类包含两个栈：queue1和queue2。这两个栈将用于实现队列的功能。接下来，我们需要实现队列的基本操作，包括push、pop、peek和empty。

首先，我们需要创建一个栈类

public class MyStack {Queue<Integer> queue1;Queue<Integer> queue2;public MyStack(){queue1 = new LinkedList<>();queue2 = new LinkedList<>();}
}

push方法

push(int value): 将一个元素添加到栈中。首先，我们将该元素添加到queue2中。然后，我们将queue1中的所有元素移动到queue2中，直到queue1为空。最后，我们交换queue1和queue2的角色，使得queue1始终是栈顶元素所在的队列。

public void push(int value){queue2.offer(value);while (!queue1.isEmpty()){queue2.offer(queue1.poll());}Queue<Integer> temp = queue1;queue1 = queue2;queue2 = temp;}

pop方法

pop(): 从栈中移除并返回栈顶元素。由于栈顶元素位于queue1中，我们只需调用queue1.poll()即可。

public int pop(){return queue1.poll();}

top()方法

top(): 返回栈顶元素但不将其从栈中移除。由于栈顶元素位于queue1中，我们只需调用queue1.peek()即可。

public int top(){return queue1.peek();}

isEmpty方法

isEmpty(): 检查栈是否为空。我们只需检查queue1是否为空即可。

public boolean isEmpty(){return queue1.isEmpty();}

完整代码

public class MyStack {Queue<Integer> queue1;Queue<Integer> queue2;public MyStack(){queue1 = new LinkedList<>();queue2 = new LinkedList<>();}public void push(int value){queue2.offer(value);while (!queue1.isEmpty()){queue2.offer(queue1.poll());}Queue<Integer> temp = queue1;queue1 = queue2;queue2 = temp;}public int pop(){return queue1.poll();}public int top(){return queue1.peek();}public boolean isEmpty(){return queue1.isEmpty();}}

测试类

public class Test {public static void main(String[] args) {MyStack myStack = new MyStack();System.out.println(myStack.isEmpty());  // truemyStack.push(1);myStack.push(2);myStack.push(3);System.out.println(myStack.pop()); // 3System.out.println(myStack.pop()); // 2System.out.println(myStack.isEmpty()); // falseSystem.out.println(myStack.pop()); // 1System.out.println(myStack.isEmpty()); // true}
}

运行结果