书名：图解数据结构与算法
ISBN：978-7-115-49828-1
本书由人民邮电出版社发行数字版。版权所有，侵权必究。
您购买的人民邮电出版社电子书仅供您个人使用，未经授权，不得以任何方式复制和传播本书内容。
我们愿意相信读者具有这样的良知和觉悟，与我们共同保护知识产权。
如果购买者有侵权行为，我们可能对该用户实施包括但不限于关闭该帐号等维权措施，并可能追究法律责任。
著 汪 建
责任编辑 傅道坤
人民邮电出版社出版发行 北京市丰台区成寿寺路11号
邮编 100164 电子邮件 315@ptpress.com.cn
网址 http://www.ptpress.com.cn
读者服务热线：(010)81055410
反盗版热线：(010)81055315
这是一本“少字多图”、以图描述原理、形象且易于理解的数据结构与算法图书。全书共分为7章，首先介绍了一些基础的数据结构，包括数组、链表、栈和队列等；然后通过例子来讲解递归和动态规划的算法思想；接着对树进行了讲解，包括二叉树、二叉搜索树、AVL树、红黑树、2-3树、B树以及Trie树等不同用途的树；在树的基础上讲解了堆，包括二叉堆、二项堆和斐波那契堆三种堆结构；还讲解了图结构，主要包括图的表示方式、图的遍历、图的最短路径以及最小生成树；最后讲解了比较排序和非比较排序，其中，比较排序包括选择排序、冒泡排序、插入排序、快速排序、希尔排序、合并排序和堆排序等，而非比较排序则包括计数排序、基数排序和桶排序等。
本书适合对数据结构和算法感兴趣并且想要通过一种轻松的方式学习和掌握数据结构与算法的读者阅读。无论他们是否有编程基础，均可看懂本书。
汪建（seaboat），毕业于广东工业大学光信息科学与技术专业，毕业后从事各类业务系统、中间件、基础架构和人工智能系统等方向的研发工作，目前致力于用AI来提升企业业务系统效率并节约人力成本。擅长工程算法、人工智能算法、自然语言处理、架构、分布式、高并发、大数据和搜索引擎等方面的技术，大多数编程语言都会使用，但更擅长Java、Python和C++。平时喜欢看书、写作和运动，擅长篮球、跑步、游泳、健身和羽毛球等运动项目。崇尚开源，崇尚技术自由，更崇尚思想自由。
个人博客为blog.csdn.net/wangyangzhizhou。大家也可以扫描下方二维码或在微信中搜索“远洋号”关注作者的个人公众号。
首先，感谢读者，您的阅读让本书变得更有价值。
其次，感谢在本书编写过程中帮助过我的人，特别是我的好兄弟“牛哥”，他对本书进行了详细认真的审阅，进而修正了一些错误并提出了很多宝贵的意见；感谢公司提供的平台让我得到了很多学习和成长的机会；感谢人民邮电出版社的傅道坤编辑一直以来给我提供的帮助和机会，并对本书提出了专业的意见。
再次，感谢旧金山大学的David Galles教授提供的visualization开源项目，该项目基于FreeBSD许可协议，本书很多示例都是基于该开源项目进行二次开发的。
最后，感谢一直鼓励、支持我的家人，他们让我的世界拥有更多的色彩。我的第一本书给了我帅气的儿子，而这本书给我可爱的女儿。
Linux内核之父林纳斯·托瓦兹（ Linus Torvalds）曾说过：“我认为一个优秀的程序员和一个不合格的程序员之间的区别在于，他是否将数据结构看得比代码更重要。不合格的程序员总是在关注代码，而优秀的程序员则会更看重数据结构。”Pascal之父及图灵奖获得者尼古拉斯·沃斯（Niklaus Wirth）也曾提出了一个著名的公式：算法+数据结构=程序。
由此可见，数据结构和算法才是程序的核心。对于程序而言，数据结构和算法都是缺一不可的，一个具有合适数据结构和优异算法的程序就像是一个艺术品。虽然数据结构和算法都无比重要，但现实情况却是很多工作了三五年的程序员并不重视数据结构和算法，他们所实现的程序往往运行效率低且难以维护。
随着面向对象思想的兴起，面向对象的编程语言将众多常用的数据结构和算法封装成了各种对象，比如不同种类的列表、集合、队列、树等。那么它们到底是如何实现的呢？实现的原理是什么？可能多数程序员都会回答：“不知道，反正编程语言已经提供了相关类，直接使用就行了。”对于编程语言，封装常用的数据结构和算法固然有很多好处，比如降低了使用成本，也大大降低了编码出错的概率。但封装同样会导致黑盒现象的产生，造成很多人在并不知道所用对象的具体实现原理的情况下，胡乱使用。
那么，数据结构是什么？算法又是什么？根据维基百科的定义，数据结构是一种数据组织、管理和存储的格式，它能提供有效的数据访问和修改操作。更准确地说，数据结构就是数据的集合，描述了各数据之间的关系，并提供了对这些数据的各种操作。而算法是一组定义清晰的指令集合，用于解决某类问题或执行某种运算任务。算法应该在有限的空间和时间内进行表达，其运行从初始状态和初始输入开始，经过一系列有限而定义清晰的指令操作后，最终产生输出并终止于某个状态。
尽管目前已经存在几本经典的算法书籍，但这几本书籍都很厚，而且内容和要点相当多。对于不是专门写算法的程序员来说，他们更需要通过一种形象且更加容易理解的方式来学习数据结构和算法。对于常见的数据结构和算法的核心思想，程序员更应该从感性的角度来理解把握，从而能够在不同的场景中知道要使用怎样的数据结构和算法。作者希望不管是刚入行的程序员还是经验丰富的工程师，都能轻松领悟常见的数据结构和算法的精髓及思想。这也是本书的写作意图。
本书具备如下特点。
本书不与任何具体的编程语言绑定，而是注重用图解的方式来描述数据结构和算法的思想。所以不管是前端程序员还是后端程序员，不管使用的编程语言是JavaScript、Java、C++还是Python，都能够轻松阅读本书。
本书以读者能够轻松地从感性的角度来理解并掌握常用的数据结构和算法为目标，摒弃繁杂的学术式陈述，以通俗易懂的方式进行讲解，跟着执行示意图便能理解核心思想。
本书采用大量图解，对讲解的每个数据结构和算法的执行过程都给出了详细的步骤图，使读者能轻松理解各类数据结构和算法的思想。
本书所讲解的都是常见的数据结构和算法，能够帮助读者在实际项目开发中理解相关的实现原理。
本书脉络结构比较清晰，由简单到复杂，循序渐进。各知识点的连贯性比较强，对于基础知识也有补充说明，便于读者阅读。
本书通篇紧扣“少字多图”的写作方针，以图来描述与数据结构和算法相关的机制原理，目的是让读者能够轻松地从感性的角度来理解并掌握常用的数据结构和算法。全书共分为7章，具体介绍如下。
第1章 基础数据结构，介绍了一些基础的数据结构，包括数组、链表、栈和队列等，其中数组包括一维数组、二维数组、三维及更高维数组，链表包括单向链表和双向链表，栈包括基于数组的栈和基于链表的栈，队列包括基于数组的队列和基于链表的队列。
第2章 递归与动态规划，介绍了递归和动态规划的算法思想。递归思想主要以阶乘和斐波那契数列为例进行讲解，动态规划思想则主要以斐波那契数列和最长公共子序列为例进行讲解。
第3章 树，介绍了树这种常见的数据结构。根据不同的用途，树衍生出了多种不同的结构，包括二叉树、二叉搜索树、AVL树、红黑树、2-3树、B树以及Trie树等，其中分别介绍了这些树的结构、性质及与其相关的主要操作。
第4章 堆，介绍了堆数据结构，主要包括二叉堆、二项堆和斐波那契堆等。除了介绍各种堆的结构和性质外，还介绍了堆的相关操作。
第5章 图，介绍了图数据结构，主要包括图的表示方式、图的遍历、图的最短路径以及最小生成树。在图的表示方式中，主要介绍了邻接表和邻接矩阵两种方式；在图的遍历中，主要介绍了广度优先搜索和深度优先搜索；在图的最短路径中，主要介绍了Dijkstra和Floyd两种算法；在最小生成树中，主要介绍了Prim和Kruskal两种算法。
第6章 比较排序，介绍了多种常见的基于比较的排序算法，包括选择排序、冒泡排序、插入排序、快速排序、希尔排序、合并排序和堆排序等，其中分别介绍了它们的排序要点、排序性能、排序过程。
第7章 非比较排序，介绍了三种常见的非比较排序算法，包括计数排序、基数排序和桶排序，分别介绍了它们的排序要点、排序性能以及排序过程。其中，计数排序主要介绍了考虑稳定性的情况和不考虑稳定性的情况，基数排序主要介绍了基于计数排序的实现、基于桶排序的实现和MSD排序方式等。
假如你对数据结构和算法感兴趣，那么这本书适合你。
假如你已经从事编程工作好几年，却没有熟练掌握常见的数据结构和算法，那么这本书适合你。
假如你想轻松学习并理解数据结构和算法，那么这本书适合你。
假如你想顺利解答面试中常见的算法题，那么这本书适合你。
本书侧重于用图讲解数据结构和算法的核心思想，并未与具体的某种编程语言绑定在一起，因此没有编程基础或者只会某一门编程语言的读者也可以顺利地阅读本书。
对数据结构和算法已经很熟悉了还有必要看吗？有必要。本书附带了常见的数据结构和算法的要点，同时通过图片形象地描述了它们的执行过程，能使读者快速抓住要点，可作为常用数据结构和算法的查阅手册。
在本书交稿时，我仍在担心是否遗漏了某些知识点，本书的内容是否详细完整，是否能让读者有所收获，是否会因为自己理解的偏差而误导读者。受写作水平和写作时间所限，本书中难免存在谬误，恳请读者批评指正。
读者可将任何意见及建议发送到邮箱wyzz8888@foxmail.com，本书相关的勘误也会发布到我的博客上，欢迎读者通过邮件或博客与我交流。
本书由异步社区出品，社区（https://www.epubit.com/）为您提供相关资源和后续服务。
作者和编辑尽最大努力来确保书中内容的准确性，但难免会存在疏漏。欢迎您将发现的问题反馈给我们，帮助我们提升图书的质量。
当您发现错误时，请登录异步社区，按书名搜索，进入本书页面，单击“提交勘误”，输入勘误信息，单击“提交”按钮即可。本书的作者和编辑会对您提交的勘误进行审核，确认并接受后，您将获赠异步社区的100积分。积分可用于在异步社区兑换优惠券、样书或奖品。
我们的联系邮箱是contact@epubit.com.cn。
如果您对本书有任何疑问或建议，请您发邮件给我们，并请在邮件标题中注明本书书名，以便我们更高效地做出反馈。
如果您有兴趣出版图书、录制教学视频，或者参与图书翻译、技术审校等工作，可以发邮件给我们；有意出版图书的作者也可以到异步社区在线提交投稿（直接访问www.epubit.com/selfpublish/submission即可）。
如果您所在的学校、培训机构或企业，想批量购买本书或异步社区出版的其他图书，也可以发邮件给我们。
如果您在网上发现有针对异步社区出品图书的各种形式的盗版行为，包括对图书全部或部分内容的非授权传播，请您将怀疑有侵权行为的链接发邮件给我们。您的这一举动是对作者权益的保护，也是我们持续为您提供有价值的内容的动力之源。
“异步社区”是人民邮电出版社旗下IT专业图书社区，致力于出版精品IT技术图书和相关学习产品，为作译者提供优质出版服务。异步社区创办于2015年8月，提供大量精品IT技术图书和电子书，以及高品质技术文章和视频课程。更多详情请访问异步社区官网https://www.epubit.com。
“异步图书”是由异步社区编辑团队策划出版的精品IT专业图书的品牌，依托于人民邮电出版社近30年的计算机图书出版积累和专业编辑团队，相关图书在封面上印有异步图书的LOGO。异步图书的出版领域包括软件开发、大数据、AI、测试、前端、网络技术等。
异步社区
微信服务号
在计算机科学中，数组是我们最熟悉也是最基础的一种数据结构。通常地，数组由有限个相同数据类型的元素按顺序排列组合而成。数组的数据是连续的，并且会设定上界和下界，其中的每个元素都有属于它们自己的索引值（也称下标），通过这些下标就能定位到元素。对于绝大多数编程语言来说，数组的索引都是从0开始，但不排除有的编程语言从1开始。
几乎所有程序都会使用数组结构，而且很多其他的数据结构也可以由数组来实现，比如栈、队列、列表等。
根据维度的不同，数组可以分为一维数组、二维数组、三维数组等，以此类推。
在各种维度的数组中，一维数组是最简单的数组结构，通常它也被称为线性数组。
① 创建一个长度为10的数组。
② 将11、22、33、44四个数字放到数组中。
③ 再将“the”“monster”“is”“coming”四个字符串放到数组中，覆盖原来的前四个元素。
④ 获取数组下标为0和3所对应元素的字符串。
⑤ 数组大小为10，则下标范围为0～9，如果超出范围即越界，将会导致错误。
由于数学领域中的矩阵可以通过二维数组来表示，因此二维数组也被称为矩阵。此外，因为它是二维的结构，所以需要两个下标才能确定一个元素，即行下标和列下标。
① 创建一个3行10列的二维数组（矩阵），它一共可存放30个元素。
② 将“the”“monster”“is”“coming”四个字符串分别放到数组的(0,1)、(2,2)、(2,6)、(1,4)四个坐标上。
③ 获取二维数组(2,6)、(1,4)坐标中所保存的字符串。
数组的维度数可以看成是获取一个元素所需的索引数，比如一维数组需要一个索引，二维数组则需要两个索引。三维数组即由三个维度组成的数组，它是最常见的多维数组，由三个下标去描述数组中的元素，也就是说获取数组中的一个元素需要三个索引。
按照正常思维，我们常常会用现实世界中的三维空间来对应三维数组以进行理解，比如一维数组对应列表，二维数组对应方形表格，而三维数组对应的是立体空间表格。对于三维及三维以下的数组，这样理解没什么问题，但对于更高维度的数组，我们就很难用现实世界中相关的概念来对应四维、五维或更高维数组，所以这样的思维方式不利于我们理解更高维度的数组。
通常地，我们可以以索引的形式来理解数组，每个维度都可以看成是一层索引，三维的情况则可以看成如下的形式。
如果将“the”放到(0,1,2)坐标中，则如下图所示。
更高维度的数组则可以继续往上抽取一维，形成一种类似于树的结构。
链表是一种线性的数据集合。在链表中，每个节点都指向后继或前驱节点，也就是说每个节点都会包含数据和指针。链表中的节点在逻辑上是相连的，但在物理内存中却是不相连的，这种特性让链表拥有了高效的插入和删除操作。
总的来说，虽然链表实现的存储结构与传统数组的结构类似，但它也有一定的优势。其优势主要体现在两方面：其一，链表能够实现更高效的插入和删除操作；其二，较于数组，它能避免重新分配内存的情况，因为数组是有固定大小的，当数组内存不够使用时，则需要重新分配更大的内存。以上优势得益于链表的存储可以是非连续的内存空间，这样就允许在链表的任意位置进行插入和删除操作，并且能在常数的时间复杂度内完成。
当然，链表也有自己的缺点，具体如下。
比较常见的两类链表为单向链表和双向链表。
单向链表属于链表的一种，也叫单链表。单向是说它的链接方向是单向的，它由若干个节点组成，每个节点都包含了数据和后继节点指针next。单向链表主要的操作包括插入、删除和遍历。需要注意的是，头部节点head不保存任何数据（也可保存数据，但为了减少一些判断，这里不保存数据），只用于指向单向链表的第一个节点，并且整个链表的指针都指向一个方向。
单向链表的创建操作很简单，只需创建头部节点head即可。
现准备将“nobody”“grows”“old”“merely”“by”“a”“number”“of”“years”等字符串按顺序分别插入链尾。下面我们看看执行过程。
① 创建“nobody”节点。
② 将头部节点的next指针指向“nobody”节点，同时维护链表长度，此时为1。
③ 继续创建“grows”节点。
④ 将“nobody”节点的next指针指向“grows”节点，此时链表长度为2。
⑤ 创建“old”节点，并将“grows”节点的next指针指向“old”节点，此时链表长度为3。
⑥ 以此类推，将剩下的字符串分别创建节点并通过next指针连接起来，最终链表长度为9。
迭代器（iterator）也称为游标（cursor），属于一种设计模式。迭代器可以提供链表上的访问接口，进而遍历链表上的全部元素。下面我们看看迭代器的使用。
① 迭代器的当前位置指针current初始时指向头部节点head。
② 执行两次next操作后，current指针指向索引为2的节点。
③ 此时的节点值为“grows”。
④ 也可以直接设置current指针指向索引为4的节点，此时的节点值为“merely”。
单向链表的插入操作默认是在链尾插入节点，但如果使用了迭代器则可以指定插入的位置。下面准备在链表索引为1的位置后面插入“but”和“someone”两个节点，过程如下。
① 先将current指针指向索引为1的节点，然后创建一个新节点“but”。
② 接着根据current指针指向的位置将“but”节点插入到链表中，同时将“nobody”节点的next指针指向“but”节点，并将“but”节点的next指针指向“grows”节点。并且维护链表长度，此时为10。
③ 执行next操作，将current指针后移一个位置。
④ 创建一个新节点“someone”。
⑤ 根据current指针指向的位置将“someone”节点插入到链表中，同时将“but”节点的next指针指向“someone”节点，并将“someone”节点的next指针指向“grows”节点。此时链表长度为11。
删除操作的核心是将原本指向待删除节点的next指针改成指向待删除节点的next指针所指向的节点，然后废弃被删除的节点。另外，在删除之前需要先通过遍历找到待删除的节点。下面来删除“but”和“someone”两个节点，我们看看删除的过程。
① 首先找到“but”节点，从头部节点head开始遍历查找“but”节点，找到该节点后进行删除操作，这时只要将“nobody”节点的next指针指向“someone”节点即可。
② 然后将“but”节点废弃，同时维护链表的长度，此时为10。
③ 同样地，要删除“someone”节点需要先找到“someone”节点，从头部节点head开始遍历查找“someone”节点，找到该节点后进行删除操作，即把“nobody”节点的next指针指向“grows”节点。
④ 将“someone”节点废弃，此时链表长度为9。
双向链表属于链表的一种，也叫双链表。双向即是说它的链接方向是双向的，它由若干个节点组成，每个节点都包含了数据、后继节点指针next和前驱节点指针prev，所以从双向链表的任意节点开始，都能很方便地访问它的前驱节点和后继节点。双向链表主要的操作包括插入、删除和遍历。头部节点head不保存任何数据，它与双向链表的第一个节点互相指向对方，整个链表的指针可指向前后两个方向。
创建一个空的双向链表时只需创建头部节点head。
现准备将“the”“monster”“is”“coming”等字符串按顺序分别插入链尾。下面我们看看执行过程。
① 创建“the”节点。
② 将头部节点的next指针指向“the”节点，而“the”节点的prev指针指向头部节点，同时维护链表长度，此时为1。
③ 继续创建“monster”节点。
④ 再将“the”节点的next指针指向“monster”节点，而“monster”的prev指针指向“the”节点，此时链表长度为2。
⑤ 以此类推，将剩下的字符串分别创建节点并通过next指针和prev指针连接起来，最终链表长度为4。
迭代器可以提供链表上的访问接口，进而遍历链表上的全部元素。下面我们看看迭代器的使用。
① 迭代器的当前位置指针current初始时指向头部节点head。
② 执行两次next操作后，current 指针指向索引为2的节点。
③ 此时的节点值为“monster”。
④ 也可以直接设置current指针指向索引为3的节点，此时的节点值为“is”。
双向链表的插入操作默认是在链尾插入节点，但如果使用了迭代器则可以指定插入的位置。下面准备在链表索引为1的位置插入“big”节点，我们看看过程。
① 先将current指针指向索引为1的节点，然后创建一个新节点“big”。
② 接着根据current指针指向的位置将“big”节点插入到链表中，同时将“the”节点的next指针指向“big”节点，而“big”节点的prev指针指向“the”节点；将“big”节点的next指针指向“monster”节点，而“monster”节点的prev指针指向“big”节点。并且维护链表的长度，此时为5。
删除操作主要的核心是将原本指向待删除节点的next指针指向待删除节点的next指针所指向的节点，相应地，prev指针也要做相应的改变。接着废弃被删除的节点。另外，在删除之前需要先通过遍历找到待删除的节点。下面开始进行删除“big”节点的操作，我们看看过程。
① 首先找到“big”节点，从头部节点head开始遍历查找“big”节点，找到该节点后进行删除操作。
② 将“the”节点的next指针指向“monster”节点，同时将“monster”节点的prev指针指向“the”节点。
③ 然后将“big”节点废弃，同时维护链表的长度，此时为4。
由于双向链表的头部节点head和链尾没有连接关系，所以如果要访问最后一个节点就需要从头开始遍历，直到最后一个节点。为了改善这个问题，我们在双向链表的基础上将头部节点head的prev指针指向最后一个节点，而将最后一个节点的next指针指向head节点，便构成了双向循环链表。通过双向循环链表，我们可以很方便地从两个方向上对链表进行遍历，实际上它看起来就像是构成了一个环形。
栈（stack）也被称为堆栈，是一种运算受限的线性表。它添加元素和删除元素都被限制在表的一端，该端被称为栈顶，而另外一端则被称为栈底。
栈中的数据以后进先出（Last In First Out，LIFO）的方式进出栈，也就是说先进栈的元素后出栈，而后进栈的元素则先出栈。栈提供了两个主要操作：进栈（push），即将某个元素添加到栈集合内；出栈（pop），即将最近添加的元素移出栈集合。此外，栈一般具有特定的容量，如果栈中添加的元素总数超过了容量，则将会导致栈处于溢出状态。
栈的实现方式主要有两种：基于数组和基于链表。它们都提供了统一的接口，即进栈和出栈，唯一的区别就是使用了不同的结构来存储栈元素。
我们先看基于数组的栈的实现方式，该方式包含的三要素分别是数组、栈顶（top）指针以及栈操作集。其中数组用于存放元素，而栈顶指针用于指引操作的位置，栈的核心操作为进栈和出栈。此外，栈存放的元素数量不能超过数组的长度。
现准备对“the”“monster”“is”“coming”四个字符串分别进行进栈操作，下面我们看看整个过程。
① “the”进栈后，栈顶指针top右移一个位置，指向索引为1的位置。
② “monster”进栈后，栈顶指针top再右移一个位置，指向索引为2的位置。
③ “is”进栈后，栈顶指针top继续右移一个位置，指向索引为3的位置。
④ “coming”进栈后，栈顶指针top继续右移一个位置，最终指向索引为4的位置。
接着再对栈中的元素进行两次出栈操作。
① “coming”出栈后，栈顶指针top左移一个位置，指向索引为3的位置。
② “is”出栈后，栈顶指针top再左移一个位置，指向索引为2的位置。
接着继续看基于单向链表的栈的实现方式，该方式包含的三要素分别是链表结构、栈顶（top）指针以及栈操作集。链表结构用于存放元素，栈顶指针用于指引操作的位置，栈的核心操作为进栈和出栈。使用链表结构来存放栈元素可以不必担心容量的问题，而基于数组的栈所存放元素的数量则不能超过数组的长度。
初始时，栈顶指针不指向任何节点，且链表为NULL。
现准备对“the”“monster”“is”“coming”四个字符串分别进行进栈操作，下面我们看看整个过程。
① 因为链表为NULL，所以直接创建“the”节点，且栈顶指针指向该节点。
② 创建“monster”节点。
③ 将“monster”节点指向前一节点，并移动栈顶指针使其指向“monster”节点。
④ 创建“is”节点，并将该节点指向前一节点，栈顶指针指向“is”节点。
⑤ 创建“coming”节点，并将该节点指向前一节点，栈顶指针指向“coming”节点。
接着再对栈中的元素进行两次出栈操作。
① 取出栈顶元素“coming”，然后将栈顶指针前移一位。
② 废弃“coming”节点。
③ 同理，第二次出栈操作先取出“is”节点，然后将栈顶指针前移一位并废弃“is”节点。
队列（queue）是一种操作受限的线性表，通过该线性表所存储的元素具有顺序性。它的插入操作只被允许在表的后端进行，而删除操作则只被允许在表的前端进行。进行插入操作的端被称为队尾，而进行删除操作的端则被称为队头。
队列中的数据以先进先出（First In First Out，FIFO）的方式进出队列，也就是说先入队的元素先出队，而后入队的元素则后出队。队列提供了两个主要操作：入队（enqueue），即将某个元素添加到队列的尾部；出队（dequeue），即将队列里最先添加的元素移出队列。此外，队列一般还具有特定的容量，如果队列中添加的元素总数超过了容量，则将会导致队列处于溢出状态。
队列的实现方式主要有两种：基于数组和基于链表。它们都提供了统一的接口，即入队和出队，唯一的区别就是使用了不同的结构来存储队列元素。
我们先看基于数组的队列的实现方式，该方式包含的四要素分别是数组、队头（head）指针、队尾（tail）指针以及队列操作集。其中，数组用于存放元素，队头指针用于指引队头位置，队尾指针用于指引队尾位置，队列的核心操作为入队和出队。此外，队列所存放的元素数量不能超过数组的长度。
现准备对“the”“monster”“is”“coming”四个字符串分别进行入队操作，下面我们看看整个过程。
① “the”入队后，队尾指针tail右移一个位置，指向索引为1的位置。
② “monster”入队后，队尾指针tail再右移一个位置，指向索引为2的位置。
③ “is”入队后，队尾指针tail继续右移一个位置，指向索引为3的位置。
④ “coming”入队后，队尾指针tail继续右移一个位置，最终指向索引为4的位置。
我们可以看到在整个过程中队头指针head都不移动。
接着再对队列中的元素进行两次出队操作。
① “the”出队后，队头指针head右移一个位置，指向索引为1的位置。
② “monster”出队后，队头指针head再右移一个位置，指向索引为2的位置。
我们可以看到在整个过程中队尾指针tail都不移动。
由于数组的长度是固定的，我们从上面的执行过程可以看到，在不断进行入队和出队操作后两个指针都将一直往右移，那么，如果当指针到达数组最后位置时是不是就得重新创建数组呢？答案是不用。我们可以通过循环机制来重用数组，即把数组看成是首尾相连的，当到达尾部后，下次操作将重新回到首部。
前面已经执行了四次入队操作和两次出队操作，现在准备继续对6个“a”进行入队操作。在对5个“a”执行入队操作后，队尾指针tail已经到达了数组的尾部。此时，如果再对第6个“a”执行入队操作，则队尾指针tail将重新回到数组首部。
接着继续看基于单向链表的队列的实现方式，该方式包含的四要素分别是链表、队头（head）指针、队尾（tail）指针以及队列操作集。其中，链表用于存放元素，队头指针用于指引队头位置，队尾指针用于指引队尾位置，队列的核心操作为入队和出队。使用链表结构来存放队列元素时可以不必担心容量的问题，而基于数组的队列所存放的元素数量则不能超过数组的长度。
初始时，队头指针和队尾指针都不指向任何节点，且链表为NULL。
现准备对“the”“monster”“is”“coming”四个字符串分别进行入队操作，下面我们看看整个过程。
① 创建“the”节点，队头指针和队尾指针都指向该节点。
② 创建“monster”节点。
③ 将“the”节点指向“monster”节点，并移动队尾指针使其指向“monster”节点。
④ 创建“is”节点，并将“monster”节点指向该节点，队尾指针指向“is”节点。
⑤ 创建“coming”节点，并将“is”节点指向该节点，队尾指针指向“coming”节点。
接着再对队列中的元素进行两次出队操作。
① 取出队头元素“the”，然后将队头指针前移一位。
② 废弃“the”节点。
③ 同理，第二次出队操作先取出“monster”元素，然后将队头指针前移一位并废弃“monster”节点。
