数据结构入门：栈、队列与链表一次讲清

数据结构说白了就是“数据怎么排队、怎么存取”。同样的信息，排法不同，取用速度和麻烦程度就完全不同。新手先搞懂三个最基础的就够了：栈、队列、链表。

栈是“后进先出”。像一摞盘子，只能从最上面放、也只能从最上面拿，后放的反而先出来。浏览器后退、编辑器撤销、函数调用，都是栈在工作：点开一个页面就压进栈，点后退就弹出最近那个。栈只关心栈顶，操作简单，但想取中间某个元素就得先把上面的全弹出来，不适合随机取用。

队列是“先进先出”。像排队买票，先来的人先办完走，后来的人在队尾等着。打印任务、消息排队、操作系统调度，都是队列：任务按到达顺序一个个处理，谁也不插队。队列只关心队头和队尾，取中间同样不方便，但公平性是它的优点。

链表是“一串用绳子连起来的盒子”。每个节点存两样东西：自己的数据，和下一个节点的地址。想在中间插入一个新节点，只要改两根“绳子”的指向，不用像数组那样把后面所有元素往后挪。代价是找第 n 个元素必须从头一个一个数过去，不能像数组那样直接按下标跳到位置，查找慢，插入删除快。

三者怎么选，看操作而不是看名字：只在同一端进出、要撤销和回退，选栈；按到达顺序公平处理，选队列；频繁在中间插入删除、不常按位置随机访问，选链表。如果经常按下标随机取，第 n 个元素一秒就要拿到，那数组更合适，别硬套链表。

一句话总结：栈管后进先出，队列管先进先出，链表管灵活增删。先分清“取用顺序”和“增删位置”这两个需求，再选结构，就不容易选错。