一，队列
与栈一样，队列也是最基本的数据结构之一。队列也是对象的一种容器，其中对象的插入和删除遵循“先进先出”（First-In-First-Out, FIFO）的原则--也就是说，每次删除的只能是最先插入的对象。因此，我们可以想象成将对象追加在队列的后端，而从其前端摘除对象。就这一性质而言，队列与栈堪称“孪生兄弟”。比如，在银行等待接受服务时，顾客们就会排成一个队列--最先到达者优先得到服务。再如，用球桶来乘放羽毛球时，所有的球也排成一个队列--你总是从一端将球取出，而从另一端把球放入。
二，队列ADT(AbstractDataType)
队列的抽象数据类型就是一个容器，其中的对象排成一个序列，我们只能访问和取出排在最前端（Front）的对象，只能在队列的尾部（Rear）插入新对象。正是按照这一规则，才能保证最先被插入的对象首先被删除（FIFO）。
队列ADT 首先支持下面的两个基本方法：
| 操作方法 | 功能描述 |
|---|---|
| enqueue(x) | 将元素x 加到队列末端 输入：一个对象 输出：无 |
| dequeue() | 若队列非空，则将队首元素移除，并将其返回否则，报错 输入：无 输出：对象 |
此外，与栈ADT 类似地，队列ADT 还支持如下的方法：
| 操作方法 | 功能描述 |
|---|---|
| getSize() | 返回队列中当前包含的元素数目 输入：无 输出：非负整数 |
| isEmpty() | 检查队列是否为空 输入：无 输出：布尔标志 |
| front() | 若队列非空，则返回队首元素（但并不移除）否则，报错 输入：无 输出：队头对象 |
队列的应用十分广泛，无论是商店、剧院、机场还是银行、医院，凡是按照“先到的客户优先接受服务”原则的场合，都可以利用队列这一数据结构来编排相应的服务。
三，基于定长循环数组的队列的实现
定义一个Queue 接口
/*
* 队列接口
*/
package dsa;
public interface Queue {
public int getSize();//返回队列中元素数目
public boolean isEmpty();//判断队列是否为空
public Object front()throws ExceptionQueueEmpty;//取队首元素（但不删除）
public void enqueue (Object obj)throws ExceptionQueueFull;//入队
public Object dequeue()throws ExceptionQueueEmpty;//出队
public void Traversal();//遍历
}
定义用到的两个异常：
一个Queue空异常
package dsa;
public class ExceptionQueueEmpty extends RuntimeException {
public ExceptionQueueEmpty (String err) {
super(err);
}
}
一个Queue满异常
package dsa;
public class ExceptionQueueFull extends RuntimeException {
public ExceptionQueueFull (String err) {
super(err);
}
}
循环数组
为了避免数组的整体移动，可以引入如下两个变量f 和r：
- f：始终等于Q 的首元素在数组中的下标，即指向下次出队元素的位置
- r：始终等于Q 的末元素的下标加一，即指向下次入队元素的位置
一开始，f = r = 0，此时队空。每次有对象入队时，将其存放于Q[r]，然后r 加一，以指向下一单元。对称地，每次有对象出队之后，也将f 加一，指向新的队首元素。这样，对front()、enqueue()和dequeue()方法的每一次调用都只需常数时间。
然而，这还不够。细心的读者或许已经注意到，按照上述约定，在队列的生命期内，f 和r 始终在单调增加。因此，若队列数组的容量为N，则在经过N 次入队操作后，r 所指向的单元必然超出数组的范围；在经过N 次出队操作后，f 所指向的单元也会出现类似的问题。
解决上述问题的一种简便方法，就是在每次f 或r 加一后，都要以数组的长度做取模运算，以保证其所指单元的合法性。就其效果而言，这就相当于把数组的头和尾相联，构成一个环状结构。
具体的实现：
public class Queue_Array implements Queue {
public static final int CAPACITY = 1000;// 数组的默认容量
protected int capacity;// 数组的实际容量
protected Object[] Q;// 对象数组
protected int f = 0;// 队首元素的位置
protected int r = 0;// 队尾元素的位置
// 构造方法（空队列）
public Queue_Array() {
this(CAPACITY);
}
// 按指定容量创建对象
public Queue_Array(int cap) {
capacity = cap;
Q = new Object[capacity];
}
// 查询当前队列的规模
public int getSize() {
return (capacity - f + r) % capacity;
}
// 判断队列是否为空
public boolean isEmpty() {
return (f == r);
}
// 入队
public void enqueue(Object obj) throws ExceptionQueueFull {
if (getSize() == capacity - 1)
throw new ExceptionQueueFull("Queue overflow.");
Q[r] = obj;
r = (r + 1) % capacity;
}
// 出队
public Object dequeue() {
Object elem;
if (isEmpty())
throw new ExceptionQueueEmpty("意外：队列空");
elem = Q[f];
Q[f] = null;
f = (f + 1) % capacity;
return elem;
}
// 取（并不删除）队首元素
public Object front() throws ExceptionQueueEmpty {
if (isEmpty())
throw new ExceptionQueueEmpty("意外：队列空");
return Q[f];
}
// 遍历（不属于ADT）
public void Traversal() {
for (int i = f; i < r; i++)
System.out.print(Q[i] + " ");
System.out.println();
}
}
四，队列应用实例
- ** 循环分配器 **
队列结构很适于用来实现循环分配器：按照环形次序反复循环，为共享某一资源的一群客户（比如共享一个CPU 的多个应用程序）做资源分配。
算法：RoundRobin
{
e = Q.dequeue();
Serve(e);
Q.enqueue(e);
}
- ** Josephus 环 (约瑟夫环)**
孩提时的你是否玩过“烫手山芋”游戏：一群小孩围成一圈，有一个刚出锅的山芋在他们之间传递。其中一个孩子负责数数，每数一次，拿着山芋的孩子就把山芋转交给右边的邻居。一旦数到某个特定的数，拿着山芋的孩子就必须退出，然后重新数数。如此不断，最后剩下的那个孩子就是幸运者。
通常，数数的规则总是从1 开始，数到k 时让拿着山芋的孩子出列，然后重新从1 开始。Josephus问题可以表述为：n 个孩子玩这个游戏，最后的幸运者是谁？
为了解答这个问题，我们可以利用队列结构来表示围成一圈的n个孩子。一开始，假定对应于队列首节点的那个孩子拿着山芋。然后，按照游戏的规则，把“土豆”向后传递到第k个孩子（交替进行k次dequeue()和k次enqueue()操作），并让她出队（dequeue()）。如此不断迭代，直到队长
（getSize()）为1。
/*
* Josephus环
*/
import dsa.*;
import java.io.*;
//模拟Josephus环
public class Josephus {
// 利用队列结构模拟Josophus环
public static Object Josephus(Queue Q, int k) {
if (Q.isEmpty())
return null;
while (Q.getSize() > 1) {// 不断迭代
Q.Traversal();// 显示当前的环
for (int i = 0; i < k; i++)
// 将山芋向前传递k次
Q.enqueue(Q.dequeue());
Object e = Q.dequeue();// 拿着山芋的孩子退出
System.out.println("\n\t" + e + "退出");
}
return Q.dequeue();// 最后剩下的那个孩子
}
// 将一组对象组织为一个队列
public static Queue buildQueue(Object a[]) {
Queue Q = new Queue_Array();
for (int i = 0; i < a.length; i++)
Q.enqueue(a[i]);
return Q;
}
// 测试用main方法
public static void main(String[] args) {
String[] kid = { "Alice", "Bob", "Cindy", "Doug", "Ed", "Fred", "Gene",
"Hope", "Irene", "Jack", "Kim", "Lance", "Mike", "Nancy",
"Ollie" };
System.out.println("最终的幸运者是" + Josephus(buildQueue(kid), 5));
}
}
网友评论