队列和栈基础
raw/articles/2026/05/队列和栈基础
核心要点
队列和栈都是操作受限的数据结构，基于数组（顺序存储）和链表（链式存储）实现。
队列（Queue）
- 特性：先进先出（FIFO — First In First Out）
- 操作限制：只能在队尾插入元素，在队头删除元素
- 类比：排队买票，先来的先离开
栈（Stack）
- 特性：先进后出（LIFO — Last In First Out）
- 操作限制：只能在栈顶插入和删除元素
- 类比：一摞盘子，最后放的在最上面，最先被拿走
基本 API
队列 API
| 方法 |
描述 |
时间复杂度 |
push(E e) |
向队尾插入元素 |
O(1) |
pop() |
从队头删除并返回元素 |
O(1) |
peek() |
查看队头元素（不删除） |
O(1) |
size() |
返回队列中元素个数 |
O(1) |
栈 API
| 方法 |
描述 |
时间复杂度 |
push(E e) |
向栈顶插入元素 |
O(1) |
pop() |
从栈顶删除并返回元素 |
O(1) |
peek() |
查看栈顶元素（不删除） |
O(1) |
size() |
返回栈中元素个数 |
O(1) |
关键理解
- 操作受限的本质：队列和栈的 API 是数组/链表 API 的子集，只保留头尾操作
- 底层实现：可以用数组或链表实现（后续文章会讲解具体实现）
- 与基础结构的关系：所有高级数据结构都是基于数组和链表"玩花活"
相关概念
- 数组：顺序存储基础
- 链表：链式存储基础
- 队列：队列概念页
- 栈：栈概念页