数据结构与算法(3)：基于链表实现的队列结构Java代码实现

队列定义

先进先出（FIFO)——先进队列的元素先出队列。来源于我们生活中的队列（先排队的先办完事）。

基本操作

• initQueue（）　　 ——初始化队列
• enqueue（） ——进队列
• dequeue（） ——出队列
• isEmpty（） ——判断队列是否为空
• size（） ——判断队列中元素的数量
• isFull() -- 判断队列是否已满：仅在设定了队列的最大容量时有效

队列可以由数组和链表两种形式实现队列操作（java语言）本文将分别实现这两种队列。

一、链队列——队列的链式表示和实现：

功能分析：

• 这里，我们将队列表示为一条从最早插入的元素到最近插入的元素的链表，实例变量first执行队列的开头，实例变量last指向队列的结尾。
• 一个元素入列时，我们将它添加到链表尾部，为空时需要额外处理：first和last同时指向第一个元素。
• 一个元素出列时，我们删除链表的尾部元素。
• size：在实例内部持有一个私有属性保存这个值。
• isEmpty:当size为0时，表示为空。

使用链表可以达到的效果：

它可以处理任意类型的数据（使用泛型），所需的空间总是和集合的大小成正比，操作所需要的时间总是和集合的大小无关。

代码实现：

/**
 *
 * @Created on 2017-02-27 12:19
 * 队列接口表示
 */
public interface FlowerQueue<T> {

    /**
     * 初始化队列： 设定当前队列的最大容量，如果需要的话。
     */
    void initQueue(int maxSize);

    /**
     * 进入队列
     */
    void enqueue(T item);

    /**
     * 出队列
     * @return
     */
    T dequeue();

    int size();

    boolean isEmpty();

    /**
     * 是否已经不再允许添加新的元素
     * @return
     */
    boolean isFull();

}

/**
 *
 * @Created on 2017-02-27 12:26
 * 链表实现的队列
 */
public class FlowerLinkedQueue<T> implements FlowerQueue<T> {

    private int size;
    private int maxSize;
    private Node<T> first;
    private Node<T> last;

    public FlowerLinkedQueue() {
        initQueue(16);
    }

    @Override
    public void initQueue(int maxSize) {
        this.maxSize = maxSize;
        first = null;
        last = null;
    }

    @Override
    public void enqueue(T item) {

        if (size() == maxSize) {
            throw new RuntimeException("已经达到当前链表的最大容量");
        }

        Node<T> oldLast = last;
        last = new Node<T>();
        last.item = item;
        last.next = null;
        // 如果是第一个元素，需要将first指向last
        if (isEmpty()) {
            first = last;
        } else {
            oldLast.next = last;
        }
        size++;
    }

    @Override
    public T dequeue() {
        if (isEmpty()) {
            return null;
        }
        T item = first.item;

        if (first.next == null) {
            first = null;
            last = null;
        } else {
            first = first.next;
        }

        size--;
        return item;
    }

    @Override
    public int size() {
        return this.size;
    }

    @Override
    public boolean isEmpty() {
        return this.size == 0;
    }

    @Override
    public boolean isFull() {
        return this.size == maxSize;
    }

    // 定义一个内部类, 作为链表结构
    private class Node<T> {
        T item;
        Node next;
    }

}

/**
 *
 * @Created on 2017-02-27 17:20
 * 链表实现的队列测试用例
 */
public class FlowerLinkedQueueTest {

    @Test
    public void test() {
        FlowerLinkedQueue<Integer> queue = new FlowerLinkedQueue<Integer>();

        for(int i=0; i<100; i++) {
            if (i < 16) {
                queue.enqueue(i);
            } else {
                Integer dequeue = queue.dequeue();
                System.out.println("出队列的数值：" + dequeue);
            }

            System.out.println("当前队列长度：" + queue.size());

        }

    }

}

二、数组队列-底层为数组的队列：

这种方式，底层使用的是数组来存储数据，然后通过2个指针来控制入队和出队。

功能分析：

• 首先定义一个固定长度的数组。
• 定义两个指针，front代表队头，rear代表队尾。
• 随着元素不断的入队和出队，会出现一种情况：数组还没满，但是rear就要越界了。因此我们需要考虑使用循环数组。
• 所谓循环数组，就当rear出现越界情况时，对其进行取模，从而使新数据放到数组索引为0的位置，直到整个数组被放满。
• 当数组中的每个索引处都有值，又有新元素入队时，需要对数组进行动态扩容：新建一个数组，将原数组的数据拷贝过来。

代码实现：

实现类：

/**
 *
 * @Created on 2017-02-27 19:12
 * 基于数组实现的队列
 */
public class FlowerArrayQueue<T> implements FlowerQueue<T> {

    private T[] data;
    public int size;
    public int front;
    public int rear;
    private int capacity = 10;

    public FlowerArrayQueue() {
        initQueue(capacity);
    }

    @Override
    public void initQueue(int maxSize) {
        // 初始化操作
        data = (T[]) new Object[maxSize];
        size = 0;
    }

    @Override
    public void enqueue(T item) {

        // 扩容
        if (size == data.length) {
            // capacity = 2 * capacity
            if (rear == 0) {
                T[] bigger = (T[]) new Object[data.length * 2];
                for (int i = front; i < data.length - front; i++) {
                    bigger[i] = data[i];
                }
                bigger[data.length] = item;
                rear = data.length;
                capacity = 2 * capacity;
                front = 0;
                data = bigger;

            } else {
                // capacity = 2 * capacity
                T[] bigger = (T[]) new Object[data.length * 2];
                for (int i = front; i < data.length - front + 1; i++) {
                    bigger[i - front] = data[i];
                }
                for (int i = 0; i < rear; i++) {
                    bigger[i + data.length - 1] = data[i];
                }
                data = bigger;
                front = 0;
                rear = data.length;
                capacity = 2 * capacity;
            }

        }
        if (size == 0) {
            front = 0;
            rear = 0;
        }
        data[rear] = item;
        // 新增到队尾时，注意使用循环数组避免越界
        rear = (rear + 1) % capacity;
        size++;
    }

    @Override
    public T dequeue() {
        if (size == 0) {
            return null;
        }
        T e = data[front];
        data[front] = null;
        // 队首取出后，注意使用循环数组避免越界
        front = (front + 1) % capacity;
        size--;
        return e;
    }

    @Override
    public int size() {
        return this.size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return size == capacity;
    }
}

测试用例：

/**
 * 
 * @Created on 2017-02-27 19:36
 * 基于数组的队列结构 测试用例
 */
public class FlowerArrayQueueTest {

    @Test
    public void test() {
        FlowerArrayQueue<Integer> queue = new FlowerArrayQueue<Integer>();
        for(int i=0; i<100; i++) {
            queue.enqueue(i);
            System.out.println("当前队列长度：" + queue.size());
        }

        for(int i=0; i<200; i++) {
            Integer dequeue = queue.dequeue();
            System.out.println("当前出队元素：" + dequeue);
            System.out.println("当前队列长度：" + queue.size());
        }
    }

}