📚 全栈开发学习系列
01 路线总览与环境搭建 ✅
02 Python 语法基础 ✅
03 Python 进阶（上）：文件读写与模块系统 ✅
04 Python 进阶（下）：异常处理与综合实战 ✅
05 C 语言与内存：指针、分配与释放 ✅
06 数据结构与算法：链表、栈与队列（当前篇）
07 Git 版本控制：分支、合并与冲突解决
08 Linux 命令行：文件、权限与进程管理
数据结构与算法：链表、栈与队列
用 C 和 Python 双语实现三种基础数据结构，理解时间复杂度与适用场景
进阶篇
数据结构
算法基础
读完本篇你将能：用 C 和 Python 双语实现单链表的创建、遍历和头部插入，理解栈的后进先出原理并用数组实现，掌握队列的循环缓冲区设计，能分析三种结构的时间复杂度，并编写一个括号匹配检查器。
📑 本文目录
01从指针到数据结构
02链表：指针的串联艺术
03栈：后进先出的叠盘子
04队列：先进先出的收费站
05时间复杂度对比
06综合实战：括号匹配检查器
07动手练习
01 从指针到数据结构
上一篇你掌握了 C 语言的指针、malloc 和 free——能向系统借内存、还内存。但内存只是原材料，真正有价值的是"如何组织这些内存中的数据"。这就是数据结构要解决的问题。
数组不够用的时候
你已经熟悉数组——一段连续的内存空间，通过下标快速访问。但数组有个致命限制：大小固定。声明 int arr[100] 后，放第 101 个元素就得重新分配。此外，在数组中间插入一个元素，后面所有元素都要后移，时间复杂度 O(n)。
数据结构就是为了解决这些痛点而设计的"数据收纳方案"。本篇学习三种最基础的结构：
链表
用指针串联的节点链，大小动态变化，插入删除 O(1)
栈
后进先出（LIFO），只允许在一端操作，像叠盘子
队列
先进先出（FIFO），一端进另一端出，像收费站排队
每种结构都有 C 和 Python 两种实现。C 让你看清内存层面的运作方式，Python 让你快速验证算法逻辑。两种视角互补，理解会更深刻。
02 链表：指针的串联艺术
链表像一场寻宝游戏：每张纸条上写着一个线索（数据）和下一张纸条的位置（指针）。你不需要把所有纸条摊在桌上排成一排——只要找到第一张，顺着指针就能找到全部。这就是链表的核心思想：用指针将分散的内存节点串联起来。
C 语言实现：节点定义
链表的最小单元是"节点"——一个包含数据和指针的结构体。上一篇学的 struct 和 malloc 在这里派上用场：
C
typedef struct Node {
int data; // 存储的数据
struct Node *next; // 指向下一个节点的指针
} Node;
data 是节点存储的整数，next 是指向下一个节点的指针。最后一个节点的 next 设为 NULL，表示链表到此结束。
创建节点与遍历
创建节点就是 malloc 一块内存，填入数据，把 next 设为 NULL。遍历则从头节点开始，沿着 next 指针逐个访问：
C
Node* create_node(int val) {
Node *n = malloc(sizeof(Node));
n->data = val;
n->next = NULL;
return n;
}
遍历链表——从头节点开始，顺着 next 走到 NULL 为止：
C
void print_list(Node *head) {
Node *cur = head;
while (cur != NULL) {
printf("%d -> ", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
头部插入与释放
链表最高效的操作是在头部插入新节点——只需调整两个指针，无需移动任何现有数据。这是链表相对于数组的核心优势：
C
Node* push_front(Node *head, int val) {
Node *n = create_node(val);
n->next = head; // 新节点指向原头节点
return n; // 返回新头节点
}
C 语言中链表用完必须手动释放每个节点，否则就是内存泄漏——上一篇学到的 free 在这里逐个归还：
C
void free_list(Node *head) {
Node *cur = head;
while (cur != NULL) {
Node *next = cur->next; // 先存下一个
free(cur); // 再释放当前
cur = next; // 走到下一个
}
}
⚠️ 常见错误
free(cur); cur = cur->next; — 先 free 再访问 cur->next，cur 已被释放，cur->next 是野指针访问
✓ 正确：先用 next = cur->next 保存下一个节点的地址，再 free(cur)，最后 cur = next
完整 C 示例与输出
C
|
1
2
3
4
5
6
7
8
9
|
int main() {
Node *list = NULL;
list = push_front(list, 30);
list = push_front(list, 20);
list = push_front(list, 10);
print_list(list);
free_list(list);
return 0;
}
|
运行后输出：
注意：每次 push_front 都返回新的头节点，所以必须用 list = push_front(list, ...) 接住返回值。
Python 实现：同样的逻辑，不同的抽象层
Python 没有显式指针，但对象的引用就是"隐式指针"——self.next = another_node 和 C 的 n->next = another_node 本质相同：
Python
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def push_front(self, val):
node = Node(val)
node.next = self.head
self.head = node
def print_list(self):
cur = self.head
|
Python 版不需要 free_list——垃圾回收器自动处理。使用方式：
Python
ll = LinkedList()
ll.push_front(30)
ll.push_front(20)
ll.push_front(10)
# 链表: 10 -> 20 -> 30 -> None
💡 小贴士
C 中 n->next 是"通过指针访问成员"，等价于 Python 的 node.next。C 需要手动管理内存生命周期，Python 由 GC 自动回收——这是两种语言在设计哲学上的根本差异。
03 栈：后进先出的叠盘子
食堂里叠盘子：你把盘子一个个往上摞，取的时候只能从最上面拿——最后放上去的盘子最先被拿走。这就是栈（Stack）：后进先出（LIFO, Last In First Out）。
栈只有两个核心操作：push（压入，把元素放到顶部）和 pop（弹出，取走顶部元素）。不支持从中间插入或删除——这个限制反而让栈在特定场景下非常高效。
C 实现：数组版栈
用数组实现栈，需要一个 top 变量记录栈顶位置。top = -1 表示空栈，每次 push 先加 1 再写入，pop 先读出再减 1：
C
|
1
2
3
4
5
6
7
8
9
10
11
12
|
#define MAX 100
typedef struct {
int data[MAX];
int top;
} Stack;
void stack_init(Stack *s) {
s->top = -1; // -1 表示空栈
}
// push: 先加1再写入
void push(Stack *s, int val) {
|
C（续）
|
1
2
3
4
5
6
7
8
9
|
if (s->top >= MAX - 1) return; // 栈满
s->data[++s->top] = val;
}
// pop: 先读出再减1
int pop(Stack *s) {
if (s->top < 0) return -1; // 栈空
return s->data[s->top--];
}
|
++s->top 是前缀自增：先把 top 加 1，再用新值做下标。s->top-- 是后缀自减：先用当前值做下标，再减 1。这两个操作符的顺序决定了 push 和 pop 的正确性。
C 栈使用示例
C
Stack s;
stack_init(&s);
push(&s, 10);
push(&s, 20);
push(&s, 30);
printf("%d\n", pop(&s)); // 30
printf("%d\n", pop(&s)); // 20
Python 实现：list 即栈
Python 的 list 天生就是栈——append() 等价 push，pop() 等价 pop，都在末尾操作：
Python
stack = []
stack.append(10) # push
stack.append(20)
stack.append(30)
print(stack.pop()) # 30
print(stack.pop()) # 20
Python 的 list.pop() 默认弹出末尾元素（即栈顶），时间复杂度 O(1)。C 需要手写 40 行代码实现的功能，Python 只需 6 行。
💡 小贴士
栈在编程中无处不在：函数调用时，CPU 把返回地址压入调用栈，函数返回时弹出——递归过深导致 StackOverflow 就是因为调用栈超出了最大容量。浏览器的"后退"按钮、编辑器的"撤销"功能，底层都是栈。
04 队列：先进先出的收费站
高速收费站：最先排队的车最先通过。这就是队列（Queue）：先进先出（FIFO, First In First Out）。元素从一端（rear）进入，从另一端（front）离开。
队列的两个核心操作：enqueue（入队，从尾部添加）和 dequeue（出队，从头部取出）。如果用数组实现，直接移动 front 和 rear 指针会导致前面空间浪费——解决方案是循环队列：把数组想象成环形，rear 到达末尾后绕回开头。
C 实现：循环队列
C
|
1
2
3
4
5
6
7
8
9
10
11
12
|
#define MAX 100
typedef struct {
int data[MAX];
int front; // 出队位置
int rear; // 入队位置
int count; // 当前元素数
} Queue;
void queue_init(Queue *q) {
q->front = 0;
q->rear = 0;
q->count = 0;
}
|
C（续）
|
1
2
3
4
5
6
7
8
9
10
11
|
void enqueue(Queue *q, int val) {
if (q->count >= MAX) return;
q->data[q->rear] = val;
q->rear = (q->rear + 1) % MAX;
q->count++;
}
int dequeue(Queue *q) {
if (q->count <= 0) return -1;
int val = q->data[q->front];
q->front = (q->front + 1) % MAX;
q->count--;
}
|
核心技巧是 (rear + 1) % MAX——取模运算让 rear 到达数组末尾后自动绕回 0，形成环形。这样数组空间可以循环利用，不会浪费。
Python 实现：用 deque 不用 list
Python 中实现队列有一个陷阱：list.pop(0) 的时间复杂度是 O(n)——因为弹出首元素后，后面所有元素都要前移。正确做法是用 collections.deque，它是双端队列，两端操作都是 O(1)：
Python
from collections import deque
q = deque()
q.append(10) # enqueue
q.append(20)
q.append(30)
print(q.popleft()) # 10
print(q.popleft()) # 20
⚠️ 常见错误
q = [1,2,3]; q.pop(0) — 用 list 实现队列，pop(0) 是 O(n) 操作，队列中有 1 万元素时每次出队都要移动 9999 个元素
✓ 正确：使用 collections.deque，popleft() 是 O(1) 操作
💡 小贴士
队列在工程中应用广泛：消息队列（RabbitMQ、Redis Queue）、任务调度（Celery）、打印队列、操作系统进程调度。掌握循环队列的 % MAX 技巧，是理解这些系统底层原理的基础。
05 时间复杂度对比
三种结构各有擅长领域。O(1) 表示常数时间（与数据量无关），O(n) 表示线性时间（随数据量增长而变慢）：
| 操作 |
链表 |
栈 |
队列 |
| 头部插入 |
O(1) |
O(1) push |
O(1) enqueue |
| 头部删除 |
O(1) |
O(1) pop |
O(1) dequeue |
| 随机访问第 i 个 |
O(n) |
不支持 |
不支持 |
| 中间插入 |
O(n)* |
不支持 |
不支持 |
| 内存开销 |
较大（每个节点存指针） |
小（连续数组） |
小（连续数组） |
* 链表中间插入本身是 O(1)（改两个指针），但找到插入位置需要 O(n) 遍历。
选择建议：需要频繁在头部增删元素且大小不确定时用链表；需要"最后放入的最先处理"时用栈（如撤销操作、递归调用）；需要"先来先服务"时用队列（如任务调度、消息传递）。
06 综合实战：括号匹配检查器
栈的经典应用：检查代码中的括号是否匹配。规则是：遇到 ( [ { 时压入栈，遇到 ) ] } 时弹出栈顶检查是否匹配。
算法思路：遍历字符串的每个字符——左括号入栈，右括号弹出栈顶比对。如果弹出的左括号与右括号不匹配，或栈为空时遇到右括号，说明不匹配。遍历结束后栈应该为空。
Python
|
1
2
3
4
5
6
7
8
9
10
|
def is_balanced(text):
stack = []
pairs = {')': '(', ']': '[', '}': '{'}
for ch in text:
if ch in '([{':
stack.append(ch)
elif ch in ')]}':
if not stack or stack.pop() != pairs[ch]:
return False
|
测试用例：
Python
print(is_balanced("({[]})")) # True
print(is_balanced("({[}])")) # False
print(is_balanced("((()))")) # True
print(is_balanced("(()")) # False
第 8 行 if not stack or stack.pop() != pairs[ch] 处理两种异常：栈空（有右括号但没左括号匹配）和栈顶不匹配（如 (]）。最后检查 len(stack) == 0 确保没有多余的左括号。
07 动手练习
🟢 基础验证
用 Python list 实现一个栈，支持 push、pop 和 peek（查看栈顶但不弹出）三个操作。压入 1、2、3 后，peek 应返回 3，pop 应返回 3，再 peek 应返回 2。
🟡 组合应用
用本篇学过的链表结构实现一个栈——不使用数组，而是用 push_front 作为栈的 push 操作，head 作为栈顶。提示：需要实现删除头节点的 pop_front 函数。
🔴 开放挑战
用两个栈实现一个队列。提示：一个栈用于入队（stack_in），另一个用于出队（stack_out）。出队时如果 stack_out 为空，就把 stack_in 中所有元素依次弹出压入 stack_out，再从 stack_out 弹出。分析这个操作的均摊时间复杂度。
📖 知识回顾
链表节点定义
头部插入 O(1)
栈 LIFO
队列 FIFO
循环队列取模
deque vs list
括号匹配
时间复杂度分析
下篇预告
07 Git 版本控制：分支、合并与冲突解决
数据结构的基础已打牢，下一篇进入工程协作核心——用 Git 管理代码版本，学习分支创建、合并策略和冲突解决，让多设备开发不再混乱。