4.5.1、队列的定义

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

图片alt

4.5.2、队列的实现

4.5.2.1、队列API设计

类名 Queue
构造方法 Queue()：创建Queue对象
成员变量 private Node head：记录首结点
private int N：当前队列的元素个数
private Node last：记录最后一个结点
成员内部类 private class Node：结点类
成员方法 public boolean isEmpty()：判断是否为空
public int size(): 获取队列的元素个数
public T dequeue()：从队列拿去一个元素
public void enqueue(T t)：往队列插入一个元素

4.5.2.2、队列实现和测试

实现类：

package cn.test.algorithm.datastruct;

import java.util.Iterator;

public class Queue<T> implements Iterable<T> {

    @Override
    public Iterator<T> iterator() {
        return new SIterator();
    }

    private class SIterator implements Iterator {

        private Node n;

        public SIterator() {
            this.n = head;
        }

        @Override
        public boolean hasNext() {
            return n.next != null;
        }

        @Override
        public Object next() {
            n = n.next;
            return n.item;
        }
    }

    //内部类
    private class Node {
        public T item;
        public Node next;

        public Node(T item, Node next) {
            this.item = item;
            this.next = next;
        }
    }

    //首结点
    private Node head;
    //尾节点
    private Node last;
    //元素个数
    private int N;


    public Queue() {
        head = new Node(null, null);
        last = null;
        N = 0;
    }

    //是否为空
    public boolean isEmpty() {
        return N == 0;
    }

    //栈的元素个数
    public int size() {
        return N;
    }

    //插入元素
    public void enqueue(T t) {
        //当前尾结点为null
        if (last == null) {
            last = new Node(t, null);
            head.next = last;
        } else {
            //当前尾节点不为null
            Node oldLast = last;

            last = new Node(t, null);

            oldLast.next = last;
        }
        N++;
    }

    //移除元素
    public T dequeue() {
        if (isEmpty()) {
            return null;
        }

        Node oldFirst = head.next;
        head.next = oldFirst.next;
        N--;

        //如果删除后为空，那么last就必须要设置为空
        if (isEmpty()) {
            last = null;
        }
        return oldFirst.item;
    }
}

测试类：

package cn.test.algorithm.test;


import cn.test.algorithm.datastruct.Queue;

public class QueueTest {
    public static void main(String[] args) {
        Queue<Integer> queue = new Queue<>();
        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);
        queue.enqueue(4);
        queue.enqueue(5);
        System.out.println("==============入队列测试==============");
        System.out.println("队列里元素个数：" + queue.size());
        System.out.println("队列里的数据：");
        for (Integer item : queue) {
            System.out.println(item);
        }

        System.out.println("====================出队列测试=====================");
        Integer result = queue.dequeue();
        System.out.println("队列里元素个数：" + queue.size());
        System.out.println("弹出元素值：" + result);
        for (Integer item : queue) {
            System.out.println(item);
        }
        result = queue.dequeue();
        System.out.println("队列里元素个数：" + queue.size());
        System.out.println("弹出元素值：" + result);
        for (Integer item : queue) {
            System.out.println(item);
        }
    }
}

运行结果：

==============入队列测试==============
队列里元素个数：5
队列里的数据：
1
2
3
4
5
====================出队列测试=====================
队列里元素个数：4
弹出元素值：1
2
3
4
5
队列里元素个数：3
弹出元素值：2
3
4
5