第二周学数据结构，说实话是个分水岭。第一周大家还停留在数组、顺序表这种“连续内存、按下标访问”的结构，写起来无非是for循环配合下标移动；到了第二周，链表、栈、队列、双端队列、递归、复杂度分析一股脑压过来，很多同学就是从这里开始掉队的。我每年带实验、帮学生看代码，都会特别强调这一周，因为后面树、图、查找、排序这些大块头，全都要靠第二周对“线性结构”和“受限线性结构”的理解来垫底。

这篇内容不是课程ppt的复述，而是把第二周我认为必须搞懂的思路、必须亲手写的代码，以及最容易踩的坑，全部梳理一遍。不管你是学校刚开数据结构课的本科生，还是准备408考研、正在啃王道那本厚书的，又或者只是用Python做数据分析、想弄明白pandas底层数据组织方式的，第二周这些内容都值得慢慢过一遍。

1. 第二周的知识地图：先搞清楚这一周到底在学什么

很多同学第二周觉得乱，是因为还在用第一周的方式学第二周的内容。第一周是“认识结构”：数组、顺序表，逻辑简单，顺着讲就能懂。第二周变成了“设计结构”和“分析结构”，光看懂已经不够了，你得能回答“为什么这样设计”“这样设计代价是什么”，这就涉及实现细节和复杂度分析。

1.1 为什么第二周开始“折腾”线性结构

第一周学的顺序表，本质是一段连续内存，按下标访问是O(1)，插入删除却要移动大量元素，最坏O(n)。第二周引入链表，结点散落在内存各处，通过指针串联，插入删除只需要修改相邻结点的指针，理论上是O(1)，但按下标访问第k个元素就得从头遍历。

很多初学者觉得链表“多此一举”，数组不是挺好吗。这个想法等到学树和图就会改变。树的左右孩子表示法、图的邻接表、哈希表的链地址法，本质都是链表思想在不同场景下的延伸。第二周把链表玩明白，后面碰到邻接表、二叉树的孩子兄弟表示法，会有一种“这我熟”的感觉。

另外，链表也是练习指针或者引用操作的绝佳素材。C语言版教材里，严蔚敏那本经典书几乎所有线性表章节都在强调指针操作；到了408考研真题，链表更是常客，反转链表、删除倒数第k个结点、判断是否有环，年年都有变体。第二周不把链表写稳，后面刷题会很被动。

1.2 栈、队列与双端队列：三个被“限制”的结构

栈和队列其实是“被限制的线性表”。栈限制成只能在一端插入删除，叫做后进先出；队列限制成一边进另一边出，叫做先进先出。为什么要把线性表“阉割”成这个样子？因为现实场景里很多操作根本不需要随机访问，只需要“记住最近的状态”或者“按顺序处理任务”。

栈的经典场景是函数调用：函数A调用函数B，B返回之后还得回到A继续执行，这就是一个天然的后进先出过程。浏览器的后退按钮、编辑器的撤销功能，底层都是栈。队列的经典场景是任务排队：打印机任务、消息队列、操作系统的进程调度，先到的先处理。双端队列则更灵活，两端都能进出，像一条两头都能开门的通道，滑动窗口最大值、回文检查这类问题往往用它。

408考研里，栈和队列的题目非常多。给你一个入栈序列，问哪个出栈序列合法；给你循环队列的头尾指针，判断队列是满还是空；用两个栈实现一个队列，要求写出push和pop的逻辑，这些都是高频考点。第二周把这些吃透，期末复习会轻松不少。

1.3 复杂度分析：空间复杂度为什么总被忽略

第二周开始写链表、写递归，复杂度分析就躲不掉了。大家通常更关注时间复杂度，毕竟“程序跑得快不快”最直观。但空间复杂度同样影响程序能不能跑起来。一个递归深度100万层的函数，即使逻辑正确，也可能直接把栈撑爆。

空间复杂度的计算，关键看“额外开辟了多少空间”，而且要看最坏情况。比如计算斐波那契数列，递归写法每一层调用都占栈空间，深度n层就是O(n)，迭代写法只用两个临时变量，O(1)。再比如归并排序需要一个和原数组等长的辅助数组，O(n)；快速排序虽然原地排序不需要额外数组，但递归调用需要栈空间，平均O(log n)，最坏O(n)。这些数字在写实验报告和考研复现时都要能算清楚。

我见过太多人代码能跑，但问“你这算法空间复杂度是多少”就卡住。第二周开始每写一个结构、一个算法，都强制自己回答三个问题：时间最好、最坏是多少？空间最坏是多少？我能不能用更少空间换时间？养成这个习惯，比多刷十道题都有用。

2. 核心知识点拆解与隐藏考点

第二周的知识点不算多，但每个都值得细抠。链表的边界处理、栈和队列的判空判满、双端队列的底层设计，这些细节才是拉开差距的地方。这一部分我会把隐藏的考点一个个挑出来讲。

2.1 链表反转为什么成了“必考题”

链表反转几乎是所有面试和考研复试的保留节目。原因很简单：它代码量不大，但非常考验对指针操作的理解。写错的人，十有八九是栽在指针顺序上。

迭代反转的思路是三个指针：prev记录前一个结点，cur记录当前结点，next保存下一个结点。每次循环做四件事：先把next存起来，再让cur的next指向prev，然后把prev挪到cur，最后cur挪到next。很多初学者写的时候先改cur的next，结果后面的结点找不到了，这就是没提前保存next导致的。

递归写法更考验思维。假设链表是1->2->3->4->5，递归到尾结点5之后逐层返回，每一层做的事是：让当前结点的下一个结点的next指回当前结点，然后当前结点的next置空。核心代码是head.next.next = head，乍一看很绕，但画图之后就清楚了。递归反转的缺点是栈空间可能很大，链表特别长时容易溢出，所以工程上常用迭代版本。

2.2 栈的两种实现：数组栈与链式栈

栈的实现有两条路，一条基于数组，一条基于链表。数组栈用top指针指向栈顶元素，初始top=-1表示空栈；入栈时先检查top是否等于maxSize-1，满了就报错；出栈时先判断top是否等于-1，空了再操作就是下溢。

链式栈相对简单，每次入栈就是头插法插入一个新结点，top指向链表头。它不需要提前知道最大容量，内存按需分配。两套方案没有绝对优劣：数组栈的优点是内存连续、缓存友好、实现简单；缺点是有容量上限。链式栈的优点是容量灵活；缺点是每个结点都要额外存指针，并且频繁malloc/free有性能开销。

实践里栈的应用非常多，括号匹配就是一个典型。写一个函数，遍历字符串，遇到左括号入栈，遇到右括号就弹出栈顶检查是否匹配。栈空遇到右括号、遍历结束栈里还有左括号，都属于不匹配。这个题目看着简单，很多人在“栈空”这个边界上翻车。

2.3 队列实现与循环队列的边界问题

队列用数组实现时，如果队头出队、队尾入队，反复操作之后队尾会撞到数组末尾，前面空着的位置却用不上，这就是“假溢出”。解决办法是循环队列，把数组逻辑上连成一个环。

循环队列最关键的两个公式必须背熟。判空：front == rear。判满：(rear + 1) % maxSize == front。队列元素个数：(rear - front + maxSize) % maxSize。

这里有一个常见困惑：为什么要浪费一个存储位置。因为如果不浪费，初始时front == rear表示空，插入一个元素后rear += 1，此时front和rear还是不相等，于是“空”和“满”的状态就分不清了。所以循环队列默认牺牲一个存储单元，用“尾指针再走一步就追上头指针”来表示满。

还有一种实现是加一个count计数器记录元素个数，这样就不浪费空间了。但每次入队出队都要维护count，多一步操作。考研和期末考试里，两种方案都可能出现，关键是看题目怎么定义结构体。

2.4 双端队列的设计思路

双端队列（deque，double-ended queue）允许在队头和队尾两端进行插入删除。它比栈和队列灵活，但也不算复杂。实现思路大致有三种。

第一种是用双向链表实现。每个结点有prev和next两个指针，再维护头尾两个哨兵结点，插入删除都是O(1)。第二种是用循环数组实现，需要维护front和rear两个指针，并且插入时要注意循环回绕。第三种是直接用现成容器，Python里有collections.deque，C++里有std::deque，Java里是ArrayDeque。

双端队列的经典应用是滑动窗口最大值。比如一个数组和一个窗口大小k，要求输出每个窗口的最大值。如果用暴力法，每个窗口都扫一遍，复杂度O(nk)；用双端队列维护当前窗口候选下标，队头始终是最大值下标，就能做到O(n)。这个题在LeetCode上叫Sliding Window Maximum，是双端队列的最好练手题目。

很多教材把双端队列放在队列章节的最后，简单提两句就过去了。但408和面试题里它出现的频率并不低，建议第二周就把它和普通队列一起消化掉。

2.5 查找与排序的第一轮入门

第二周一般还会接触最简单的查找和排序。查找里最重要的是二分查找，前提是数据有序，每次把搜索区间缩小一半，时间O(log n)。二分查找的细节很多：循环条件是low <= high还是low < high，mid应该怎么算，更新边界时到底加一减一，这些不做几道题真的记不住。

排序部分，第二周至少要掌握冒泡、选择和插入三种O(n²)排序，理解它们为什么慢：每次比较都可能只消除一个逆序对。在此基础上，可以开始碰快速排序和归并排序。快排的核心是partition，一趟划分之后，枢轴元素落到最终位置，左边都小于等于它，右边都大于等于它。归并排序则是“先分后合”，需要借助辅助数组。

我整理一个第二周常见排序的复杂度对照表，写实验报告和期末复习都能直接用：

这个表不需要死记，而要能推导。比如插入排序在接近有序时非常快，所以最好时间是O(n)；快排坏在每次划分都极度不平衡，所以最坏退化成O(n²)。

3. 实操记录：这一周我建议你亲手写一遍的代码

数据结构是“手感”学科，看懂和写出来完全是两回事。第二周我布置给学生的任务，通常固定在五个小实验上。这些实验不需要很大的代码量，但每一个都把本周核心知识砸得很实。

3.1 实验1：用数组实现循环队列

先定义一个结构体，包含数组、队头front、队尾rear和最大容量maxSize。初始时front和rear都置为0。然后实现init、isEmpty、isFull、enqueue、dequeue、length几个基本函数。下面是我常用的C语言参考版本：

#include <stdio.h> #include <stdlib.h> typedef struct { int *data; int front; int rear; int maxSize; } CircularQueue; void initQueue(CircularQueue *q, int size) { q->data = (int *)malloc(sizeof(int) * size); q->front = 0; q->rear = 0; q->maxSize = size; } int isEmpty(CircularQueue *q) { return q->front == q->rear; } int isFull(CircularQueue *q) { return (q->rear + 1) % q->maxSize == q->front; } int enqueue(CircularQueue *q, int value) { if (isFull(q)) return 0; q->data[q->rear] = value; q->rear = (q->rear + 1) % q->maxSize; return 1; } int dequeue(CircularQueue *q, int *value) { if (isEmpty(q)) return 0; *value = q->data[q->front]; q->front = (q->front + 1) % q->maxSize; return 1; }

测试的时候要故意制造边界情况：空队列出队，满队列入队，入队出队交替进行直到绕一圈。只测正常路径测不出问题，边界用例才是实验报告的加分项。

3.2 实验2：用两个栈实现队列

这是栈与队列章节的高频题。思路是维护两个栈：inStack负责入队，outStack负责出队。入队时直接push到inStack；出队时，如果outStack为空，就把inStack所有元素倒到outStack，再pop outStack。这样元素顺序被两次反转，正好恢复成先进先出。

class MyQueue: def __init__(self): self.in_stack = [] self.out_stack = [] def push(self, x: int) -> None: self.in_stack.append(x) def pop(self) -> int: if not self.out_stack: while self.in_stack: self.out_stack.append(self.in_stack.pop()) return self.out_stack.pop() def peek(self) -> int: if not self.out_stack: while self.in_stack: self.out_stack.append(self.in_stack.pop()) return self.out_stack[-1] def empty(self) -> bool: return not self.in_stack and not self.out_stack

这里有一个很重要的优化点：out_stack里还有元素时，不要急着从in_stack倒数据，否则会打乱顺序。很多第一次写的同学每次pop都倒一遍，结果队列顺序全乱了。正确的做法是“out_stack空了才倒”。

3.3 实验3：反转链表的迭代与递归

反转链表我建议迭代和递归都写一遍。迭代版用三个指针，前面已经讲过，这里直接给代码。递归版则要理解“当前结点后面的链表已经反转好了，我只需要把自己接上去”。

struct ListNode { int val; struct ListNode *next; }; // 迭代反转 struct ListNode* reverseList(struct ListNode* head) { struct ListNode *prev = NULL; struct ListNode *cur = head; struct ListNode *next; while (cur != NULL) { next = cur->next; cur->next = prev; prev = cur; cur = next; } return prev; } // 递归反转 struct ListNode* reverseListRecursive(struct ListNode* head) { if (head == NULL || head->next == NULL) { return head; } struct ListNode *newHead = reverseListRecursive(head->next); head->next->next = head; head->next = NULL; return newHead; }

写递归版时，我建议先画一个只有三个结点的链表，手动走一遍调用栈。知道每层返回的newHead是谁，就掌握了递归反转的本质。

3.4 实验4：快速排序的一次完整推导

快速排序第二周先不用全写，但partition过程一定要能手推一次。我常用一个经典例子：arr = [49, 38, 65, 97, 76, 13, 27]。选第一个元素49作为枢轴，目标是让49左边都小于等于它，右边都大于等于它。

具体过程是：用i指向最左，j指向最右。先从j开始向左找比枢轴小的元素，找到27，把27放到i位置；然后i从左边向右找比枢轴大的元素，找到65，把65放到j位置；继续交替，直到i和j相遇。最后把枢轴49放入相遇位置。一趟结束后数组变成 [27, 38, 13, 49, 76, 97, 65]，49已经落在它最终的位置上。

手推一遍之后要回答两个问题：这个pivot最终位置是几？快排为什么说平均O(n log n)而不是每趟都缩小一半就完了？能回答上来，快排才算真的入门了。

3.5 实验5：用Python pandas体验“数据结构创建”

如果你是Python方向，第二周可以顺手做一个小实验：用pandas创建Series和DataFrame，体会“在底层数组上再包一层索引和标签”这件事。

import pandas as pd s = pd.Series([10, 20, 30], index=['a', 'b', 'c']) print(s) print(s.values) print(s.index) df = pd.DataFrame({ '姓名': ['张三', '李四'], '成绩': [88, 92] }, index=[1, 2]) print(df) print(df['成绩'].values)

Series的values本质就是一个ndarray，index可以理解为行标签数组。DataFrame则可以看作多个Series按列拼起来。很多人在“头歌”平台上做过pandas数据结构创建的练习，核心就是理解DataFrame创建时，字典的键会成为列名，而数据本身还是存放在连续数组中。这个理解对你以后分析数据、写实验报告都有帮助，因为它把“抽象结构”和“底层实现”串起来了。

3.6 实验报告怎么写才有含金量

每到期末，总有人问“数据结构实验报告有没有模板”。我的看法是，模板只能解决格式问题，解决不了内容空洞。一份有含金量的实验报告，至少要包含几个部分：实验目的、设计思路、核心代码、测试用例、边界情况分析、复杂度分析。

举例来说，循环队列的报告不能只写“我实现了入队和出队”。你应当写出：为什么用循环数组、判空和判满公式是怎么推导出来的、测试时覆盖了空队出队和满队入队两个异常路径、时间复杂度和空间复杂度分别是多少。这些东西写下来，才称得上“实验报告”，而不是代码抄写。

顺便提醒一句，网上流传的教材PDF版本很多，有的还有排版错误。比如李春葆老师的《数据结构》第五版就有学习指导勘误汇总，建议对照勘误再看，不然代码照着抄可能都跑不通。

4. 常见问题与排查技巧实录

第二周的问题非常集中，基本就那几类。我把这几年带实验时最常见的坑整理成一个速查表，再逐个展开讲。

4.1 段错误与指针悬垂

链表操作出现段错误，九成是指针问题。常见情况有三类：malloc分配内存后没有检查返回值就使用；free之后还继续访问那块内存，这就是悬垂指针；遍历链表时循环条件写错，比如把cur != NULL写成cur->next != NULL，导致空指针解引用。

排查段错误，我有个习惯：先看崩溃行，再往上一两行看指针状态。链表题画图非常重要，把prev、cur、next三个指针的指向画出来，每一步操作之后是什么样子，一目了然。很多学生不爱画图，觉得浪费时间，实际上一道链表面试题，画图三分钟，盲写半小时还可能错。

4.2 循环队列的判空判满误区

循环队列最大的坑不是实现，而是公式用错。假如maxSize=5，初始front=rear=0，连续入队4个元素之后rear=4，此时再入队第5个，按公式(rear + 1) % maxSize == front，也就是5 % 5 == 0，等于front，所以队列满，无法再入。于是队里最多只能放4个元素，最后一个位置永久空着。这个设计必须理解，否则考场上容易懵。

如果题目明确说用count记录元素个数，那就不需要浪费空间。isFull的判断变成count == maxSize，isEmpty变成count == 0。做题时先看清楚题目给的结构体包含哪些字段，再决定用哪套公式。

4.3 递归栈溢出

递归是第二周开始大量出现的写法。有些同学喜欢递归反转链表、递归算斐波那契、递归遍历树，看起来很简洁，但递归深度过大时，Python会抛RecursionError，C语言则直接栈溢出崩溃。

我踩过最惨的一次是写一个深搜，递归深度到了几万层，程序毫无征兆地崩溃。后来改成显式栈模拟递归，完美解决。所以写递归前先估算深度：如果输入规模可能达到百万级别，就不要用递归；如果深度可控，则要注意终止条件和base case。Python里确实可以调大sys.setrecursionlimit，但那是治标不治本，工程上还是优先考虑迭代。

4.4 空间复杂度总被忽略

很多同学写完算法只报时间复杂度，空间复杂度一句话带过，这其实很亏。面试和考试恰恰喜欢在空间复杂度上做文章。判断标准很简单：除了输入数据占用的空间，你的算法额外开了多少内存。

举个例子，反转链表迭代版只用固定几个指针，O(1)；递归版每次递归都在栈上压一层，O(n)。归并排序需要等长辅助数组，O(n)；计数排序、桶排序要看数据范围，可能O(k)。做题时多问一句“能不能原地完成”，不仅能降低空间复杂度，还能加深对算法的理解。

4.5 学习资料那么多，到底怎么选

后台经常有人问我数据结构看严蔚敏还是王道，C语言版还是Python版，要不要买PDF。我的建议很简单：挑一本主教材，从头到尾跟完，比同时翻十本书强。严蔚敏的C语言版是经典，逻辑严谨但代码风格偏教学；王道更适合考研应试，知识点归纳很系统；李春葆版本题目丰富，但要注意看勘误。Python方向则可以搭配pandas和collections模块的官方文档练习。

还有人说“数据结构排序算法那么多，记不住”。其实不用记，把每个排序的“一趟操作”亲手模拟一遍，时间复杂度自然就推出来了。这一周不要急着赶进度，把链表、栈、队列、双端队列和复杂度分析的底子打好，后面学树和图会顺畅得多。

我个人带实验的过程中体会最深的一点是：第二周最容易掉队的不是听不懂，而是只看书不写代码。数据结构是一门需要“手感”的学科，链表反转、循环队列、快排划分这些操作，看十遍不如自己写一遍。建议这周准备一个小本子，专门记边界条件：空栈、空队、满队、头结点、空链表，每一种情况单独记一页。以后刷题、期末复习、考研冲刺，这本子翻出来比任何笔记都有用。第二周的内容看着多，拆解开就是几个结构加几种操作，一个一个过，完全来得及。