stack and queue

stack

方法	描述	时间复杂度
push()	元素入栈（添加至栈顶）	$O(1)$
pop()	栈顶元素出栈	$O(1)$
peek()	访问栈顶元素	$O(1)$

通常情况下，我们可以直接使用编程语言内置的栈类。然而，某些语言可能没有专门提供栈类，这时我们可以将该语言的“数组”或“链表”当作栈来使用，并在程序逻辑上忽略与栈无关的操作。

1. 链表做栈

• 链表头节点作为栈顶

  • 插入新元素（push）：只要在链表头前面挂一个新节点，O(1) 就完成了。

  • 删除元素（pop）：只要把头节点去掉，指针指到下一个节点，也是 O(1)。

  • 如果你把尾节点当栈顶，那每次删除尾节点都要从头找到尾巴，复杂度变成 O(n)，很慢。

👉 所以链表一般选 头节点 = 栈顶，保证操作快。

---

2. 数组做栈

• 数组尾部作为栈顶

  • 插入新元素：只要在数组最后加一个，O(1) 就行。

  • 删除元素：只要把最后一个删掉，也是 O(1)。

  • 如果你把数组开头当栈顶，那每次插入或删除都要移动后面的所有元素，变成 O(n)。

👉 所以数组一般选 尾部 = 栈顶，避免大规模搬家。

栈的典型应用

• 浏览器中的后退与前进、软件中的撤销与反撤销。每当我们打开新的网页，浏览器就会对上一个网页执行入栈，这样我们就可以通过后退操作回到上一个网页。后退操作实际上是在执行出栈。如果要同时支持后退和前进，那么需要两个栈来配合实现。
• 程序内存管理。每次调用函数时，系统都会在栈顶添加一个栈帧，用于记录函数的上下文信息。在递归函数中，向下递推阶段会不断执行入栈操作，而向上回溯阶段则会不断执行出栈操作。

queue

方法名	描述	时间复杂度
push()	元素入队，即将元素添加至队尾	$O(1)$
pop()	队首元素出队	$O(1)$
peek()	访问队首元素	$O(1)$

为了实现队列，我们需要一种数据结构，可以在一端添加元素，并在另一端删除元素，链表和数组都符合要求。

在数组中删除首元素的时间复杂度为 $O(n)$ ，这会导致出队操作效率较低。然而，我们可以采用以下巧妙方法来避免这个问题。

人为定义”尾指针”，存储，避免每次都要计算：我们可以使用一个变量 front 指向队首元素的索引，并维护一个变量 size 用于记录队列长度。定义 rear = front + size ，这个公式计算出的 rear 指向队尾元素之后的下一个位置。

基于此设计，数组中包含元素的有效区间为 [front, rear - 1]，各种操作的实现方法如下图所示。

• 入队操作：将输入元素赋值给 rear 索引处，并将 size 增加 1 。
• 出队操作：只需将 front 增加 1 ，并将 size 减少 1 。

可以看到，入队和出队操作都只需进行一次操作，时间复杂度均为 $O(1)$ 。

但，在不断进行入队和出队的过程中，front 和 rear 都在向右移动，当它们到达数组尾部时就无法继续移动了。为了解决此问题，我们可以将数组视为首尾相接的“环形数组”：我们需要让 front 或 rear 在越过数组尾部时，直接回到数组头部继续遍历。这种周期性规律可以通过“取余操作”来实现。

double-ended queue

允许在头部和尾部执行元素的添加或删除操作。

方法名	描述	时间复杂度
push_first()	将元素添加至队首	$O(1)$
push_last()	将元素添加至队尾	$O(1)$
pop_first()	删除队首元素	$O(1)$
pop_last()	删除队尾元素	$O(1)$
peek_first()	访问队首元素	$O(1)$
peek_last()	访问队尾元素	$O(1)$

队列典型应用

• 淘宝订单。购物者下单后，订单将加入队列中，系统随后会根据顺序处理队列中的订单。在双十一期间，短时间内会产生海量订单，高并发成为工程师们需要重点攻克的问题。
• 各类待办事项。任何需要实现“先来后到”功能的场景，例如打印机的任务队列、餐厅的出餐队列等，队列在这些场景中可以有效地维护处理顺序。
• 双向队列兼具栈与队列的逻辑，因此它可以实现这两者的所有应用场景，同时提供更高的自由度。
  • 我们知道，软件的“撤销”功能通常使用栈来实现：系统将每次更改操作 push 到栈中，然后通过 pop 实现撤销。然而，考虑到系统资源的限制，软件通常会限制撤销的步数（例如仅允许保存 $50$ 步）。当栈的长度超过 $50$ 时，软件需要在栈底（队首）执行删除操作。但栈无法实现该功能，此时就需要使用双向队列来替代栈。请注意，“撤销”的核心逻辑仍然遵循栈的先入后出原则，只是双向队列能够更加灵活地实现一些额外逻辑。