使用两个堆栈来实现队列
时间: 2024-05-05 19:16:23 浏览: 7
使用两个堆栈来实现队列的算法如下:
1. 创建两个堆栈stack1和stack2,分别用于存储队列中的元素。
2. 元素入队操作:将元素压入stack1中。
3. 元素出队操作:先检查stack2是否为空,如果不为空,则直接弹出stack2的栈顶元素作为队列的出队元素;如果stack2为空,则将stack1中的所有元素依次弹出并压入stack2中,然后再从stack2中弹出栈顶元素作为队列的出队元素。
4. 元素获取操作:同出队操作,只是不弹出栈顶元素。
下面是使用Java语言实现的代码:
```java
import java.util.Stack;
public class QueueWithTwoStacks<T> {
private Stack<T> stack1 = new Stack<>();
private Stack<T> stack2 = new Stack<>();
public void enqueue(T item) {
stack1.push(item);
}
public T dequeue() {
if (stack2.isEmpty()) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
public T peek() {
if (stack2.isEmpty()) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
return stack2.peek();
}
public boolean isEmpty() {
return stack1.isEmpty() && stack2.isEmpty();
}
public int size() {
return stack1.size() + stack2.size();
}
}
```
在上面的代码中,enqueue()方法将元素压入stack1中,dequeue()方法先检查stack2是否为空,如果不为空,则直接弹出stack2的栈顶元素作为队列的出队元素;如果stack2为空,则将stack1中的所有元素依次弹出并压入stack2中,然后再从stack2中弹出栈顶元素作为队列的出队元素。peek()方法也是同理。isEmpty()方法检查队列是否为空,size()方法返回队列中元素的个数。