背包、队列和栈

许多基础数据类型都和对象的集合有关。具体来说，数据类型的值就是一组对象的集合，所有操作都是关于添加、删除或是访问集合中的对象。

API

泛型可迭代的基础集合数据类型的API

背包

public class Bag<Item> implements Iterable<Item>| ----|---- Bag()|创建一个空背包 void add(Item item)|添加一个元素 boolean isEmpty()|背包是否为空 int size()|背包中的元素数量

先进先出（FIFO）队列

public class Queue<Item> implements Iterable<Item>| ----|---- Queue()|创建空队列 void enqueue(Item item)|添加一个元素 Item dequeue()|删除最近添加的元素 boolean isEmpty()|队列是否为空 int size()|队列中的元素数量

下压（后进先出，LIFO）栈

public class Statck<Item> implements Iterable<Item>| -----|----- Static()|创建一个空栈 void push(Item item)|添加一个元素 Item pop()|删除最近添加的元素 boolean isEmpty()|栈是否为空 int size()|栈中的元素数量

泛型

集合类的抽象数据类型的一个关键特性是我们应该可以用它们存储任意类型的数据，Java机制——泛型可以做到这点。

在每份API中，类名后的<Item>记号将Item定义为一个类型参数，它是一个象征性的占位符，表示的是用例将会用到的某种数据类型。

自动装箱

类型参数Item必须实例化为引用类型。原始数据类型的封装类型（Boolean、Byte、Character、Double、Float、Integer、Long和Short）就是原始数据类型所对应的引用类型。

Statck<Integer> statck=new Statck<Integer>();
statck.push(17);   //自动装箱（int -> Integer）
int i=statck.pop();   //自动拆箱（Integer -> int）

自动装箱：自动将一个原始数据类型转换为一个封装类型。 自动拆箱：自动将一个封装类型转换为一个原始数据类型。

可迭代的集合类型

例如用例在Queue中维护一个交易集合，如：

Queue<Transaction> collection=new Queue<Transaction>();

如果集合是可迭代的，用例用一行语句就可以打印出交易的列表：

for(Transaction t : collection)
{StdOut.println(t);}

背包

背包是一种不支持从中删除元素的集合数据类型——它的目的就是帮助用例收集元素并迭代遍历所有收集到的元素（用例也可以检查背包是否为空或者获取背包中的元素的数量）。迭代的顺序不确定且与用例无关。

先进先出队列

先进先出队列（或简称队列）是一种基于先进先出（FIFO）策略的集合类型。在应用程序中使用队列的主要原因是在用集合保存元素的同时保存它们的相对顺序：使它们入列顺序和出列顺序相同。

下压栈

下压栈（或简称栈）是一种基于后进后出（LIFO）策略的集合类型。在应用程序中使用栈迭代器的一个典型原因是在用集合保存元素的同时颠倒它们的相对顺序。

集合类数据类型的实现

定容栈

定容栈是一种表示容量固定的字符串栈的抽象数据类型。它只能处理String值，它要求用例指定一个容量且不支持迭代。

public class FixedCapacityStackOfStrings| ----------------------------------------|--- FixedCapacityStackOfStrings(int cap)|创建一个容量为cap的空栈 void push(String item)|添加一个字符串 String pop()|删除最近添加的字符串 boolean isEmpty()|栈是否为空 int size()|栈中的字符串数量

泛型

实现一个泛型的栈：