一、四件套的性格说明书

数组：一排连续格子。强项＝按下标直达；弱项＝中间插队要整体挪。 链表：散落的格子＋【下一格地址】牵手。强项＝插入删除只改牵手；弱项＝只能顺藤摸瓜。 栈：只有一个口的塔。后进先出（LIFO）。 队列：两头开的管道。先进先出（FIFO）。 往后还有树（分层）与哈希表（按内容直达）——四件套是它们的地基。

二、摆法决定本领

同一批数据，摆法不同，能快做的事完全不同： 要【随机访问第 N 个】——数组一步到；要【频繁插删】——链表改牵手；要【恢复最近操作】——栈（撤销键就是它）；要【保先来后到】——队列（打印队列就是它）。 所以选结构先问三个问题：查得多还是改得多？先进先出还是后进先出？要不要保持顺序？

三、结构选型是权衡不是背诵

没有全能冠军：数组的直达换来了插删慢，链表的灵活换来了查找慢。 工程里的真实做法：按主要操作选结构，为次要操作付代价。【三本账】（查找、插删、内存）在心里过一遍，选型自然浮出。

四、动手 Demo：四件套性格对照表

把四种结构连同口子、次序、应用列成一张总表——本章的【随身地图】。

# 四件套速查
ds = [("数组", "下标直达"), ("链表", "牵手慢行"),
      ("栈", "后进先出"), ("队列", "先进先出")]
for name, character in ds:
    print(name, "->", character)

实跑输出：

--------------------------------------------------------------------
要点 4——典型数据结构四件套
--------------------------------------------------------------------

数据结构＝数据的【摆法】。四种典型摆法各有一种性格：

  结构     摆法              进出规矩           生活类比
  -----------------------------------------------------------
  数组     一排连续格子      按下标直达         剧院一排座位
  链表     散落格子+牵手     顺藤摸瓜逐个走     寻宝游戏线索
  栈       叠盘子            后进先出 LIFO      食堂餐盘塔
  队列     排队伍            先进先出 FIFO      排队买票

摆法决定本领，本领决定用途：
    数组 -> 随机访问快（二分查找的舞台）
    链表 -> 插入删除快（不用整体挪动）
    栈   -> 记【最近发生】的事（撤销、函数调用）
    队列 -> 保【先来后到】的序（打印、消息队列）

第六章的其余要点就是把这四样逐个拆开看实现。

Python 里四种都有对应物：列表、自己串的节点、列表当栈、双端队列——但概念先于语法。 第六章剩余的 6.5~6.7 就是把这四样逐个【拆开看零件】。

30 秒实验

1. 给【撤销功能】【打印机任务排队】各选一种数据结构并说理由（栈／队列）。
2. 想一想通讯录该用哪个：查得多选数组，加删多选链表——你的通讯录是哪种用法？

常见误区

1. 以为有【最好的数据结构】——只有最合适的，权衡没有全能冠军。
2. 把栈和队列的次序记反——用【叠盘子】和【排队买票】的画面记，不忘。

• ☐ 下一节（6.5 要点5：了解栈和队列的实现方法）

相关笔记

• 特殊的程序流程——中断处理 — 栈保存现场的老朋友
• 🗄️ 数据库基础 · 索引 — 索引与 B 树是数据结构的进阶舞台
• 💻 计算机是怎样跑起来的 · 索引