数据结构(二) -- 队列

一，队列

与栈一样，队列也是最基本的数据结构之一。队列也是对象的一种容器，其中对象的插入和删除遵循“先进先出”（First-In-First-Out, FIFO）的原则--也就是说，每次删除的只能是最先插入的对象。因此，我们可以想象成将对象追加在队列的后端，而从其前端摘除对象。就这一性质而言，队列与栈堪称“孪生兄弟”。比如，在银行等待接受服务时，顾客们就会排成一个队列--最先到达者优先得到服务。再如，用球桶来乘放羽毛球时，所有的球也排成一个队列--你总是从一端将球取出，而从另一端把球放入。

二，队列ADT(AbstractDataType)

队列的抽象数据类型就是一个容器，其中的对象排成一个序列，我们只能访问和取出排在最前端（Front）的对象，只能在队列的尾部（Rear）插入新对象。正是按照这一规则，才能保证最先被插入的对象首先被删除（FIFO）。

队列ADT 首先支持下面的两个基本方法：

此外，与栈ADT 类似地，队列ADT 还支持如下的方法：

队列的应用十分广泛，无论是商店、剧院、机场还是银行、医院，凡是按照“先到的客户优先接受服务”原则的场合，都可以利用队列这一数据结构来编排相应的服务。

三，基于定长循环数组的队列的实现

定义一个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));
    }
}