背包、队列和栈

本文内容为《算法》第4版学习笔记。

背包

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

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

先进先出队列

先进先出队列（或简称队列）是一种基于先进先出（FIFO）策略的集合类型。任何服务性策略的基本原则都是公平。在提到公平时大多数人的第一个想法就是应该优先服务等待最久的人，这正是先进先出策略的准则。队列是许多日常现象的自然模型，它也是无数应用程序的核心。当用例使用foreach语句迭代访问队列中的元素时，元素的处理顺序就是它们被添加到队列中的顺序。在应用程序中使用队列的主要原因是在用集合保存元素的同时保存它们的相对顺序：使它们入列顺序和出列顺序相同。

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

下压栈

下压栈（或简称栈）是一种基于后进先出（LIFO）策略的集合类型。点击一个超链接，浏览器会显示一个新的页面（并将它压入一个栈）。你可以不断点击超链接并访问新页面，但总是可以通过点击”回退“按钮重新访问以前的页面（从栈中弹出）。栈的后进先出策略正好能够提供你所需要的行为。当用例使用foreach语句迭代遍历栈中的元素时，元素的处理顺序和它们被压入的顺序正好相反。

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

---

本文由 浩码农 创作，采用 CC BY-NC-SA 4.0 许可协议
本站文章除注明转载/出处外，均为本站原创或翻译，转载请务必署名

赏

我的娃的奶粉钱就看你们的打赏啦

支付宝

微信