外观
栈、队列和链表分别适合什么？
栈是后进先出，用来配对括号、做撤销和模拟递归。队列是先进先出，用来按顺序处理任务和广度优先遍历。链表用节点串起元素，插入删除不必搬移整段数组，但不能按下标 O(1) 访问。
原理
数组按下标访问是 O(1)，中间插入要搬移元素。单向链表要找到前驱才插得进去，查找是 O(n)。双向链表删除已知节点更快。前端的列表数据绝大多数用数组，因为需要按下标渲染，引擎对数组也更友好。
栈可以用数组的 push 和 pop。队列如果只用 shift，头部删除是 O(n)。流量大时用双栈或环形缓冲区，面试里说明复杂度即可。
链表题的常见操作是反转、找环、合并有序链表。反转时用三个指针走一遍。找环用快慢指针。写的时候先画空链表和单节点，再写循环。
浏览器里的调用栈就是栈。任务排队、消息按顺序消费是队列。DOM 是树，不是链表，但遍历子节点时会用栈或队列。
追问
数组和链表怎么选？
要随机访问、数据量连续，用数组。要在已知位置频繁插入删除、又很少随机访问，链表在教科书里更合适。实际工程先用数组，测量出搬移成本后再换结构。
循环队列解决什么？
固定容量里复用空出来的槽位，入队出队都是 O(1)，并且不会无限增长。要处理队满和队空的区分，通常多留一个空位或单独记长度。
易错点
shift当队列用，却把复杂度说成 O(1)。- 反转链表时丢掉下一个节点的引用。
- 在没有尾指针的链表末尾插入，却说是 O(1)。