共计 3253 个字符，预计需要花费 9 分钟才能阅读完成。
前言
上一篇：算法分析下一篇：基本排序
本篇内容主要是栈，队列 (和包)的基本数据类型和数据结构
在很多应用中，我们需要维护多个对象的集合，而对这个集合的操作也很简单
基本数据类型
对象的集合
操作：
insert — 向集合中添加新的对象
remove — 去掉集合中的某个元素
iterate — 遍历集合中的元素并对他们执行某种操作
test if empty — 检查集合是否为空
做插入和删除操作时我们要明确以什么样的形式去添加元素，或我们要删除集合中的哪个元素。
处理这类问题有两个经典的基础数据结构：栈(stack) 和队列(queue)
两者的区别在于去除元素的方式：
栈：去除最近加入的元素，遵循后进先出原则(LIFO: last in first out)。
插入元素对应的术语是入栈 — push；去掉最近加入的元素叫出栈 — pop
队列：去除最开始加入的元素，遵循先进先出原则(FIFO: first in first out)。
关注最开始加入队列的元素，为了和栈的操作区分，队列加入元素的操作叫做入队 — enqueue；去除元素的操作叫出队 — dequeue
此篇隐含的主题是模块式编程，也是平时开发需要遵守的原则
模块化编程
这一原则的思想是将接口与实现完全分离。比如我们精确定义了一些数据类型和数据结构(如栈，队列等)，我们想要的是把实现这些数据结构的细节完全与客户端分离。客户端可以选择数据结构不同的实现方式，但是客户端代码只能执行基本操作。
实现的部分无法知道客户端需求的细节，它所要做的只是实现这些操作，这样，很多不同的客户端都可以使用同一个实现，这使得我们能够用模块式可复用的算法与数据结构库来构建更复杂的算法和数据结构，并在必要的时候更关注算法的效率。
Separate client and implementation via API.
API：描述数据类型特征的操作 Client：使用 API操作的客户端程序。Implementation：实现 API 操作的代码。
下面具体看下这两种数据结构的实现
栈
栈 API
假设我们有一个字符串集合，我们想要实现字符串集合的储存，定期取出并且返回最后加入的字符串，并检查集合是否为空。我们需要先写一个客户端然后再看它的实现。
字符串数据类型的栈
性能要求：所有操作都花费常数时间客户端：从标准输入读取逆序的字符串序列
测试客户端
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
public static void main(String[] args)
{
StackOfStrings stack = new StackOfStrings();
while (!StdIn.isEmpty())
{
// 从标准输入获取一些字符串
String s = StdIn.readString();
// 如果字符串为 ”-“, 则客户端将栈顶的字符串出栈，并打印出栈的字符串
if (s.equals(“-“)) StdOut.print(stack.pop());
// 否则将字符串入栈到栈顶
else stack.push(s);
}
}
客户端输入输出：
栈的实现：链表
链表 (linked-list) 连接待添加 …
我们想保存一个有节点组成的，用来储存字符串的链表。节点包含指向链表中下一个元素的引用(first).
维持指针 first 指向链表中的第一个节点
Push：入栈，在链表头插入一个新的节点
Pop：出栈，去掉链表头处第一个节点
Java 实现
public class LinkedStackOfStrings
{
// 栈中唯一的实例变量是链表中的第一个节点的引用
private Node first = null;
// 内部类，节点对象，构成链表中的元素，由一个字符串和指向另一个节点的引用组成
private class Node
{
private String item;
private Node next;
}
public boolean isEmpty()
{return first == null;}
//
public void push(String item)
{
// 将指向链表头的指针先保存
Node oldfirst = first;
// 创建新节点：我们将要插入表头的节点
first = new Node();
first.item = item;
// 实例变量的 next 指针指向链表 oldfirst 元素，现在变成链表的第二个元素
first.next = oldfirst;
}
// 出栈
public String pop()
{
// 将链表中的第一个元素储存在标量 item 中
String item = first.item;
// 去掉第一个节点：将原先指向第一个元素的指针指向下一个元素，然后第一个节点就等着被垃圾回收处理
first = first.next;
// 返回链表中原先保存的元素
return item;
}
}
图示：
出栈：
入栈：
性能分析
通过分析提供给客户算法和数据结构的性能信息，评估这个实现对以不同客户端程序的资源使用量
Proposition 在最坏的情况下，每个操作只需要消耗常数时间(没有循环)。Proposition 具有 n 个元素的栈使用 ~40n 个字节内存(没有考虑字符串本身的内存，因为这些空间的开销在客户端上)
栈的实现：数组
栈用链表是实现花费常数的时间，但是栈还有更快的实现
另一种实现栈的 natural way 是使用数组储存栈上的元素将栈中的 N 个元素保存在数组中，索引为 n，n 对应的数组位置即为栈顶的位置，即下一个元素加入的地方
使用数组 s[] 在栈上存储 n 个元素。
push()：在 s[n] 处添加新元素。
pop()：从 s[n-1] 中删除元素。
在改进前使用数组的一个缺点是必须声明数组的大小，所以栈有确定的容量。如果栈上的元素个数比栈的容量多，我们就必须处理这个问题(调整数组)
Java 实现
public class FixedCapacityStackOfStrings
{
private String[] s;
//n 为栈的大小，栈中下一个开放位置，也为下一个元素的索引
private int n = 0;
//int capacity：看以下说明
public FixedCapacityStackOfStrings(int capacity)
{s = new String[capacity]; }
public boolean isEmpty()
{return n == 0;}
public void push(String item)
{
// 将元素放在 n 索引的位置，然后 n+1
s[n++] = item;
}
public String pop()
{
// 然后返回数组 n - 1 的元素
return s[–n];
}
}
int capacity：在构造函数中加入了容量的参数，破坏了 API，需要客户端提供栈的容量。不过实际上我们不会这么做，因为大多数情况下，客户端也无法确定需要多大栈，而且客户端也可能需要同时维护很多栈，这些栈又不同时间到达最大容量，同时还有其他因素的影响。这里只是为了简化。在调整数组中会处理可变容量的问题，避免溢出
对于两种实现的思考
上述的实现中我们暂时没有处理的问题：
Overflow and underflow
Underflow：客户端从空栈中出栈我们没有抛出异常
Overflow：使用数组实现，当客户端入栈超过容量发生栈溢出的问题
Null item：客户端是否能像数据结构中插入空元素
Loitering 对象游离：即在栈的数组中，我们有一个对象的引用，可是我们已经不再使用这个引用了
数组中当我们减小 n 时，在数组中仍然有我们已经出栈的对象的指针，尽管我们不再使用它，但是 Java 系统并不知道。所以为了避免这个问题，有效地利用内存，最好将去除元素对应的项设为 null，这样就不会剩下旧元素的引用指针，接下来就等着垃圾回收机制去回收这些内存。这个问题比较细节化，但是却很重要。
public String pop()
{
String item = s[–n];
s[n] = null;
return item;
}
调整数组
队列
泛型
迭代器
栈与队列的应用
附录