背包、队列和栈——背包

有很多基础数据类型都和对象的集合有关。具体来说，数据类型的值其实就是一组对象的集合，所有的操作都是关于添加、删除或者访问集合中的对象。有三种数据类型：背包(Bag)、队列(Queue)和栈(Stack)。这三者的不同之处在于删除或者访问对象的顺序不同。这三种数据类型都非常基础并且应用广泛
1.3.1 API
一般我们对集合型的抽象数据类型的讨论从定义它们的API开始


如上表，每一份API都含有一个无参数的构造函数、一个向集合中添加单个元素的方法、一个测试集合是否为空的方法和一个返回集合大小的方法。Stack和Queue都含有一个能够删除集中的特定元素的方法。在后面的内容中我们将会解释这几份API反映出的两种Java特性：泛型与迭代。
1.3.1.1 泛型
集合类的抽象数据类型的一个关键特性是我们应该可以用它们存储任意类型的数据。一种特别的Java机制能够做到这一点，它被称作泛型，也叫做参数化类型。以Stack为例，类名后的<item>记号将Item定义为一个类型参数，它是象征性的占用符，表示的用例将会使用某种数据类型。可以将Stack<item>理解为某种元素的栈。在实现Stack时，我们并不知道Item的具体类型，但用例可以用我们的栈处理任意类型的数据，甚至是我们实现之后才出现的数据。创建栈的时候，用例会提供一种具体的数据类型：我们可以将Item替换为任意引用数据类型(Item出现的每个地方都是如此)，这种能力正是我们需要的。
如果没有泛型，我们就必须为需要收集的每种数据类型定义（并实现）不同的API。有泛型之后我们就只需要一份API（和一次实现）就能处理所有类型的数据，甚至是在未来定义的数据类型。
1.3.1.2 自动装箱
类型参数必须实例化为引用类型，因此Java有一种特殊机制来使泛型能够处理原始数据类型。我们在之前说到过Java的封装类型都是原始数据类型所对应的引用类型：Boolean、Byte、Character、Double、Float、Integer、Long和Short分别对应boolean、byte、char、double、float、int、long和short。在处理赋值语句、方法的参数和算数或逻辑表达式时，Java会自动在引用类型和对应的原始数据类型之间转换。在这里这种转换有助于我们同时使用泛型和原始数据类型。例如：</item></item>

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

自动将一个原始数据类型转换为封装类型被称为自动装箱，自动将一个封装类型转换为一个原始数据被成为自动拆箱。在上面这个例子中，当我们将一个原始数据类型的值17传递给push()方法时，Java将它的类型自动转换（自动装箱）为Integer。pop()方法返回了一个Integer类型的值，Java在将它赋予变量i之前将它的类型自动转换（自动拆箱）为了int。
1.3.1.3 背包
背包是一种不支持从中删除元素的集合数据类型——它的目的就是帮助用例收集元素并迭代遍历所有收集到的元素（用例也可以检查背包是否为空或者获取背包中的元素数量）。迭代的顺序不确定且与用例无关。使用Bag的API，用例可以将元素添加进背包并根据需要随时使用foreach语句访问所有数据。用例也可以是栈或是队列，但使用Bag可以说明元素的处理顺序不重要。