栈(Stack)
定义:栈是一种遵循后进先出(LIFO, Last In First Out)原则的有序集合。新添加或待删除的元素都保存在栈的同一端,称为栈顶,另一端称为栈底。在栈中,元素的添加(称为压栈或入栈)和移除(称为弹栈或出栈)操作都只能在栈顶进行。
特性:
- 后进先出:最后添加到栈中的元素将是第一个被移除的。
- 栈顶元素:栈顶元素是栈中最后被添加进去的元素,也是唯一可以从栈中删除的元素(在没有进行其他入栈操作的情况下)。
- 栈底元素:栈底元素是栈中最早被添加进去的元素,也是唯一无法直接通过正常操作被删除的元素(除非栈被完全清空)。
应用场景:
- 函数调用栈:在程序执行过程中,函数调用是通过栈来实现的,每调用一个函数,就会将其返回地址以及局部变量等压入栈中,当函数执行完毕时,再从栈中弹出这些信息,返回到调用点继续执行。
- 表达式求值:栈在表达式求值中非常重要,尤其是中缀表达式转换为后缀表达式,以及后缀表达式的计算。
- 后台任务管理:如浏览器的标签页管理,最近访问的页面通常显示在最前面。
队列(Queue)
定义:队列是一种遵循先进先出(FIFO, First In First Out)原则的有序集合。队列的头部是队列中存放时间最长的元素,队列的尾部是存放时间最短的元素。新元素被添加到队列的尾部,移除操作(也称为出队)则发生在队列的头部。
特性:
- 先进先出:最先添加到队列中的元素将是第一个被移除的。
- 队列头:队列中最早被添加进去的元素,也是第一个被移除的元素。
- 队列尾:队列中最后被添加进去的元素,它只能在其他元素被移除后才能成为队列头。
应用场景:
- 缓冲区:如操作系统中用于存储输入输出数据的缓冲区。
- 任务调度:在多任务系统中,任务按照它们进入系统的顺序被处理。
- 并发编程:在并发编程中,队列常被用来管理线程或进程的任务分配。
如何用栈实现队列
方法概述
- 入队(Enqueue):将元素压入第一个栈(我们称之为“输入栈”)。
- 出队(Dequeue):
- 如果第二个栈(我们称之为“输出栈”)为空,则将第一个栈中的所有元素依次弹出并压入第二个栈。此时,第一个栈的栈底元素(即最先入队的元素)就变成了第二个栈的栈顶元素。
- 然后从第二个栈中弹出栈顶元素,该元素即为队列的队首元素。
- 检查队列是否为空:如果两个栈都为空,则队列为空。
class MyQueue {
private Stack<Integer> stackIn; // 输入栈
private Stack<Integer> stackOut; // 输出栈
public MyQueue() {
stackIn = new Stack<>();
stackOut = new Stack<>();
}
// 入队
public void enqueue(int x) {
stackIn.push(x);
}
// 出队
public int dequeue() {
// 如果输出栈为空,则将输入栈的元素倒序压入输出栈
if (stackOut.isEmpty()) {
while (!stackIn.isEmpty()) {
stackOut.push(stackIn.pop());
}
}
// 从输出栈中弹出栈顶元素
return stackOut.pop();
}
// 查看队首元素
public int front() {
// 如果输出栈为空,则需要先将输入栈的元素倒序压入输出栈
if (stackOut.isEmpty()) {
while (!stackIn.isEmpty()) {
stackOut.push(stackIn.pop());
}
}
// 返回输出栈的栈顶元素,但不弹出
return stackOut.peek();
}
// 检查队列是否为空
public boolean isEmpty() {
// 如果两个栈都为空,则队列为空
return stackIn.isEmpty() && stackOut.isEmpty();
}
}
注意事项
- 这种方法在每次
dequeue
或front
操作前,可能需要将输入栈的所有元素转移到输出栈,这会增加额外的时间复杂度。在最坏的情况下(每次enqueue
后都紧接着dequeue
或front
),时间复杂度会达到O(n)。 - 然而,从平均或摊还分析的角度来看,由于每个元素最多被转移两次(一次从输入栈到输出栈,一次从输出栈中弹出),因此摊还时间复杂度仍然是O(1)。
- 这种方法的空间复杂度是O(n),其中n是队列中元素的数量,因为需要两个栈来存储队列中的所有元素
如何用队列实现栈
方法概述
我们可以使用两个队列,我们称之为queue1
和queue2
。主要思路是,在模拟栈的push
操作时,我们直接将元素入队到queue1
。然而,在模拟栈的pop
操作时,我们需要将queue1
中除了最后一个元素之外的所有元素都移动到queue2
,然后从queue1
中弹出最后一个元素(即栈顶元素)。最后,为了保持两个队列的轮转使用,我们可以将queue2
重新命名为queue1
(或将queue1
的引用指向queue2
,如果使用的是引用类型的队列),并将原来的queue1
清空或重新用作queue2
。
class MyStack {
private Queue<Integer> queue1; // 主队列
private Queue<Integer> queue2; // 辅助队列
public MyStack() {
queue1 = new Queue<>();
queue2 = new Queue<>();
}
// 入栈
public void push(int x) {
queue1.enqueue(x);
}
// 出栈
public int pop() {
// 如果queue1为空,则直接返回-1或抛出异常,表示栈为空
if (queue1.isEmpty()) {
// 这里可以根据需要抛出异常或返回-1等
throw new RuntimeException("Stack is empty");
}
// 将queue1中除了最后一个元素之外的所有元素都移动到queue2
while (queue1.size() > 1) {
queue2.enqueue(queue1.dequeue());
}
// 弹出queue1中的最后一个元素,即栈顶元素
int top = queue1.dequeue();
// 为了保持轮转使用,交换queue1和queue2的角色
Queue<Integer> temp = queue1;
queue1 = queue2;
queue2 = temp;
// 可选:清空或重置queue2
queue2.clear();
return top;
}
// 查看栈顶元素
public int top() {
// 类似pop操作,但不弹出元素
if (queue1.isEmpty()) {
throw new RuntimeException("Stack is empty");
}
while (queue1.size() > 1) {
queue2.enqueue(queue1.dequeue());
}
int top = queue1.peek(); // peek操作不弹出元素
// 将刚才移出的元素移回queue1
queue2.enqueue(queue1.dequeue());
// 交换queue1和queue2的角色
Queue<Integer> temp = queue1;
queue1 = queue2;
queue2 = temp;
// 清空或重置queue2
queue2.clear();
return top;
}
// 检查栈是否为空
public boolean isEmpty() {
return queue1.isEmpty();
}
}
注意事项
- 这种方法的时间复杂度是O(n),其中n是栈中的元素数量。因为每次
pop
或top
操作都可能需要将queue1
中的元素移动到queue2
。 - 空间复杂度是O(n),因为我们需要两个队列来存储栈中的所有元素。然而,由于这两个队列在逻辑上是相互替代的,所以实际使用的额外空间并不会随着栈的大小线性增长,而是保持在一个固定的水平(两个队列的容量)。但是,从“空间使用峰值”的角度来看,我们可以说空间复杂度是O(n)。
- 在实际应用中,如果
pop
和top
操作非常频繁,这种方法可能会因为大量的元素移动而导致性能问题。因此,在选择实现方式时,需要根据具体的应用场景和需求进行权衡。