Stack, Queue & Deque

Stack

Stack：

LIFO — Last In, First Out

主要操作：

• push
• pop
• top / peek

常见应用：

• 函数调用栈
• 括号匹配
• DFS
• 表达式计算
• Undo

---

Queue

Queue：

FIFO — First In, First Out

主要操作：

• enqueue
• dequeue
• front

常见应用：

• BFS
• 任务调度
• 消息处理
• 请求排队

---

Deque

Deque（Double-Ended Queue）是双端队列，两端都允许插入和删除。

典型操作：

left  ← [ ... ] → right

可以同时支持：

• 左端插入 / 删除
• 右端插入 / 删除

在合适实现下，两端操作通常都可以做到 O(1)。

因此 Deque 可以灵活承担：

• FIFO Queue
• 某些 Stack 场景
• 双端滑动窗口等需要两端操作的场景

---

Python Queue / Deque

不推荐高频使用：

list.pop(0)

因为 Python list 本质上是动态数组。

删除第 0 个元素后，后面的元素需要整体移动：

$$O(n)$$

推荐：

from collections import deque

q = deque()
q.append(x)
q.popleft()

deque 为双端插删设计，常见的：

• append
• appendleft
• pop
• popleft

均可做到 O(1)。

---

易错点

Python list 不是链表，其底层更接近动态数组。

不要因为 list 可以 append/pop 就把它和链表或 Deque 的底层结构混为一谈。

---

Practice:

04_Practice/CS_MCQs/Data_Structure_Lesson_1.md

Interview QA:

06_Interview/CS_QA/Data_Structure.md