背包、队列和栈的概念

最近读《算法（第四版）》，学习了背包（Bag）、队列（Queue）和栈（Stack），下面总结其相关概念。

背包、队列和栈都为一种数据类型。

数据类型指的是一组值和一组对这些值的操作的集合。比如 String 类是一种数据类型，其值为保存的字符串，其操作即 length()、charAt(int index) 之类的方法。

背包、队列和栈的值为一组对象的集合（与数组类似），其操作即添加、删除或是访问集合中的对象。它们的不同之处在于删除或者访问对象的顺序不同。

背包是一种不支持从中删除元素的集合数据类型——它的目的就是帮助用例收集元素并迭代遍历所有收集到的元素。迭代的顺序不确定（或者说不要求确定）。

队列（全称先进先出队列）是一种基于先进先出（FIFO）策略的集合类型。所谓“基于先进先出（FIFO）策略”，也就是先进入队列的元素先出来。正如一群人在排队领票，先进入队列的人排在前面，其领票也最早。当用例迭代访问队列中的元素时，元素的处理顺序就是它们被添加到队列中的顺序。在应用程序中使用队列的主要原因是在用集合保存元素的同时保存它们的相对顺序：使它们入列顺序和出列顺序相同。

栈（全称下压/后进先出栈）是一种基于后进先出（LIFO）策略的集合类型。所谓“基于后进先出（LIFO）策略”，也就是后进入栈的元素先出来。正如你在网上冲浪时点击一个超链接，浏览器会显示一个新的页面（并将它压入一个栈），你不断点击超链接并访问新页面，但总是可以通过点击“回退”按钮重新访问以前的页面，返回到的页面（从栈中出来的页面）总是最近浏览（最近进入到栈中）的页面。

下面是三种数据结构的 API：