《Algorithms》(4th Edition)学习笔记——背包、队列和栈

 背包是一种不支持从中删除元素的集合数据类型——它的目的就是帮助用例收集元素并迭代遍历所有收集到的元素（用例也可以检查背包是否为空或者背包中元素的数量）。其中，迭代的顺序不确定并且与用例无关。可以这样理解背包，不透明的布袋里放入各式各样的小球，一次放入一个，取出时也是一次取一个，取出顺序与放入顺序并无关系，这一点与后面的队列、栈有区别。

 先进先出队列（习惯性称为队列）是一种基于先进先出（FIFO，即first in first out）策略的集合类型，是一种特殊的线性表，其插入和删除操作分别在线性表两端进行。可想象为日常生活中的排队购票，先来的人先买完成后从队伍头离去，后来的人从队伍末尾进队。入列顺序与出列顺序相同是队列特点之一。队列除去用链表实现的情况外，可采用顺序队列、顺序循环队列，除此之外还有一种特殊的优先队列（队列中的每个元素都有一个优先级，每次出队的是具有最高优先级的元素）。下面讨论顺序队列与顺序循环队列。顺序队列使用数组，会存在假溢出的情况，如下图

而顺序循环队列呢，可扩充队列容量

至此，队列都在用顺序存储，下面试试链式存储，这就不得不提一个重要的知识点——链表，个人认为链表非常容易操作（虽然在一些问题上比较麻烦，比如寻找特定位置的数据，链表须从头遍历因此运行时间会变长）。基于链表数据结构实现Queue其实很简单，它将队列表示为一条从最早插入的元素到最近插入的元素的链表，实例变量first指向队列的开头，实例变量last指向队列的结尾，如果一个元素入队，就将他添加到表尾，并更新last的值，出队只需更新first值即可（first = first.next）。

 下压栈（习惯性成为栈），是一种基于后进后出（LIFO）策略的集合类型，对栈的形象解释可理解为桌子上的一摞文件。栈还有一种运用即浏览网页：点击一个超链接，浏览器会显示一个新的页面（并将其压入一个栈），你可以不断点击链接访问新的页面，但总是可以通过（退后）回到以前的页面（从栈弹出）。在计算机领域，栈具有基础而深远的影响，算术表达式求值（Dijkstra的双栈算术表达式求值算法），下一篇将说明。