《algorithms》摘录评注之贰：栈和队列

本笔记基于ROBERT SEDGEWICK & KEVIN WAYNE开设的《Algorithms》课程，同时配有同名教材。
slides本身内容丰富详实，所以我会先甄选出重点的篇幅整理出来并做简单批注，后续会添上对应算法题的演示。

栈和队列是两种基本的数据结构类型，它们有不同的方式去对存储的数据进行操作。
具体操作有：插入（push）、移除（pop）、迭代（iterate）以及检查是否为空等。
两者的差别主要是数据的移动顺序：
栈：后进先出
队列：先进先出

栈的链表实现：


栈的数组实现：

正如我们在数组实现这里所看到的，我们定义的数组容量是有限的，那么就会存放的元素就会出现“上溢”（数组放不下，要满溢出来了）或“下溢”（数组已经空了，还进行操作）的情况，所以我们需要一种“伸缩自如”的机制来防止这种溢出情况的发生，称为“resizing-array”。



其具体实现方法：
“伸”：如果原来的数组已满，那么创建一个新数组，容量为原来的两倍，同时把原来数组的元素拷贝进新数组。
“缩”：如果数组中的元素减少为容量的四分之一时，把数组容量减少为原来的一半。

可伸缩的数组实现与链表实现对比：

队列的链表实现：

队列的数组实现：

栈的应用实例，非常常见：比如浏览网页/打开文件夹后使用“后退”（回到最近的位置，后进先出）等等。

每篇文章除特殊声明外均以 CC BY-NC-SA 4.0 协议发布，非商业用途可以在保留署名和来源的情况下任意转载。