实例简析队列的链式实现

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。在队列的形成过程中，可以利用线性链表的原理，来生成一个队列，也就是所谓的队列的链式实现。基于链表的队列，要动态创建和删除节点，效率较低，但是可以动态增长。

队列采用的FIFO(first in first out)，新元素（等待进入队列的元素）总是被插入到链表的尾部，而读取的时候总是从链表的头部开始读取。每次读取一个元素，释放一个元素。所谓的动态创建，动态释放。因而也不存在溢出等问题。由于链表由结构体间接而成，遍历也方便。

维护一个指向队首的front结点，一个指向队尾的rear结点，和一个标识队列大小的count变量：

private LinearNode front,rear;//指示队首和队尾

private int count;

构造函数：

public LinkedQueue()

    {

        front = null;

        rear = null;

        count = 0;

    }

在看代码之前，先注意几个非空判断：

可以判断队列为空的条件：

head = null

tail = null

head = tail = null

入队/出队时需要的非空判断：

enqueue（入队）：若为空 tail = head = node

dequeue（出队）

出队前空：return null

出队后空：tail = head = null

链式实现：

package Queue;

import Bag.LinearNode;

public class LinkedQueue implements QueueADT {

    private LinearNode front,rear;

    private int count;

    public static void main(String[] args) {

        LinkedQueue queue = new LinkedQueue();

        System.out.println("依次将0到9入队，然后连续出队5次");

        for(int i = 0;i < 10;i++)

            queue.enqueue(i);

        for(int i = 0;i < 5;i++)

            queue.dequeue();

        System.out.println("队列的大小为： " + queue.size());

        System.out.println("队列为空吗？： " + queue.isEmpty());

        System.out.println("队列的头为： " + queue.first());

    }

    public LinkedQueue()

    {

        front = null;

        rear = null;

        count = 0;

    }

    public int size() {

        return count;

    }

    public boolean isEmpty() {

        return (size() == 0);

    }

    public void enqueue(Object element) {

        LinearNode node = new LinearNode(element);

        if(isEmpty())

            front = rear = node;

        else

        {

            rear.setNext(node);

            rear = node;

        }

        count++;

    }

    public Object dequeue() {

        if(isEmpty())

        {

            System.out.println("队列中没有元素");

            System.exit(1);

        }

        Object result = front.getElement();    

        front = front.getNext();

        count--;

        return result;    

    }

    public Object first() {

        return front.getElement();

    }

}

结果：

依次将0到9入队，然后连续出队5次

队列的大小为： 5

队列为空吗？： false

队列的头为： 5

我们再来看个例子：

public class LinkedQueue<E> {

    class Node<E> {

        E item;

        Node<E> next;

        public Node(E e) {

            this.item = e;

        }

    }

    private Node head; // 队首

    private Node tail; // 队尾

    public LinkedQueue() {

     // 队列为空时 head = tail = null

        head = tail = null;

    }

    public void enqueue(E e) {

        Node node = new Node(e);

        // 队列为空

        if(tail == null) {

            head = tail = node;

        }else {

            tail.next = node;

            tail = node;

        }

    }

    public E dequeue() {

        // 出队前为空

        if (head == null) {

            return null;

        }

        E item = (E)head.item;

        // 出队后空

        if (head.next == null) {

            head = tail = null;

        }

        return item;

    }

    public E peek() {

        return this.head == null ? null : (E)this.head.item;

    }

}

从上面代码不难看出，链式队列其实就是链表的基本操作，所以LinkedList也是Queue的一个实现。队列的链式实现的本质是队列的形成过程中，利用线性链表的原理，来生成一个队列。想了解更多有趣的数据结构，学习更多的数据结构知识，可以观看本站的数据结构和算法教程，让我们的学习实现质的飞跃！