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

完整代码拉到最底下

一、介绍

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

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

二、实现过程及思路

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

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

1、编写类及属性

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

public class MyQueue {        private  [] arr;//存放队列元素的数组    private int elements;//队列元素数量    private int front;//队头元素在数组中的索引    private int end;//队尾元素在数组中的索引            public MyQueue() {        arr = new  [10];        elements = 0;        front = 0;        end = -1;    }    public MyQueue(int maxSize) {        arr = new  [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   peek() {    return arr[front];}

5、移除队首元素

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

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

6、插入

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

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

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

public void insert(  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  [] arr;    private int elements;//队列元素数量    private int front;//队头元素在数组中的索引    private int end;//队尾元素在数组中的索引    public MyQueue() {        arr = new  [10];        elements = 0;        front = 0;        end = -1;    }    public MyQueue(int maxSize) {        arr = new  [maxSize];        elements = 0;        front = 0;        end = -1;    }    //从队尾插入    public void insert(  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   remove() {        if (isEmpty()) {            throw new RuntimeException("队列已经是空的，放心使用吧");        }          value = arr[front++];        //如果已经是最后一个元素了,将指针重置即可        if (elements == 1) {            end = -1;            front = 0;            elements = 0;        } else {            elements--;        }        return value;    }    //查看数据，从队头查看    public   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());        }    }}