数据结构 —— 数组、栈、队列、链表

数据结构 —— 数组、栈、队列、链表

编辑历史：
2018.7.3  小赖   文档初始化

数据结构是什么？

数据结构是在计算机为了组织数据的特定方式，目的是为了高效地使用数据。

数据结构提供不同的方式来存储数据，以便快速、动态地搜索、插入、移除、更新数据。列举一些常用的数据结构：

• 数组 （Array）
• 栈（Stacks）
• 队列（Queues）
• 链表（Linked Lists）
• 集合（Sets）
• 树（Trees）
• 图（Graphs）
• 哈希表（Hash Tables）

数据结构

数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。

1. 集合:数据结构中的元素之间除了“同属一个集合” 的相互关系外，别无其他关系；
2. 线性结构:数据结构中的元素存在一对一的相互关系；
3. 树形结构:数据结构中的元素存在一对多的相互关系；
4. 图形结构:数据结构中的元素存在多对多的相互关系。

概念介绍

数组

• 概念：数组是在内存中开辟一段连续的空间，并在此空间存放元素。
• 理解：就像是一层学生公寓，有20个房间，从01到50每个房间都有固定编号，通过编号就可以快速找到住房子的人。
• 特点：元素类型是固定的、长度是固定的、通过角标查询，查询快，增删慢。
• 时间复杂度：O(1）
• 空间复杂度：

图片示例：

15306884463884.jpg

图片解释：0，1... 代表的是角标。

栈

• 概念：栈是一种先入后出的线性结构，每次加入新的元素和拿走元素都在顶部操作。
• 理解：就像羽毛球盒，只有一个口，有顺序地进出，并且只能一端进与出，称为LIFO，先进后出或者后进先出，顾名思义就是先进去的就后出来，先进去的球会被后来的球不断的挤压，此举称之为压栈。
• 特点：1.遵循 后进先出（LIFO ）规则;2.有用于管理栈内内容的 push（add） 和 pop（remove） 方法;3.有一个 top 属性用于跟踪栈的大小以及当前栈顶位置。
• 时间复杂度：O(n）
• 空间复杂度：

图片示例：

15306897582599.jpg

链表

• 概念：链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。
• 类型：单链表，双链表，有序链表
• 理解：有一条街，小明住在街中一角，他有小红的地址，然后小红也是住在这条街，她有小花的地址，同样小花也有别人的地址。某天我想找小红玩，但是我不知道她住哪里，我可以问小明，就知道小红住在哪里了。那么小明小红小花这些人之间的关系就组成一个链表。
• 特点：1.链表存储的数据在地址空间上可连续，可不连续;2.链表中的每一个节点都包括数据和指向下一个地址的指针;3.方便数据的增删。
• 时间复杂度：O(n）

示例图片：

15306901103088.jpg
15306900584335.jpg

1. 单链表：就是小明只是右手握着小红的地址，他只有小红一个人的地址

2. 双链表：就是小明左手握着小白的地址，右手握着小红的地址，他有两个人的地址

3. 循环链表：就是小明握有小红的地址，小红握有小花的地址，而小花又握有小明的地址，这样就形成了一个循环

4. 有序链表：以某个标准，给链表的元素排序，比如比较内容大小、比较哈希值等

队列

• 概念：队列是一种先入先出的逻辑结构，对元素的操作分别在对头和队尾，元素的插入在对尾，元素的删除在对头

• 理解：就像是一条水管，有两端，有顺序地进出，并且只能一端进另一端出，称为FIFO，先进先出，顾名思义就是先进去的就先出来，如果你要删除，只能从出口端，一个一个的顺序删除，同理，要增加，也只能通过入口端顺序地添加进去。

• 特点：先进先出。

示例图片

未完待续。