【读书笔记】数据结构与算法之美 第2章 数组、链表、栈和队列
《数据结构与算法之美》，王争 著
标签：数据结构、算法
第2章 数组、链表、栈和队列
第一部分：数组
作者在数组这个小节，本书从工程或应用的角度出发介绍了一些内容：
数组的定义（这一节的点评，下面统一说）
寻址公式和随机访问特性：其中特别指出数组中定位操作的时间复杂度是O(1)，而不是查找操作的时间复杂度是O(1)。
低效的插入和删除操作
警惕数组访问越界问题。这个内容有意思，喜欢动手运行程序的读者，可以把代码执行一下，看看是否如作者所说。
容器能否完全替代数组：比较了编程语言提供的容器类和数组的适用性。
数据结构中的数组和编程语言中的数组的区别：作者简单描述了C/C++、Java和JavaScript三种编程语言中数组数据类型的区别。
本节点评：介绍几种经典编程语言中容器、和数组数据类型的区别，以及和数据结构中数组的区别非常好，从工程和应用的角度，可以丰富数据结构一般教材的不足（一般教材不注重应用性），对编程学习者，理论和实际都很重要，让数据结构能接地气。
文中有段话应该是作者的感悟，也是我很喜欢的，推荐给读者：“数据结构和算法的魅力就在于此，很多时候我们并不需要死记硬背某个数据结构或算法，而是要学习其背后的思想和处理技巧，这些东西才是最有价值的。如果读者细心留意，就会发现，无论是在软件开发还是架构设计中，总能找到数据结构和算法的影子”
下面我表达一下个人的观点
数组这个词，在数据结构、算法、和程序设计、编程软件开发这些领域中，经常出现，大家对数组的理解一般都不会有大的出错，但是这个词因为历史悠久且应用广泛，如果不搞清楚，对喜欢探究的初学者来说，为有一些困扰。
如果只是“数组”这个词，它代表了太多东西，要学习和理解数组，其实要加上很多前提约束，这样初学者就不会那么困惑了。
在数据结构领域里，线性结构是一种逻辑数据，线性表、栈和队列是具有线性结构的抽象数据类型（抽象在这里强调的数据集的结构关系）。在数据结构领域，数组是一种物理数据结构（物理在这里表示的是计算机可以支持或实现的结构），线性表可以基于数组来实现。
在程序设计领域中，数组表示一组连续的内存空间存储具有相同类型的数据。在不同的编程语言中真的实现数组数据类型时，由于编程语言设计的理念不同，不同编程语言中的数组数据类型是不同的，也不是完全遵循数据结构中的数组这个概念。而且随着编程语言的发展，还出现了容器，容器可以说是抽象数据类型的实例化。利用C++ STL中的vector，可以认为是线性表这种抽象数据类型的理念在C++中的实例化（不是数组的实例化）。
理解了程序设计（编程语言）中数组和数据结构中线性表（数组）的区别，
那么在学习数据结构线性结构部分时，为什么在数组中插入和删除操作效率低，就不难理解了。如果在程序设计领域，在数组中插入一个新的元素（删除一个元素），完全可以在O(1)的时间复杂度的方法实现。但是在数据结构领域，线性表或数组（这两个词，在很多数据结构教材中有点混用）因为要维持数据集中的线性结构特性，在插入和删除时才需要移动部分元素的位置。
简单说，如果只是程序设计中的数组，插入元素或删除数组中的某个元素，是不需要移动其他元素的。但是如果是用程序设计编程语言的数组来实现线性表（或数组），那么，插入和删除时才需要移动部分元素的位置。当然这都是理论上的（或者称为思想上的），到了具体的编程语言，程序设计中的数组理念，不同的编程语言可以针对编程语言自身的特点，进行相应的调整，实现出不同的数组数据类型；数据结构中的线性表（数组）理念，不同的编程语言可以实现出不同的数据类型或容器。
二、链表
作者在链表这个小节，从工程或应用的角度出发介绍了一些内容：
链表的底层结构：数组和链表的底层结构区别
链表的定义和操作
链表的变形结构：单链表、循环链表、双向链表
链表和数组的性能对比
基于链表实现LRU缓存淘汰算法
作者总结了6个编写链表相关代码的技巧。这一部分重点推荐。具体内容就不剧透了。
三、栈
作者在栈这个小节，从工程或应用的角度出发介绍了一些内容：
l栈的定义
顺序栈和链式栈
支持动态扩容的顺序栈
栈在函数调用中的应用
栈在表达式求值中的应用
栈在括号匹配中的应用
如何用栈实现浏览器的前进、后退功能
四、队列
作者在队列这个小节，从工程或应用的角度出发介绍了一些内容：
队列的定义
顺序队列和链式队列
循环队列
阻塞队列和并发队列
线程池如何处理请求一个线程
一般的数据结构教材中，栈和队列都说很重要，但是，本书作者在栈和队列部分介绍了很多应用的场景，虽然篇幅和细节不多，但是对于初学者来说，开拓视野，以及比简单地说教栈和队列很有用很常用要更加打动读者。
