Queue(队列)的Java实现

概述
  队列作为一种基础数据结构，是算法学习过程中必须要掌握的。此前在学习《啊哈！算法》一书中，见到该书作者使用在C语言下使用数组的方式实现了队列的功能，晚辈稍有佩服。但是这里就不使用数组的来实现队列了，还是使用最常规的链表来实现吧。
  对了，另外说一下，这里实现的是先进先出队列（FIFO）。好了，就不继续啰嗦了，直接上代码。

---

实现
新建链表节点

public class QueueNode<Item>
{
    Item item;
    QueueNode next;
}

构建一个指向FIFO头节点的指针

    private QueueNode first;

构建一个指向FIFO尾节点的指针

    private QueueNode last;

构建一个记录节点数的Int变量

    private int nodeNum;

判断队列是否为空

    public boolean isEmpty()
    {
        return first == null;
    }

获取队列的大小

    public int size()
    {
        return nodeNum;
    }

入队操作

    public void enqueue(Item item)
    {
        QueueNode oldLast = last;
        last = new QueueNode();
        last.item = item;
        last.next = null;
        if (isEmpty())
        {
            first = last;
        } else
        {
            oldLast.next = last;
        }
        nodeNum++;
    }

出队操作

    public Item dequeue()
    {

        Item item = (Item) first.item;
        first = first.next;
        if (isEmpty())
        {
            last = null;
        }
        nodeNum--;
        return item;

    }

新建一个类用于实现Iterator<Item>操作

    private class LinkListIterator implements Iterator<Item>
    {
        QueueNode node = first;

        @Override
        public boolean hasNext()
        {
            // TODO Auto-generated method stub
            return node.next != null;
        }

        @Override
        public Item next()
        {
            // TODO Auto-generated method stub
            Item item = (Item) node.item;
            node = node.next;
            return item;
        }

    }

---

全部代码如下

import java.util.Iterator;

public class Queue<Item> implements Iterable<Item>
{
    private QueueNode first;
    private QueueNode last;
    private int nodeNum;

    public boolean isEmpty()
    {
        return first == null;
    }

    public int size()
    {
        return nodeNum;
    }

    public void enqueue(Item item)
    {
        QueueNode oldLast = last;
        last = new QueueNode();
        last.item = item;
        last.next = null;
        if (isEmpty())
        {
            first = last;
        } else
        {
            oldLast.next = last;
        }
        nodeNum++;
    }

    public Item dequeue()
    {

        Item item = (Item) first.item;
        first = first.next;
        if (isEmpty())
        {
            last = null;
        }
        nodeNum--;
        return item;

    }

    @Override
    public Iterator<Item> iterator()
    {
        // TODO Auto-generated method stub
        return new LinkListIterator();
    }

    private class LinkListIterator implements Iterator<Item>
    {
        QueueNode node = first;

        @Override
        public boolean hasNext()
        {
            // TODO Auto-generated method stub
            return node.next != null;
        }

        @Override
        public Item next()
        {
            // TODO Auto-generated method stub
            Item item = (Item) node.item;
            node = node.next;
            return item;
        }

    }
}