@循环队列元素个数
 
若f指向第一个元素，r指向最后一个元素的下一个元素。队列长度为n。
 
情况1：r在f的上面
 此时元素个数为r-f
 
情况2：r在f下面
 

 此时元素个数为 r-0 + n-f 即r-f+n
 
元素个数不可能超过n。
 故综合两种情况可知要取模。
 即（r-f+n)%n。

队列，循环队列为什么用空一个元素的位置
 
队列介绍
 
1）队列是一个有序列表，可以用数组或是链表表示。
 
2）遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出。
 
front及rear分别记录队列前后端的下标，front随着数据的输出而改变，而rear则是随着数据输入而改变。
 
 
代码实现
 
import java.util.Scanner;

public class ArrayQueueDemo {
    public static void main(String[] args) {
        //创建一个队列
        ArrayQueue arrayQueue = new ArrayQueue(3);
        char key = ' ';//接受用户输入
        Scanner scanner = new Scanner(System.in);
        boolean loop = true;
        //输出一个菜单
        while(loop){
            System.out.println("s(show):显示队列");
            System.out.println("e(exit):退出程序");
            System.out.println("a(add):添加数据到队列");
            System.out.println("g(get):从队列取出数据");
            System.out.println("h(head):查看队列头的数据");
            key = scanner.next().charAt(0);
            switch (key){
                case 's':
                    arrayQueue.showQueue();
                    break;
                case 'a':
                    System.out.println("请输入一个数字：");
                    int value = scanner.nextInt();
                    arrayQueue.addQueue(value);
                    break;
                case 'g':
                    try {
                        int res = arrayQueue.getQueue();
                        System.out.println("取出数据："+res);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h':
                    try {
                        int res = arrayQueue.headQueue();
                        System.out.println("队列头数据："+res);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e':
                    scanner.close();
                    loop = false;
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序退出");
    }
}

class ArrayQueue{
    private int maxSize;
    private int front;
    private int rear;
    private int[] arr;//模拟队列，该数组用于存放数据

    //创建队列的构造器
    public ArrayQueue(int arrMaxSize){
        maxSize = arrMaxSize;
        arr = new int[maxSize];
        front = -1;//指向队列头部（第一个数据的前面）
        rear = -1;//指向队列尾部（最后一个数据）
    }
    //判断队列是否满
    public boolean isFull(){
        return rear == maxSize-1;
    }
    //判断队列是够为空
    public boolean isEmpty(){
        return front==rear;
    }
    //添加数据到队列
    public void addQueue(int n){
        if(isFull()){
            System.out.println("队列已满，不可加入数据");
            return;
        }
        rear++;
        arr[rear] = n;
    }
    //从队列中取出数据
    public int getQueue(){
        if(isEmpty()){
            throw new RuntimeException("队列为空，不可取出数据");
        }
        front++;
        return arr[front];
    }
    //显示队列的中的所有数据
    public void showQueue(){
        if(isEmpty()){
            System.out.println("队列为空");
            return;
        }
        for (int i = 0; i <arr.length ; i++) {
            System.out.print(i+":"+ arr[i]+"\n");
        }
    }
    //显示队列的头数据，不是取出数据
    public  int headQueue(){
        if(isEmpty()){
            System.out.println("队列为空");
            throw new RuntimeException("队列为空");
        }
        return arr[front+1];
    }
}

 
问题分析并优化：
 
 
目前数组使用了一次就不能用了，没有达到复用的效果
 
 
我们要使用算法，将目前的数组改成一个环形的队列 取模%
 
 
数组环形队列思路：
 
1、front变量的含义做一个调整：front就指向队列的第一个元素，就是是说arr[front]就是队列的第一个元素，front初始值为0；
 
2、rear变量的含义做一个调整：rear指向队列的最后一个元素的后一个位置，rear的初始值为0；
 
3、队列满的条件：(rear+1)%maxSize ==front
 
4、队列空的条件是：rear == front
 
5、此时队列的有效长度是： (rear+maxSize-front)%maxSize
 
遇到的问题（循环队列空一个元素的位置）
 
在得到队列满的条件：(rear+1)%maxSize ==front时，我充满了疑惑，怎么算都觉得在rear已经表示最后元素的后一位了，这种情况下加一肯定是不对的，后来我查了一些资料。
 
 
那么，循环队列为什么用空一个元素的位置呢？？？
 
 
 
这个是根据需要来用的
 循环队列中，由于入队时尾指du针向前追赶头指针；zhi出队时头指针向前追赶尾指针，造成dao队空和队满时头尾指针均相等。因此，无法通过条件front==rear来判别队列是"空"还是"满"。
 解决这个问题的方法至少有三种：
 ①另设一布尔变量以区别队列的空和满；
 ②少用一个元素的空间。约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：rear所指的单元始终为空）；
 ③使用一个计数器记录队列中元素的总数（即队列长度）。
 
 
代码实现（循环队列）
 
import java.util.Scanner;

public class CicleArrayQueueDemo {
    public static void main(String[] args) {

        System.out.println("测试数组模拟环形数据");
        CircleArray queue = new CircleArray(4);//空出一个位置，其队列有效数据为3；
        char key = ' ';
        Scanner scanner = new Scanner(System.in);
        boolean loop = true;
        while(loop){
            System.out.println("s(show):显示队列");
            System.out.println("e(exit):退出程序");
            System.out.println("a(add):添加数据到队列");
            System.out.println("g(get):从队列取出数据");
            System.out.println("h(head):查看队列头的数据");
            key = scanner.next().charAt(0);
            switch (key){
                case 's':
                    queue.showQueue();
                    break;
                case 'a':
                    System.out.println("请输入一个数字：");
                    int value = scanner.nextInt();
                    queue.addQueue(value);
                    break;
                case 'g':
                    try {
                        int res = queue.getQueue();
                        System.out.println("取出数据："+res);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h':
                    try {
                        int res = queue.headQueue();
                        System.out.println("队列头数据："+res);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e':
                    scanner.close();
                    loop = false;
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序退出");

    }

    static class CircleArray{
        private int maxSize;
        private int front;//front就指向队列的第一个元素，就是是说arr[front]就是队列的第一个元素，front初始值为0；
        private int rear;//rear指向队列的最后一个元素的后一个位置，rear的初始值为0；
        private int[] arr;//模拟队列，该数组用于存放数据

        public CircleArray(int arrMaxSize){
            maxSize = arrMaxSize;
            arr = new int[maxSize];
        }

        //判断队列是否满
        public boolean isFull(){
            return (rear + 1)%maxSize ==front;
        }
        //判断队列是够为空
        public boolean isEmpty(){
            return front==rear;
        }
        //添加数据到队列
        public void addQueue(int n){
            if(isFull()){
                System.out.println("队列已满，不可加入数据");
                return;
            }
            arr[rear] = n;
            rear = (rear+1)%maxSize;
        }
        //从队列中取出数据
        public int getQueue(){
            if(isEmpty()){
                throw new RuntimeException("队列为空，不可取出数据");
            }
            int value = arr[front];
            front = (front+1) % maxSize;
            return value;
        }
        //求出当前队列的个数
        public int arrCount(){
            return (rear+maxSize-front)%maxSize;
        }
        //显示队列的中的所有数据
        public void showQueue(){
            if(isEmpty()){
                System.out.println("队列为空");
                return;
            }
            for (int i = front; i <front+arrCount(); i++) {
                System.out.print((i%maxSize)+":"+ arr[i%maxSize]+"\n");
            }
        }
        //显示队列的头数据，不是取出数据
        public  int headQueue(){
            if(isEmpty()){
                System.out.println("队列为空");
                throw new RuntimeException("队列为空");
            }
            return arr[front];
        }

    }
}

 
 
因为循环对列，rear不一定比front大
 
如果rear<front结果是rear-front+maxsize 
如果rear>front结果是rear-front
为了用一个表达式同时表达两者，用(rear-front+maxsize)%maxsize
假设maxsize=10
rear=1 front=9，那么结果是2
rear=9 front=1，那么结果是8
 
 
 
reference：
 
https://ask.csdn.net/questions/256277

 
顺序存储的队列，元素循环存储
 
循环队列定义
循环队列判空、判满
循环队列长度
代码实现
测试结果
 

 
循环队列定义
 
在逻辑上把顺序存储的队列想象成一个环，就是循环队列。
 循环队列仍是顺序存储，只是元素可以循环存储在给定的存储空间。
 
前篇文章，顺序存储队列基本操作 所描述的队列的存储空间只可以使用一次，在一些元素出队之后，空出来的空间没有办法再次存储，造成浪费，所以更多选择循环队列。
 
两者的内存中的存储一样，只是逻辑上将两者分为了非循环和循环。
 
循环队列判空、判满
 
判空和判满可以有多种方式，根据自己的设计选择即可。
 
第一种方式：
 判空：当首尾指针指向同一位置时，队列为空。
 判满：当尾指针+1 = 首指针，队列已满。
 （这种方式是牺牲一个存储空间来判断队列是否已满）
 注意：判满时 需要对maxsize取余，否则rear可能超出maxsize。
 
第二种方式：
 单独设置一个length变量，来存储队列的长度
 判空：length = 0
 判满：length = maxsize
 
前篇文章，顺序存储队列基本操作 就是利用length判断长度
 
第三种方式
 设置一个tag参数 tag=1 时队满；tag= 0 时对空。
 判空：当首尾指针指向同一位置时，队列为空。
 判满：tag=1 时队满；tag= 0 时对空。
 
循环队列长度
 
length = （rear + maxsize - front）%maxsize；
 
代码实现
 
/**
 * 循环队列的基本操作
 */
#include <cstdio>

#define maxsize 6  //定义队列中元素的最大个数
/**
 * 定义结构
 */
typedef struct {
    int data[maxsize];  //存放队列元素
    int front,rear;     //对头指针和队尾指针   数组下标也可以表示指针，可以不加*
}SqQueue;

/**
 * 初始化队列，构造一个空的队列
 */
void initQueue(SqQueue &Q){
    Q.front = Q.rear = 0;   //初始化队首队尾指针，构建空的队列
}
/**
 * 判断队列是否为空
 */
bool QueueIsEmpty(SqQueue Q){
    if(Q.front == Q.rear){  //队列为空
        printf("队列为空 \n");
        return true;
    }else{
        return false;
    }
}
/**
 * 入队操作
 * @param Q
 * @param value 入队的值
 */
void enQueue(SqQueue &Q,int value){
    if(Q.front == (Q.rear + 1)%maxsize ){//判断队列是否已满
        printf("队列已满 \n");
        return;
    }
    Q.data[Q.rear] = value; //队尾指针指向新入队的数据
    Q.rear = (Q.rear+1)%maxsize;//rear指针+1 ，此处求余目的是不超出给定的maxsize
}
/**
 * 出队操作,返回出队元素
 * @param Q
 */
int outQueue(SqQueue &Q){
    if(QueueIsEmpty(Q)){ //判断队列是否为空
        printf("队列为空 \n");
        return 0;
    }
    int x = Q.data[Q.front]; //要出队的元素
    Q.front = (Q.front+1)%maxsize;  //首指针后移一位
    return x;
}
/**
 * 读队头元素，并返回
 * @return
 */
 int getHead(SqQueue Q){
     return Q.data[Q.front];
 }
/**
 * 创建完整队列
 * @param Q
 */
void creatQueue(SqQueue &Q){
    //初始化
    initQueue(Q);
    
     int x;
     scanf("%d",&x);
     while(x != 9999){
         enQueue(Q,x);
         if(Q.front == (Q.rear + 1)%maxsize){
             break;
         }
         scanf("%d",&x);
     }

 }
 /**
  * 打印
  * @return
  */
 void print(SqQueue Q){
     for (int i = Q.front; i < Q.rear; ++i) {
         printf("队列中存储的值 %d \n",Q.data[i]);
     }
     /**
      * 由于是循环存储数据，rear指针可能指向2的位置，
      * front指针指向5的位置（这种情况是尾指针跑到了首指针前面，会出现负数）
      * 负数不能取余，所以+maxsize，保证数据的正确，取余会把加的maxsize再去掉
      */
     int length = (Q.rear+maxsize - Q.front)%maxsize;
     printf("队列length %d \n",length);
  }
int main(){
    SqQueue Q;
    printf("--------创建完整队列（入队）--------- \n");
    creatQueue(Q);
    printf("--------打印--------- \n");
    print(Q);
    printf("--------获取队头元素--------- \n");
    int head1 = getHead(Q);
    printf("队头元素 - %d \n",head1);
    printf("--------出队--------- \n");
    int out = outQueue(Q);
    printf("出队元素 - %d \n",out);
    printf("--------获取队头元素--------- \n");
    int head2 = getHead(Q);
    printf("队头元素 - %d \n",head2);

    return 0;
}
 
测试结果
 
--------创建完整队列（入队）---------
12
13
14
15
16
17
18
9999
--------打印---------
队列中存储的值 12
队列中存储的值 13
队列中存储的值 14
队列中存储的值 15
队列中存储的值 16
队列中存储的值 17
队列中存储的值 18
队列length 7
--------获取队头元素---------
队头元素 - 12
--------出队---------
出队元素 - 12
--------获取队头元素---------
队头元素 - 13

 
顺序存储队列基本操作：https://blog.csdn.net/qq_35963993/article/details/106080380