数据结构与算法-实战(4)

01、数据结构和算法 - 实战：Java实现循环队列

1.1 什么是循环队列

循环队列：具有队头指针（front）和队尾指针（rear），指示队列元素所在的位置，避免删除元素时移动大量元素。队列也是一种线性表，只不过它是操作受限的线性表，只能在两端操作，先进先出（First In First Out，FIFO）。

循环队列特性：

只能队尾插入元素、在队头删除元素。
先进先出（First In First Out）的线性表，先进入的元素出队，后进入的元素才能出队。

优点：

相比普通的队列，元素出队时无需移动大量元素，只需移动头指针。
适合处理用户排队等待的情况。

时间复杂度:

读取时的时间复杂度为O(1)。
插入、删除时的时间复杂度为O(1)。

1.2 图解循环队列

1、顺序队列：

队列的顺序存储形式，可以用一个一维数组存储数据元素，用两个整型变量记录队头和队尾元素的下标。

顺序存储方式：

2、 队列的入队和出队情况：；

假设现在顺序队列Q分配了6个空间，然后进行入队出队操作，过程如图所示：

2.1 开始时为空队，front=rear，如图所示：

2.2 元素a1进队，放入尾指针rear（整型下标）的位置，rear后移一位，如图所示：

2.3 元素a3，a4，a5分别按顺序进队，尾指针rear依次后移，如图所示：

2.4 元素a1出队，头指针front（整型下标）后移一位，如图所示：

2.5 元素a2出队，头指针front（整型下标）后移一位，如图所示：

2.6 元素a6进队，放入尾指针rear（整型下标）的位置，rear后移一位，如图所示：

元素a7进队，此时尾指针rear已经超过了数组的下标，无法再存储进队，但是我们发现前面明明有2个空间，却出现了队满的情况，这种情况称为"假溢出"。

2.7 上面第【2.6】步元素a6进队之后，尾指针rear要后移一个位置，此时已经超过了数组的下标，即rear + 1 = maxSize（最大空间数6），那么如果前面有空闲，rear可以转向前面0的位置，如图所示：

2.8 然后元素a7进队，放入尾指针rear（整型下标）的位置，rear后移一位，如图所示：

2.9 元素a8进队，放入尾指针rear（整型下标）的位置，rear后移一位，如图所示：

2.10 队满临界条件判断，如图所示：

这时候虽然队列空间存满了，但是出现了一个大问题，队满时front = rear，这和队空的条件一模一样，无法区分队空还是队满，如何解决呢？有两种办法：一是设置一个标志，标记队空和队满；另一种办法是浪费一个空间，当尾指针rear的下一个位置front是时，就认为是队满。如图所示：

上述到达尾部又向前存储的队列称为循环队列，为了避免"假溢出"，我们通常采用循环队列。
循环队列无论入队还是出队，队尾、队头加1后都要取模运算，例如入队后队尾后移一位：rear = ( rear + 1) % maxSize。

2.10 为什么要对maxSize取余

主要是为了处理临界状态，即rear向后移动一个位置rear+1后，很有可能超出了数组的下标，这时它的下一个位置其实是0，如果将一维数组画成环形图，如图所示：

上图中最大空间maxSize，当rear=maxSize-1时，(rear + 1) % maxSize = 0，而且 front =0 ，正好满足队满的条件：(rear+1) % maxSize = front，此时为队满。

因此无论是front还是rear向后移动一个位置时，都要加1与最大空间maxSize取模运算，处理临界问题。

1、总结；

如下表格中，记录循环队列状态和说明：

状态	说明
队空	front=rear; // rear和front指向同一个位置
队满	(rear + 1) % maxSize = front; // rear向后移一位正好是front
入队	[rear] = x; // 将元素放入rear所指空间，rear =(rear+1) % maxSize; //rear向后移一位
出队	element = data[front]; //用变量记录data[front]所指元素，front = (front + 1) % maxSize // front向后移一位

1、 循环队列中存了元素个数；

因为队列是循环的，所以存在两种情况：

4.1 rear>= front，这种情况队列中元素个数为：rear - front=4-1=3。如下图所示：

4.2 rear< front，如下图所示：

此时，rear=4，front = maxSize-2，rear-front = 6-maxSize。但是我们可以看到循环队列中的元素实际上为6个，那怎么办呢？当两者之差为负数时，可以将差值+maxSize计算元素个数，即：rear - front + maxSize = 6 - maxSize + maxSize = 6，元素个数为6。

4.3 那么在计算元素个数时，可以分两种情况判断：

rear>= front：元素个数为rear-front；
rear<front：元素个数为rear-front+ maxSize；
4.4 采用取模的方法把两种情况统一为一个语句：

队列中元素个数：(rear - front + maxSize)% maxSize

当rear-front为负数时，加上maxSize再取余正好是元素个数，如(-2+6)%6=4；当rear-front为正数时，加上maxSize超过了最大空间数，取余后正好是元素个数，如(3+6)%6=3。

1.3 Java实现循环队列

CustomCyclicArrayQueue类是一个自定义实现了循环队列。

package com.yuanxw.datastructure.chapter1;
import java.util.NoSuchElementException;
/**
 * 自定义实现循环队列
 */
public class CustomCyclicArrayQueue {
   
     
    public static void main(String[] args) {
   
     
        CyclicArrayQueue arrayQueue = new CyclicArrayQueue<>(3);
        System.out.println("获得arrayQueue元素列表：" + arrayQueue);
        System.out.println("arrayQueue.add()，添加【Java】元素，执行返回结果：" + arrayQueue.add("Java"));
        System.out.println("arrayQueue.add()添加【C】元素，执行返回结果：" + arrayQueue.add("C"));
        System.out.println("arrayQueue.add()添加【Python】元素，执行返回结果：" + arrayQueue.add("Python"));
        /**
         * 添加第4个元素时：arrayQueue.add("C++");
          执行结果：
            Exception in thread "main" java.lang.IllegalStateException: Queue full
          	at com.yuanxw.datastructure.chapter1.CustomArrayQueue$ArrayQueue.add(CustomArrayQueue.java:88)
          	at com.yuanxw.datastructure.chapter1.CustomArrayQueue.main(CustomArrayQueue.java:17)
         */
        System.out.println(arrayQueue);
        System.out.println("获得arrayQueue队列个数："+arrayQueue.size());
        System.out.println("获得arrayQueue队列中的第一个元素："+arrayQueue.peek());
        System.out.println("获得arrayQueue队列中的第一个元素："+arrayQueue.peek());
        System.out.println(arrayQueue);

        System.out.println("当前arrayQueue对象中take()数据值为：" + arrayQueue.take());
        System.out.println(arrayQueue);
        System.out.println("当前arrayQueue对象中take()数据值为：" + arrayQueue.take());
        System.out.println(arrayQueue);
        System.out.println("当前arrayQueue对象中take()数据值为：" + arrayQueue.take());
        System.out.println(arrayQueue);
        /**
         * 当队列中的元素为空时，调用 arrayQueue.take()方法，抛出异常。
         * Exception in thread "main" java.util.NoSuchElementException
         * 	at com.yuanxw.datastructure.chapter1.CustomCyclicArrayQueue$CyclicArrayQueue.take(CustomCyclicArrayQueue.java:146)
         * 	at com.yuanxw.datastructure.chapter1.CustomCyclicArrayQueue.main(CustomCyclicArrayQueue.java:36)
         */
        // System.out.println("当前arrayQueue对象中take()数据值为：" + arrayQueue.take());

        System.out.println("arrayQueue.add()，添加【C++】元素，执行返回结果：" + arrayQueue.add("C++"));
        System.out.println("arrayQueue.add()添加【JavaScript】元素，执行返回结果：" + arrayQueue.add("JavaScript"));
        System.out.println("arrayQueue.add()添加【C#】元素，执行返回结果：" + arrayQueue.add("C#"));
        System.out.println(arrayQueue);
    }

    static class CyclicArrayQueue<E> {
   
     
        // 队列头部，指向队列头的第一个位置。默认值为：0
        private int front;
        // 队列尾，指向队列尾的位置。默认值为：0
        private int rear;
        // 数据
        private E[] data;
        // 容量
        private int maxSize;

        /**
         * 构造函数
         * @param capacity
         */
        public CyclicArrayQueue(int capacity) {
   
     
            this.front = 0;
            this.rear = 0;
            // 预留一个判断是否队满。
            this.maxSize = capacity + 1;
            this.data = (E[])new Object[maxSize];
        }
        /**
         * 判断是否已经满
         * @return
         */
        public boolean isFull(){
   
     
            return (rear  + 1) % maxSize == front;
        }

        /**
         * 是否为空
         * @return
         */
        public boolean isEmpty(){
   
     
            return rear == front;
        }

        /**
         * 获取大小
         * @return
         */
        public int size(){
   
     
            return (rear - front + maxSize) % maxSize;
        }

        /**
         * 添加元素
         * @param element
         * @return
         */
        public boolean add(E element){
   
     
            if(element == null){
   
     
                throw new NullPointerException("can not add element be null");
            }
            // 队列已经满
            if(isFull()){
   
     
                throw new IllegalStateException("Queue full");
            }
            data[rear] = element;
            rear = (rear + 1) % maxSize;
            return true;
        }

        /**
         * 返回队列中的第一个元素
         * @return
         */
        public E get(){
   
     
            if(isEmpty()){
   
     
                throw new NoSuchElementException();
            }
            E element = data[front];
            front = (front + 1) % maxSize ;
            return element;
        }

        /**
         * 返回队列中的第一个元素
         * @return
         */
        public E peek(){
   
     
            if(isEmpty()){
   
     
                throw new NoSuchElementException();
            }
            return data[front];
        }

        /**
         * 删除此队列的头并返回
         * @return
         */
        public E take(){
   
     
            if(isEmpty()){
   
     
                throw new NoSuchElementException();
            }
            E takeValue = data[front];
            front = (front + 1) % maxSize ;
            return takeValue;
        }

        @Override
        public String toString() {
   
     
            StringBuffer buffer = new StringBuffer();
            if(isEmpty()){
   
     
                return buffer.append("[]").toString();
            }

            buffer.append("[");
            for (int i = front; i < front + size(); i++) {
   
     
                buffer.append(data[i%maxSize]).append(",");
            }
            // 删除最后一个逗号
            buffer.deleteCharAt(buffer.length()-1);
            buffer.append("]");

            return buffer.toString();
        }
    }
}

执行结果：

获得arrayQueue元素列表：[]
arrayQueue.add()，添加【Java】元素，执行返回结果：true
arrayQueue.add()添加【C】元素，执行返回结果：true
arrayQueue.add()添加【Python】元素，执行返回结果：true
[Java,C,Python]
获得arrayQueue队列个数：3
获得arrayQueue队列中的第一个元素：Java
获得arrayQueue队列中的第一个元素：Java
[Java,C,Python]
当前arrayQueue对象中take()数据值为：Java
[C,Python]
当前arrayQueue对象中take()数据值为：C
[Python]
当前arrayQueue对象中take()数据值为：Python
[]
arrayQueue.add()，添加【C++】元素，执行返回结果：true
arrayQueue.add()添加【JavaScript】元素，执行返回结果：true
arrayQueue.add()添加【C#】元素，执行返回结果：true
[C++,JavaScript,C#]

–