数据结构与算法 - 队列的JAVA代码实现

数据结构与算法 - 队列的JAVA代码实现 队列的定义

在数据结构与算法里面，队列指的是一种抽象的、和对象的集合有关的数据类型。它是一组对象的集合，所有 *** 作都是关于添加、删除或是访问集合中的对象。队列和背包、栈一样非常基础并且应用广泛。

了解队列之前要先了解什么是链表。链表是链式数据结构的一种。简单点说就是在一个类的实例里面包含对本类的另外一个实例的引用。譬如：

public class Node {
		private Item item;
		private Node next;
}

借助链表我们可以实现很多不同的抽象数据类型。

先进先出队列

队列对其存储的数据一般遵循先进先出的规则（First In First Out, FIFO）。现实生活有很多类似的例子，譬如排队买票，先排的先买。队列是许多日常现象的自然模型，它也是无数应用程序的核心。

队列和栈相反，栈是后进先出（Last In First Out LIFO)。

队列的Java实现

下面直接上代码：

package algorithm;

import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Scanner;

public class Queue implements Iterable{

    private Node first;   // 队列的开头
    private Node last;    // 队列的结尾
    private int n;              // 队列的元素的数量

    // 辅助用的链表类，因为不需要对外暴露，所以以内部类的形式存在
    private static class Node {
        private Item item;
        private Node next;
    }

    // 初始化一个空的队列
    public Queue() {
        first = null;
        last = null;
        n = 0;
    }

    // 队列为空时返回True
    public boolean isEmpty() { return first == null;}

    // 返回队列元素的数量
    public int size() { return n;}

    // 查看队列排头的那个元素（就是最早添加的那个元素），不删除
    public Item peek() {
        if (isEmpty()) throw new NoSuchElementException("队列为空。");
        return first.item;
    }

    // 往队列添加元素
    public void enqueue(Item item) {
        Node oldlast = last; 
        last = new Node<>();
        last.item = item;
        if (isEmpty()) first = last;
        else oldlast.next = last;
        n++;
    }

    // 删除并返回队列开头的那个元素（就是最早添加的那个元素）
    public Item dequeue() {
        if (isEmpty()) throw new NoSuchElementException("Queue underflow;");
        Item item = first.item;
        first = first.next;
        n--;
        if (isEmpty()) last = null; // to avoid loitering
        return item;
    }

    // 队列的toString()方法
    public String toString() {
        StringBuilder s = new StringBuilder();
        for (Item item :
                this) {
            s.append(item);
            s.append(' ');
        }
        return s.toString();
    }

    // 返回队列的迭代器
    public Iterator iterator() {
        return new linkedIterator(first);
    }

    // 迭代器
    private class linkedIterator implements Iterator {
        private Node current;

        public linkedIterator(Node first) {current = first;}

        public boolean hasNext() {return current != null;}
        public void remove() { throw new UnsupportedOperationException();}

        public Item next() {
            if (!hasNext()) throw new NoSuchElementException();
            Item item = current.item;
            current = current.next;
            return item;
        }
    }

    // 测试，输入数据，遇到“-”就出列，其他就入列
    public static void main(String[] args) {
        Queue queue = new Queue<>();
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String s = sc.nextLine();
            if (!s.equals("-"))
                queue.enqueue(s);
            else if (!queue.isEmpty())
                System.out.println(queue.dequeue() + " ");
        }
        System.out.println("( 队列余下元素的数量：" + queue.size() + ")");
        sc.close();

    }
}

结语

在应用程序中使用队列的主要原因是在用集合保存元素的同时保存它们的相对顺序：使它们入列顺序和出列顺序相同。队列是数据结构的一种，是实现算法的基础。

资料引用：
《算法4》by Robert Sedgewick & Kevin Wayne