算法(4th ed)(120):基础——背包、队列和栈 5.1.5

阅读数:10 2019 年 11 月 6 日 07:29

算法(4th ed)(120):基础——背包、队列和栈 5.1.5

(API:先进先出队列)

先进先出队列(或简称队列)是一种基于先进先出(FIFO)策略的集合类型,如图 1.3.2 所示。按照任务产生的顺序完成它们的策略我们每天都会遇到:在剧院门前排队的人们、在收费站前排队的汽车或是计算机上某种软件中等待处理的任务。任何服务性策略的基本原则都是公平。在提到公平时大多数人的第一个想法就是应该优先服务等待最久的人,这正是先进先出策略的准则。队列是许多日常现象的自然模型,它也是无数应用程序的核心。当用例使用foreach 语句迭代访问队列中的元素时,元素的处理顺序就是它们被添加到队列中的顺序。在应用程序中使用队列的主要原因是在用集合保存元素的同时保存它们的相对顺序:使它们入列顺序和出列顺序相同。例如,下页的用例是我们的In 类的静态方法 readInts() 的一种实现。这个方法为用例解决的问题是用例无需预先知道文件的大小即可将文件中的所有整数读入一个数组中。我们首先将所有的整数读入队列中,然后使用 Queuesize() 方法得到所需数组的大小,创建数组并将队列中的所有整数移动到数组中。队列之所以合适是因为它能够将整数按照文件中的顺序放入数组中(如果该顺序并不重要,也可以使用 Bag 对象)。这段代码使用了自动装箱和拆箱来转换用例中的 int 原始数据类型和队列的 Integer 封装类型。

算法(4th ed)(120):基础——背包、队列和栈 5.1.5

图 1.3.2 一个典型的先进先出队列

复制代码
public static int[] readInts(String
name)
{
In in = new In(name);
Queue<Integer> q = new
Queue<Integer>();
while (!in.isEmpty())
q.enqueue(in.readInt());
int N = q.size();
int[] a = new int[N];
for (int i = 0; i < N; i++)
a[i] = q.dequeue();
return a;
}
Queue 的用例

评论

发布