概述

队列是一种用于存储数据的数据结构（与链表和栈类似）。队列是一种只能在一端插入（队尾），在另一端删除（队头），有一定操作约束的线性表。队列中第一个插入也是第一个被删除的元素。所以，队列是一种先进先出（FIFO）的线性表。

举一个生活中的例子来理解队列的概念，例如排队。新来的人只能入队尾，排队头的人也是最早被服务，然后出队的人。

基于链表实现队列

如何使用链表来实现队列呢，来个图加深理解：

名词解释

• 插入数据：入队（enqueue），类似于从排队尾部插入。
• 删除数据：出队（dequeue），类似于排队的头部出去。
• 先入先出：First In First Out（FIFO）

通过上图，我们可知，队列的头部就是链表的表头结点，队列的尾部就是链表的表尾结点。enqueue 操作本质就是链表表尾插入；dequeue 操作本质就是链表表头删除。若还要实现对队列中所有元素的遍历操作，Queue 类需要实现 Iterable， 具体参考【背包】。

代码：

public class Queue<Item> implements Iterable<Item>{
    private Node first; // 指向最早添加的结点的链接
    private Node last;  // 指向最近添加的结点的链接
    private int N;  // 队列中的元素数量
    private class Node{  // 定义了结点的嵌套类
        Item item;
        Node next;
    }
    public boolean isEmpty() { return first == null; } // 或：N == 0
    public int size() { return N; }
    public void enqueue(Item item) { // 向表尾添加元素
        Node oldlast = last;
        last = new Node();
        last.item = item;
        last.next = null;
        if(isEmpty()) first = last;
        else oldlast.next = last;
        N++;
    }
    public Item dequeue() {  // 从表头删除元素
        Item item = first.item;
        first = first.next;
        if(isEmpty()) last = null;
        N--;
        return item;
    }
    // iterator() 的实现参看背包
    public static void main(String[] args) { 
        // 创建一个队列并操作字符串入队或出列
        Queue<String> q = new Queue<String>();
        while(!StdIn.isEmpty()) { 
            String item = StdIn.readString();
            if(!item.equals("-"))
                q.enqueue(item);
            else if(!q.isEmpty()) StdOut.print(q.dequeue() + " ");
        }
        StdOut.println("(" + q.size() + " left on queue)");
    }
}

运行结果