数据结构（3）：队列的原理和实现

完整代码拉到最底下

一、介绍

队列顾名思义就像我们生活中排队一样，先进先出。

如上图所示，25、16、5、9依次在队列中，按照顺序拿出的数据也分别是25、26、5、9。

二、实现过程及思路

底层使用数组来实现，实现的功能有插入数据到队尾、移除队首数据、查看队首数据、判断队列是否为空、判断队列是否存满。

将队列的元素存储在数组的某个区间内，队列在数组中是连续的，所以使用变量标记队列在数组中的位置。

1、编写类及属性

我们可以使用elements变量标记队列中元素的数量，使用front变量标记队首元素在数组的索引，end变量标记队尾元素在数组中的索引。

public class MyQueue {

    private Object[] arr;//存放队列元素的数组
    private int elements;//队列元素数量
    private int front;//队头元素在数组中的索引
    private int end;//队尾元素在数组中的索引


    public MyQueue() {
        arr = new Object[10];
        elements = 0;
        front = 0;
        end = -1;
    }

    public MyQueue(int maxSize) {
        arr = new Object[maxSize];
        elements = 0;
        front = 0;
        end = -1;
    }
}

2、队列是否为空

标记队列元数量的变量 elements 为 0 即为空

public boolean isEmpty() {
    return elements == 0;
}

3、队列是否已经满了

队列元素个数与数组的长度相等即为满

public boolean isFull() {
    return elements == arr.length;
}

4、获取队头元素

获取数组中索引为 front的元素

public Object peek() {
    return arr[front];
}

5、移除队首元素

每次都是移除数组中索引为 front 的元素，下一个元素就变成了队首，即front+1，队列元素个数elements-1。共有三种情况要考虑，如果队列已经空了就无须做任何操作，如果已经是最后一个元素，直接将标记位置的变量重置即可，其他情况正常操作。

public Object remove() {
    if (isEmpty()) {
        throw new RuntimeException("队列已经是空的，放心使用吧");
    }
    Object value = arr[front++];
    //如果已经是最后一个元素了,将指针重置即可
    if (elements == 1) {
        end = -1;
        front = 0;
        elements = 0;
    } else {
        elements--;
    }
    return value;
}

6、插入

我们编写一个持续可用的队列，所以要考虑到以下情况。

(1)存储队列的数组满了(队列满了)，这个好理解，满了就无法向队尾加入元素了。

(2)因为队列在数组中是连续的，如果队列的元素在数组中最后，需要将元素从队首到队尾移到数组中第一位，也就是将后面的位置空出来(参考下图)。

public void insert(Object value) {
    //检测队列是否已经满了
    if (isFull()) {
        throw new RuntimeException("队列内元素已达到设定长度");
    }

    //如果后面没有空位置，将余下元素放到数组的头
    if (elements > 1 && end == arr.length - 1) {
        int i = 0;
        for (; i < elements; i++, front++) {
            arr[i] = arr[front];
        }
        front = 0;
        end = i-1;
    }
    //其他情况正常向后添加元素
    arr[++end] = value;
    elements++;
}

7、测试

public static void main(String[] args) {
    MyQueue queue = new MyQueue(4);
    queue.insert(11);
    queue.insert(12);
    queue.insert(13);
    queue.insert(14);

    queue.remove();
    queue.remove();
    queue.insert(16);
    //queue.remove();
    //queue.remove();

    //queue.insert(19);
    //queue.insert(20);
    queue.remove();

    queue.remove();

    queue.insert(21);
    queue.insert(22);

    while (!queue.isEmpty()) {
        System.out.println(queue.remove());
    }
}

三、完整代码

package com.jikedaquan.datastruct;

public class MyQueue {
    private Object[] arr;
    private int elements;//队列元素数量
    private int front;//队头元素在数组中的索引
    private int end;//队尾元素在数组中的索引

    public MyQueue() {
        arr = new Object[10];
        elements = 0;
        front = 0;
        end = -1;
    }

    public MyQueue(int maxSize) {
        arr = new Object[maxSize];
        elements = 0;
        front = 0;
        end = -1;
    }

    //从队尾插入
    public void insert(Object value) {
        //检测队列是否已经满了
        if (isFull()) {
            throw new RuntimeException("队列内元素已达到设定长度");
        }

        //如果后面没有空位置，将余下元素放到数组的头
        if (elements > 1 && end == arr.length - 1) {
            int i = 0;
            for (; i < elements; i++, front++) {
                arr[i] = arr[front];
            }
            front = 0;
            end = i-1;
        }
        arr[++end] = value;
        elements++;

    }

    //删除数据，从队头删除
    public Object remove() {
        if (isEmpty()) {
            throw new RuntimeException("队列已经是空的，放心使用吧");
        }
        Object value = arr[front++];
        //如果已经是最后一个元素了,将指针重置即可
        if (elements == 1) {
            end = -1;
            front = 0;
            elements = 0;
        } else {
            elements--;
        }
        return value;
    }

    //查看数据，从队头查看
    public Object peek() {
        return arr[front];
    }

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

    public boolean isFull() {
        return elements == arr.length;
    }

    public static void main(String[] args) {
        MyQueue queue = new MyQueue(4);
        queue.insert(11);
        queue.insert(12);
        queue.insert(13);
        queue.insert(14);

        queue.remove();
        queue.remove();
        queue.insert(16);
//        queue.remove();
//        queue.remove();

//        queue.insert(19);
//        queue.insert(20);
        queue.remove();

        queue.remove();

        queue.insert(21);
        queue.insert(22);

        while (!queue.isEmpty()) {
            System.out.println(queue.remove());
        }
    }
}