循环队列

一、普通队列的弊端

队列：是一种可以分别在两端进行增删的特殊线性表。既然是线性表，那么可以使用顺序存储和链式存储来实现，如果是链式存储的话，那么增删的复杂度都是O(1)，这一点很好理解，应该只要修改一下指针就好了，如果是顺序存储的话，在队尾增加的时间复杂度是O(1)，但是在队头进行删除的时候，会涉及到迁移操作，这时候的时候复杂度就是O(n)，所以一般来讲不会直接使用顺序存储的方式来实现普通队列。

image-20220212152617429

二、循环队列的原理概述

较之普通队列用顺序存储来实现存在删除带来的时间损耗，怎么去避免它，因为普通队列删除队头结点，会将后续结点进行整体的一个前移，所以才会带来O(n)的时间复杂度，如果不前移结点，而是调整头结点的位置，删除一个结点，就将头结点往后移动一位。

TIP：front是指向头结点的指针，rear是指向下一个要插入结点的指针

image-20220212152728705

队列初始状态

image-20220212152746226

删除节点后状态

那么这样子是可以避免删除带来的时间损耗了，但是可以发现当往下标4插入数据后，rear指针该何去何从，放在脚标5？那么会报数组越界，而且很明显下标0和1的位置都空着，所以rear应该指向0才对，那么这种实现方式其实就是循环列表。

image-20220212152802331

循环队列

实现循环列表存在几个要考虑的事情：-
1：啥时候表示队列空着？
一般在循环队列的初始状态，可以将front和rear指针都指向下标0，当插入元素时，rear会顺时针方向累加，当删除元素时，front也会顺时针方向累加，那么删的和加的一样多，其实在同一个方向走的下标也一样多，那么自然容易想到当_front == rear_时，表示队列为空。只不过这里需要注意一点，因为是循环队列，front和rear的值不能无限递增，比如一个数组，大小为5，最大下标是4，难道还能4+1=5，出来个5下标，明显不可能，所以，这里的递增，需要这么操作：(front + 1) % maxSize，巧妙的用到了取模运算符。

2：啥时候表示队列满了？
队列啥时候算满呢？其实可以发现front可能在rear的后面，也有可能在rear的前面，仔细想想可能会发现某种情况下，当rear == front也是队列满的时候，但是这样就跟队列空着的时候，判断条件一致了，这样明显也不行，为了区分开来，单独留一个结点不存值，当rear和front相差一个结点时，即证明循环队列已满。判断条件为：**(rear + 1) % maxSize = front**

image-20220212152919522

循环队列满的状态

3：怎么才能知道队列当前含有元素的多少?
由于循环队列的特性，队列里面的元素可能是连续的，也有可能是分成两段的，那么怎么去统计含有多少元素呢？可以使用这个公式(rear - front + maxSize) % maxSize，因为rear - front可能为正数，也有可能会负数，为正数表示是连续的，为负数表示不连续的。

三、循环队列的实现-java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
public class CircularQueue<E> {
    /**
     * 循环队列
     */
    /**
     * 循环队列常用的方法如下：
     * 1、InitCircularQueue()    初始化一个循环队列
     * 2、ClearCircularQueue()   清空一个循环队列
     * 3、CircularEmpty()    判断循环队列是否为空
     * 4、GetHead()  获取循环队列尾部结点数据
     * 5、EnCircularQueue()  在循环队列尾部插入新结点
     * 6、DeCircularQueue()  删除循环队列头部结点
     * 7、CircularQueueLength()  返回循环队列的长度
     */

    Object[] queueArray = null;
    int front; //队头指针
    int rear; //队尾指针
    int maxQueueSize;
    public CircularQueue(int maxSize){
        // 初始化循环队列的基础存储结构，数组
        this.maxQueueSize = maxSize;
        this.queueArray = new Object[maxSize];
        this.front = 0; //队头指针指向循环队列的第一个结点，初始为0
        this.rear = 0;//队尾指针指向循环队列的待插入结点位置，初始为0
    }
    public void ClearCircularQueue(){
        if (front == rear){return;}
        //清空一个循环队列，只需要从front开始，一直到rear-1，将节点元素赋值成null
        for (;front != rear;){
            DeCircularQueue();
        }
    }

    public Boolean CircularEmpty(){
        if (front == rear){return true;}
        else{return false;}
    }

    public E GetHead(){
        return (E)queueArray[front];
    }

    public void EnCircularQueue(E elem){
        //满足(rear+1)%maxSize=front说明该循环队列已经达到满队列状态，无法在插入
        if ((rear + 1) % maxQueueSize == front){
            return;
        }
        queueArray[rear] = elem;
        //循环队列在rear指针时，如果只是简单累加，很可能会出现空指针异常
        rear = (rear + 1) % maxQueueSize;
    }

    public E DeCircularQueue (){
        //满足front = rear时，说明队列为空
        if (front == rear){return null;}
        E returnElem = (E)queueArray[front];
        queueArray[front] = null;
        front = (front + 1) % maxQueueSize;
        return returnElem;
    }

    public int CircularQueueLength(){
        return (rear - front + maxQueueSize) % maxQueueSize;
    }

    public String toString(){
        StringBuffer stringBuffer = new StringBuffer();
        for (int index = 0;index < maxQueueSize;index++){
            if (index + 1 < maxQueueSize){
                stringBuffer.append(queueArray[index]);
                stringBuffer.append(",");
            }else{
                stringBuffer.append(queueArray[index]);
            }
        }
        return stringBuffer.toString();
    }

    public static void main(String[] args) {
    }
}

​

四、循环队列时间复杂度分析

可以很明显发现，循环队列的增删操作时间复杂度都是O(1)，并且还能实现充分利用申请到的空间，所以如果能够确认一个队列的大小，那么就使用顺序方式来实现，并且是循环队列，而不是普通队列。如果确认不了，那么还是使用链式方式来实现。