使用两个队列可以实现一个栈,一个队列用来存储栈中的元素,另一个队列用来在pop操作时暂存元素。
上才艺:
import java.util.LinkedList;
import java.util.Queue;
public class MyStack<T> {
private Queue<T> queue; // 主队列
private Queue<T> tempQueue; // 辅助队列
public MyStack() {
queue = new LinkedList<>();
tempQueue = new LinkedList<>();
}
// 添加元素到栈顶
public void push(T element) {
queue.offer(element);
}
// 弹出栈顶元素并返回
public T pop() {
if (isEmpty()) {
throw new RuntimeException("stack is empty");
}
// 将主队列中除了最后一个元素外的所有元素移到辅助队列中
while (queue.size() > 1) {
tempQueue.offer(queue.poll());
}
T element = queue.poll(); // 获取最后一个元素
Queue<T> temp = queue; // 交换主队列和辅助队列的引用
queue = tempQueue;
tempQueue = temp;
return element;
}
// 获取栈顶元素但不弹出
public T peek() {
if (isEmpty()) {
throw new RuntimeException("stack is empty");
}
// 将主队列中除了最后一个元素外的所有元素移到辅助队列中
while (queue.size() > 1) {
tempQueue.offer(queue.poll());
}
T element = queue.poll(); // 获取最后一个元素
tempQueue.offer(element); // 将最后一个元素放回主队列
Queue<T> temp = queue; // 交换主队列和辅助队列的引用
queue = tempQueue;
tempQueue = temp;
return element;
}
// 判断栈是否为空
public boolean isEmpty() {
return queue.isEmpty();
}
}
其中,push方法用来入栈,直接将元素加入queue队列中。
pop方法用来出栈,先将queue队列中的元素倒入tempQueue队列中,直到queue队列中只有一个元素,将其弹出即可。
peek方法用来获取栈顶元素,与pop方法类似,只是在弹出元素之前需要先将其加入tempQueue队列中
isEmpty方法用来判断栈是否为空,如果queue队列为空,则栈为空。
这个实现的时间复杂度为O(n),空间复杂度为O(n),其中n为栈中元素的个数。