▤ 栈 Stack
LIFO · Last In, First Out —— 后进先出
栈顶 TOP ↑
还空着
栈是空的，先放一个数字进去。
星图 · 活页
数据如何拥有秩序
数据结构的五个小实验：把数字压进栈、排进队列、串成链表，把一棵树按四种顺序走一遍，再看冒泡排序怎么把乱序推回正轨，最后做三道题验一验。
讲义 · 数据结构
数据很多。秩序从哪儿来？
数据结构不是一张要背的名词表，而是组织信息、安排操作次序的一套想法。下面五个实验都能动手—— 凡是能点、能按的地方都试一遍，比死记“先进先出”四个字有用得多。
栈与队列：顺序决定规则
两种结构都能装下一串数据，区别只在取出的顺序。往里面放几个数字试试。
一句话分清：栈像一摞盘子，最后放上去的最先拿走；队列像排队买票，先来的人先离开。
⇥ 队列 Queue
FIFO · First In, First Out —— 先进先出
队首 →122436→ 队尾
队首在左，队尾在右。
链表：让节点彼此相连
数组把元素摆在连续的内存里；链表由节点组成，每个节点存着数据，另存一个指向下一个节点的引用。
动手接一条链表
加节点、删头节点，看 HEAD 指向怎么跟着变。
HEAD →369→ NULL
每个节点只需要知道下一个节点在哪里。
数组与链表，各有所长
没有绝对的赢家，只有合不合适。
数组 按下标取元素很快：O(1)
但在中间插入或删除，往往要把后面的一大串挪位置。
链表 已知位置时改连接很方便：O(1)
但要找第 k 个元素，通常只能从头一个个走过去：O(n)。
记住这个画面
链表不是“挨在一起”，而是“指向彼此”。
顺着 next 一路走，就能访问到整条链；代价是没法“跳着看”。
树：把层级关系摊开
文件夹、组织架构、语法分析，都能用树来描述。遍历就是约定一套次序，把每个节点都访问一遍。
二叉树遍历实验
换一种次序，看同一棵树被访问的先后如何变化。
前序遍历
先访问根节点，再遍历左子树，最后遍历右子树。可以用来复制一棵树。
播放后，这里按访问顺序排出节点。
顺带一提：二叉搜索树满足“左子树都更小、右子树都更大”，对它做中序遍历，得到的正好是有序序列。
排序实验室：看算法怎么干活
同一组数字，不同的比较与交换策略会走出不同的路径。这里用冒泡排序看相邻元素如何一步步归位。
冒泡排序 Bubble Sort
比较相邻两项，顺序不对就交换。一轮下来，最大的那个会被推到最右边。
点「下一步」，看算法先比较哪两个数字。朱砂实心表示正在比较的两个，浅朱砂表示已经归位的那一段。
已归位正在比较第 0 轮
检查一下，真的理解了吗
不用背定义，拿刚才动手的经验回答就好。三道题，选完立刻给解析。
答对 0 题选一个你认为对的。
问题 1 / 3栈中依次压入 A、B、C，第一次出栈会得到什么？
栈遵循后进先出（LIFO），最后压入的 C 正位于栈顶，所以最先被拿走。
问题 2 / 3如果需要频繁按下标读取第 k 个元素，通常哪个结构更合适？
数组支持按下标直接定位，访问时间通常是 O(1)；链表一般要逐节点走过去。
问题 3 / 3遍历一棵有 n 个节点的二叉树，至少要访问多少个节点？
完整遍历要每个节点访问一次，因此时间复杂度是 O(n)——这是它的下界。
三道都答完，按钮会变成重新练习。
把这些收进工具箱
挑结构时别先问“哪个最厉害”，先问“我最频繁的操作是什么”。
顺序本身就是规则
栈和队列存的是同一批数据，差别只在“谁先离开”。选之前先问自己：我要按什么顺序取？
挨在一起，还是指向彼此
数组按下标直达，链表靠指针串门。频繁按下标读用数组，频繁在两头增删用链表。
遍历是访问的次序
同一个结构，换一种遍历就换一种视角。排序则是用比较和交换，把无关紧要的次序试出来。