为什么我们需要数据结构？
学习数据结构之前，我们可以先问一个很朴素的问题：
为什么我们需要数据结构？
假设没有任何结构，数据会是什么样子？
它可能就是一大堆散落的字符、字符串、数字。比如你现在有一百个人的信息，包括姓名和年龄，如果没有任何组织方式，它们可能长这样：
张三，李四，10岁，11岁，16岁，38岁，王二……
这当然也是“数据”，但它几乎没法被好好使用。
你很难知道：
张三到底几岁？
10岁对应的是谁？
王二在不在里面？
怎样增加一个新的人？
怎样删除一个人？
怎样找到年龄最大的人？
数据本身虽然存在，但它们之间没有清晰的关系，没有规则，也没有秩序。这样的数据就像把一百个人的档案全部撕开混在一起，名字一堆，年龄一堆，看起来都有信息，但真正用的时候非常痛苦。
所以我们需要数据结构。
简单来说：
数据结构就是为了把数据组织起来，让数据形成某种有逻辑的结构，从而便于存储、获取、修改和处理。
比如对于人的姓名和年龄，我们可以把它组织成这样：
[
{姓名: 张三, 年龄: 10},
{姓名: 李四, 年龄: 11},
{姓名: 王二, 年龄: 16}
]
这样一来，姓名和年龄就被绑定起来了。数据不再是散落的碎片，而是有了关系、有了层次、有了可操作的形状。
这就是数据结构最基本的意义。
数据结构不是为了“存”，而是为了“用”
很多初学者刚接触数据结构时，会觉得数据结构就是“存数据的东西”。
这个理解不算错，但还不够。
因为我们真正关心的不是单纯地把数据放进去，而是：
能不能方便地放进去？
能不能方便地拿出来？
能不能快速找到？
能不能删除？
能不能修改？
能不能按照某种规则管理它？
也就是说，数据结构服务的是具体需求。
常见需求包括：
插入
删除
查找
修改
遍历
获取最大值
获取最小值
判断是否为空
获取数据规模
而插入本身还可以继续细分，比如：
头部插入
尾部插入
中间插入
按照顺序插入
查找也可以有不同需求：
按下标查找
按值查找
查找最大值
查找最小值
查找某个范围内的数据
所以数据结构不是凭空出现的。它们之所以不同，是因为我们面对的数据使用需求不同。
你要频繁按位置访问，可能会想到数组。
你要频繁在中间插入删除，可能会想到链表。
你要先进先出地处理任务，可能会想到队列。
你要后进先出地撤销操作，可能会想到栈。
你要快速根据名字找到年龄，可能会想到哈希表。
数据结构的背后，其实始终是一个问题：
我接下来要怎样使用这些数据？
ADT：先规定“能做什么”，再考虑“怎么做”
为了描述不同的数据结构，我们通常会先定义一套行为规则。
这就是 ADT，Abstract Data Type，中文叫抽象数据类型。
ADT 关心的是：
一个数据类型应该支持哪些操作，这些操作应该表现出什么行为。
它暂时不关心底层到底怎么实现。
比如我们说“队列”这个东西，它的核心规则可能是：
add(x)：添加元素 x
remove()：移除下一个应该被移除的元素
注意，这里最关键的是“下一个应该被移除的元素”。
不同规则下，“下一个”是不一样的。
如果规定最早加入的元素最先被移除，那就是 FIFO 队列。
如果规定最后加入的元素最先被移除，那就是 LIFO 栈。
所以 ADT 像是在说：
你应该提供什么功能？
这些功能应该遵守什么规则？
而具体实现则是在说：
我用数组实现？
我用链表实现？
我用语言内置容器实现？
我怎样让它更快、更省空间？
因此可以这样理解：
ADT 定义行为。
具体实现决定性能。
这是学习数据结构时非常重要的一层抽象。
本次先讲两个ADT，Queue和List，后续会陆续出其它ADT的讲解。
Queue：从 add 和 remove 开始理解
我们先从一个很简单的抽象开始：
Queue
广义地说，Queue 可以理解为一种能提供下面两个操作的东西：
add(x)：添加元素 x
remove()：移除一个元素
但问题是：
remove() 到底应该移除谁？
这个问题一问出来，队列和栈的区别就出现了。
FIFO Queue：先进先出
FIFO 是 First In, First Out，也就是：
先进先出
它就像现实生活中的排队。
假设大家排队买奶茶：
张三先来
李四后到
王二最后来
那么服务的时候，应该是：
张三先被服务
李四第二个
王二最后
先进入队伍的人，先离开队伍。
这就是 FIFO Queue。
你可以把它想象成一条两端连通的通道：
入口 -> [ 张三 | 李四 | 王二 ] -> 出口
元素从一端进入，只能从另一端离开。
所以最先放进去的元素，会最先被取出。
这就是先进先出。
它通常支持的操作可以写成：
add(x)：把 x 加到队尾
remove()：从队头移除元素
比如：
add(张三)
add(李四)
add 王二
remove() -> 张三
remove() -> 李四
remove() -> 王二
队列非常适合处理“按顺序来”的场景，比如：
排队系统
打印任务
消息队列
广度优先搜索 BFS
操作系统中的任务调度
只要你看到“先来的先处理”，就可以想到 FIFO Queue。
LIFO Stack：后进先出
LIFO 是 Last In, First Out，也就是：
后进先出
它就是我们常说的栈。
栈像什么呢？
它像一个只有一个口的封底圆筒。
你把糖片一片片从上面放进去：
先放 A
再放 B
最后放 C
圆筒里大概是这样：
顶部
C
B
A
底部
现在你要拿糖片，只能从顶部拿。
所以你最先拿到的是 C，而不是 A。
也就是说：
最后放进去的元素，最先被取出。
这就是后进先出。
栈常见操作是：
push(x)：把 x 放到栈顶
pop()：移除并返回栈顶元素
top() / peek()：查看栈顶元素，但不移除
比如：
push(A)
push(B)
push(C)
pop() -> C
pop() -> B
pop() -> A
栈非常适合那些“最近发生的事情要最先处理”的场景，比如：
撤销操作
函数调用栈
浏览器后退
括号匹配
表达式求值
深度优先搜索 DFS
比如撤销操作就很像栈。
你先输入一句话，又加粗，又改颜色。现在你按撤销，当然应该先撤销“改颜色”，再撤销“加粗”，最后才撤销“输入文字”。
这就是典型的后进先出。
Deque：两头都能操作的队列
接下来是 Deque。
Deque 是 Double-ended Queue，也就是：
双端队列
它比普通 Queue 更灵活。
普通 FIFO Queue 通常是：
一端进，另一端出
而 Deque 是：
两端都可以进，两端都可以出
你可以把它想象成一根线上串珠子。
左边可以穿珠子，也可以取珠子。
右边也可以穿珠子，也可以取珠子。
它的典型操作是：
AddFirst(x)：把 x 添加到队列前端
AddLast(x)：把 x 添加到队列后端
RemoveFirst()：移除并返回前端元素
RemoveLast()：移除并返回后端元素
比如一开始 Deque 是空的：
[ ]
执行：
AddLast(A)
得到：
[ A ]
再执行：
AddLast(B)
得到：
[ A, B ]
再执行：
AddFirst(C)
得到：
[ C, A, B ]
这时候：
RemoveFirst() -> C
RemoveLast() -> B
Deque 的灵活性很强。它可以当普通队列用，也可以当栈用。
当作队列：
AddLast(x)
RemoveFirst()
当作栈：
AddLast(x)
RemoveLast()
所以 Deque 像是一个更通用的结构。
它常见于：
滑动窗口问题
双端搜索
需要两头插入删除的场景
实现栈或队列
一句话概括 Deque：
Deque 就是一条两端都开口的通道，元素可以从两头进，也可以从两头出。
List：按位置组织的一串元素
接下来是 List。
List 通常表示一种线性结构。
所谓线性结构，就是元素像排成一条线一样，一个接一个：
[ a0, a1, a2, a3, a4 ]
每个元素都有自己的位置，也就是下标：
0, 1, 2, 3, 4
List 的核心特点是：
元素之间有先后顺序，并且可以通过位置来访问和操作。
一个 List ADT 常见会规定这些操作：
Size()：返回列表长度 n
Get(i)：返回第 i 个位置上的元素
Set(i, x)：把第 i 个位置上的元素改成 x
Add(i, x)：在第 i 个位置插入 x
Remove(i)：删除第 i 个位置上的元素
比如现在有一个 List：
[ A, B, C, D ]
它的长度是 4：
Size() -> 4
获取下标 2 的元素：
Get(2) -> C
修改下标 1 的元素：
Set(1, X)
得到：
[ A, X, C, D ]
在下标 2 的位置插入 Y：
Add(2, Y)
得到：
[ A, X, Y, C, D ]
删除下标 3 的元素：
Remove(3)
得到：
[ A, X, Y, D ]
List 的抽象非常自然，因为我们日常生活中经常使用这种“有顺序的一串东西”。
比如：
购物清单
播放列表
学生名单
排行榜
文章段落
任务列表
它们都有一个共同特点：
元素是一个接一个排列的。
元素之间有顺序。
我们经常需要按位置访问、插入、删除、修改。
List 的两种常见实现：数组和链表
List 是一种 ADT，它规定了应该支持哪些操作。
但是它不规定底层必须怎么实现。
所以 List 有很多实现方式，其中最常见的是：
数组实现
链表实现
尤其常见的是：
ArrayList
LinkedList
或者在 C++ 中，可以类比为：
vector
list
不过要注意，它们虽然都可以用来表示“一串有顺序的数据”，但底层结构完全不同，因此性能差别很大。
用数组实现 List
数组实现的 List，可以想象成一排连续的格子：
[ A ][ B ][ C ][ D ][ ][ ]
每个格子都有编号，所以按下标访问非常快。(初学者可能觉得比较神奇，实际上，数组之所以能够快速按下标访问，是因为数组变量通常保存的是第一个元素的起始地址，数组元素在内存中连续存储，且每个元素大小相同，因此可以根据起始地址和下标直接计算出目标元素的内存地址，而不需要逐个查找)
如果我要访问第 2 个元素：
Get(2)
计算机可以直接跳到第 2 个位置。
所以数组实现 List 的一个重要优点是：
按下标访问快
通常可以做到：
Get(i)：O(1)
Set(i, x)：O(1)
但是它的缺点也很明显。
如果你要在中间插入一个元素，比如在 B 和 C 之间插入 X：
[ A ][ B ][ C ][ D ]
插入后应该变成：
[ A ][ B ][ X ][ C ][ D ]
那么 C 和 D 都需要往后挪。
如果后面有很多元素，就要挪很多次。
所以数组实现的 List：
中间插入慢
中间删除慢
按下标访问快
它适合的场景是：
经常按位置访问
很少在中间插入删除
数据整体比较连续
用链表实现 List
链表则完全不同。
链表不是一排连续的格子，而是一颗颗珠子，每颗珠子里面除了存数据，还会存“下一颗珠子在哪里”。
如果是双向链表，每颗珠子还会知道：
前一颗在哪里
后一颗在哪里
它大概像这样：
A <-> B <-> C <-> D
这就是 doubly-linked list，双向链表。
链表的优点是插入删除很灵活。
比如你要在 B 和 C 之间插入 X，只需要改变几个连接关系：
A <-> B <-> X <-> C <-> D
不需要像数组那样把后面一大堆元素整体搬家。
所以链表在某些插入删除场景下很有优势。
但是链表也有缺点。
如果你想访问第 100 个元素，链表不能像数组那样直接跳过去。
它只能从头开始，一个一个往后找：
第 0 个
第 1 个
第 2 个
……
第 100 个
所以链表：
按下标访问慢
已知位置时插入删除快
它适合的场景是：
经常插入删除
不太需要频繁随机访问
数据规模变化频繁
同一个 ADT，可以有不同实现
这就是数据结构里非常重要的一个思想：
同一个 ADT 可以有不同实现，而不同实现的性能可能差别非常大。
比如 List 这个 ADT 规定：
Size()
Get(i)
Set(i, x)
Add(i, x)
Remove(i)
但是它可以用数组实现，也可以用链表实现。
数组实现时：
Get(i) 很快
Set(i, x) 很快
中间 Add / Remove 可能较慢
链表实现时：
随机 Get(i) 较慢
但如果已经定位到节点，插入删除很方便
它们对外都可以叫 List，但内部完全不是一回事。
这就像你都可以从北京去上海：
坐高铁
坐飞机
开车
骑车
目标一样，方式不同，成本和速度也完全不同。
ADT 规定的是“你能去上海”。
具体实现决定的是“你怎么去、多久到、花多少钱”。
语言中的容器，本质上就是封装好的数据结构
在真实编程中，我们很多时候并不会从零开始手写数据结构。
因为大多数语言已经帮我们封装好了。
比如 C++ 中常见的容器有：
vector
list
deque
queue
stack
map
set
unordered_map
unordered_set
priority_queue
它们背后其实就是各种数据结构和 ADT 的具体实现。
比如：
vector：动态数组
list：双向链表
deque：双端队列
queue：队列适配器
stack：栈适配器
unordered_map：哈希表
map：通常是平衡搜索树
所以现实编程中，我们经常不是先问：
我要不要自己实现一个数据结构？
而是先问：
我的数据需要什么行为？
我最常做什么操作？
我更关心查找、插入、删除，还是有序性？
然后再选择合适的容器。
比如：
如果你需要一串元素，经常按下标访问：
vector
如果你需要先进先出：
queue
如果你需要后进先出：
stack
如果你需要两头都能插入删除：
deque
如果你需要根据 key 快速查找 value：
unordered_map
如果你需要数据自动保持有序：
map
set
这就是数据结构在现实编程中的使用方式。
学数据结构，学的到底是什么？
很多人学数据结构时，会陷入一种误区：
我要背会所有操作。
我要记住所有代码。
我要把每种结构都手写一遍。
当然，能实现它们很重要。
但更核心的是：
理解每种数据结构的组织规则，以及这种规则带来的能力和代价。
比如你学 Queue，不只是记住 add 和 remove，而是要理解：
它是一种先进先出的秩序。
它适合处理按到达顺序排队的问题。
你学 Stack，不只是记住 push 和 pop，而是要理解：
它是一种后进先出的秩序。
它适合处理最近发生的事情。
你学 Deque，不只是记住 AddFirst 和 RemoveLast，而是要理解：
它把两端都开放了，所以更灵活。
你学 List，不只是记住 Get、Set、Add、Remove，而是要理解：
它是一串有顺序的元素。
不同实现会影响访问、插入、删除的效率。
所以学习数据结构，其实是在学习三件事：
第一，数据可以怎样被组织。
第二，这种组织方式支持哪些操作。
第三，这些操作的时间和空间成本是多少。
最后总结
数据结构存在的原因很简单：
数据如果没有结构，就只是散乱的信息；有了结构，才变成可以被高效使用的资源。
ADT 则帮助我们先从抽象层面定义一种结构应该具备的行为。
比如：
Queue 关注 add 和 remove，并根据 remove 的规则分出 FIFO 和 LIFO。
Deque 允许两端插入和删除。
List 关注按位置组织元素，并支持 Get、Set、Add、Remove 等操作。
而具体实现则决定这些操作到底快不快、占多少空间、适合什么场景。
同一个 ADT 可以有多种实现。
同一种需求也可能有多种数据结构可以选择。
所以真正学会数据结构，不是死记硬背某个容器的名字，而是能在看到问题时想清楚：
我的数据是什么？
我最常做什么操作？
我需要什么规则？
我能接受什么性能代价？
当你能这样思考时，数据结构就不再是一堆抽象名词，而会变成你组织问题、驾驭复杂性的工具。
