• 数据结构：循环队列

    之前已经做过队列的学习笔记，这一篇写的是循环队列，大部分代码可以继续沿用，某些地方需要作出更改，使其可以实现循环队列的功能。

    通俗的总结一下队列的操作，我的思路是将头指针固定不动，然后每一次元素入队就将尾指针后移，每一次出队就把当前头指针指向的元素返回，然后将整个数组整体前移一个位置，尾指针同时减一。而循环队列可以看作将数组围成一个圆形，头指针和尾指针都会根据入队与出队而发生改变，这样就可以省去队列数据结构出队时需要将出队元素除外的其他所有元素整体前移，从而增加了效率。

    创建一个CircleQueue类，rear表示尾指针，front表示头指针，size表示用于实现循环队列的数组大小，而arr就是用于实现循环队列的数组。

    1. class CircleQueue{
    2.     private int rear;
    3.     private int front;
    4.     private int size;
    5.     private int[] arr;
    6. }

    一、构造循环队列

    与普通队列不同的是，头指针front与尾指针rear的初始值都设置为0，并且由于循环队列中需要空出一个位置用于判断和保持操作一致，因此数组实际大小应该比用户期待队列的大小大1，因此size的值应该为用户期待队列大小的值maxsize加一。

    1.     public CircleQueue(int maxsize){
    2.         size = maxsize + 1;
    3.         arr = new int[size];
    4.         rear = 0;
    5.         front = 0;
    6.     }

    二、判断循环队列是否已满

    由于队列是循环的，因此判满的方法也需要更改。当尾指针+1的值对队列大小size取模的结果值刚好为头指针的值则代表队列已满。（用文字描述难免有些晦涩，在草稿画个环作数组运算一下便于理解。）

    1.     public boolean isFull(){
    2.         return (rear + 1) % size == front;
    3.     }

    三、判断循环队列是否已空

    当尾指针rear与头指针front重叠时，即证明当前队列为空。（队列已满应该为两指针相邻，所以才有判满的那条公式(rear+1)(rear+1)。这也是循环数组需要预留一个位置用于判断，否则判满与判空的条件很可能就相同从而无法判断了。)

    1.     public boolean isEmpty(){
    2.         return rear == front;
    3.     }

    四、元素入队

    入队前，判满操作还是不能少。通过判断后，将出入元素element保存在rear所指向的位置，然后rear指针按照公式(rear+1)(rear+1)移动（为了实现循环，需要取模操作）。最后打印“入队成功提示”作提示。

    1.     public void addQueue(int element){
    2.         if(isFull()){
    3.             //throw new RuntimeException("队列已满！");
    4.             System.out.println("队列已满！");
    5.             return;
    6.         }
    7.         arr[rear] = element;
    8.         rear = (rear +1) % size;
    9.         System.out.println("入队成功！");
    10.     }

    五、元素出队

    出队前同样需要判空操作。接着先将出队元素用临时变量ans保存着，然会按公式移动front指针，让front后退一个位置，最后返回出队元素。

    1.     public int getQueue(){
    2.         if(isEmpty()){
    3.             throw new RuntimeException("队列已空！");
    4.         }
    5.         int ans = arr[front];
    6.         front = (front + 1) % size;
    7.         return ans;
    8.     }

    六、展示队列

    循环队列的展示队列操作有点点绕。第一步判空操作（可有可无）。getSzie方法就是计算从rear到size之间的距离，因为是循环队列，所以也需要进行取模运算。计算后，在showQueue方法中，以front为起点，直至front加上相距距离。但是在打印时不能用i作为数组下标，这样很可能会出现数组越界。为了使下标正确，还需要对i进行取模运算，运算结果才是正确的数组下标。最后实现遍历循环队列，输出打印。

    1.     public void showQueue(){
    2.         if(isEmpty()){
    3.             System.out.println("队列为空，没有数据~");
    4.             return;
    5.         }
    6.         System.out.println("队列展示：");
    7.         for(int i = front ; i < front + getSize(); i++){
    8.             System.out.println(arr[i % size]);
    9.             //System.out.println(arr[i]);
    10.         }
    11. //        System.out.println("front:" + front);
    12. //        System.out.println("getsize:" + getSize());
    13.     }
    14.     public int getSize(){
    15.         return (rear + size -front) % size;
    16.     }

    七、获取队首元素

    这个方法与普通队列中完全相似，同样先判空，若符合要求则返回队首元素。在此不再赘述。

    1.     public void rearQueue(){
    2.         if(isEmpty()){
    3.             System.out.println("队列为空，peek不了啦~");
    4.             return;
    5.         }
    6.         System.out.println("队头元素是：" + arr[front]);
    7.     }

    八、界面

    界面保持一致，不需要作更改。将代码再放一次在这里。

    1. public class CircleArray {
    2.     public static void main(String[] args){
    3.         Scanner input = new Scanner(System.in);
    4.         boolean flag = true;
    5.         char key = ' ';
    6.  
    7.         System.out.print("请输入队列大小：");
    8.         Scanner inputs = new Scanner(System.in);
    9.         int size = inputs.nextInt();
    10.         CircleQueue AQ = new CircleQueue(size);
    11.  
    12.         while(flag){
    13.             System.out.println("---------------------------");
    14.             System.out.println("|（1）退出程序：e（exit）     |");
    15.             System.out.println("|（2）元素入队：a（add）      |");
    16.             System.out.println("|（3）元素出队：g（get）      |");
    17.             System.out.println("|（4）查询队头：p（peek）     |");
    18.             System.out.println("|（5）展示队列：s（show）     |");
    19.             System.out.println("---------------------------");
    20.             System.out.print("【输入字母选择操作】");
    21.             key = input.next().charAt(0);
    22.             switch (key){
    23.                 case 'a':
    24.                     System.out.print("入队元素：");
    25.                     int element = input.nextInt();
    26.                     AQ.addQueue(element);
    27.                     break;
    28.                 case 'g':
    29.                     System.out.println("出队元素是：" + AQ.getQueue());
    30.                     break;
    31.                 case 'p':
    32.                     AQ.rearQueue();
    33.                     break;
    34.                 case 's':
    35.                     AQ.showQueue();
    36.                     break;
    37.                 case 'e':
    38.                     System.out.println("成功退出...");
    39.                     flag = false;
    40.                     break;
    41.                 default:
    42.                     System.out.println("输入不合法，请重新输入~");
    43.             }
    44.  
    45.         }
    46.     }
    47.  
    48. }

    完整代码：

    1. import java.util.Scanner;
    2.  
    3. public class CircleArray {
    4.     public static void main(String[] args){
    5.         Scanner input = new Scanner(System.in);
    6.         boolean flag = true;
    7.         char key = ' ';
    8.  
    9.         System.out.print("请输入队列大小：");
    10.         Scanner inputs = new Scanner(System.in);
    11.         int size = inputs.nextInt();
    12.         CircleQueue AQ = new CircleQueue(size);
    13.  
    14.         while(flag){
    15.             System.out.println("---------------------------");
    16.             System.out.println("|（1）退出程序：e（exit）     |");
    17.             System.out.println("|（2）元素入队：a（add）      |");
    18.             System.out.println("|（3）元素出队：g（get）      |");
    19.             System.out.println("|（4）查询队头：p（peek）     |");
    20.             System.out.println("|（5）展示队列：s（show）     |");
    21.             System.out.println("---------------------------");
    22.             System.out.print("【输入字母选择操作】");
    23.             key = input.next().charAt(0);
    24.             switch (key){
    25.                 case 'a':
    26.                     System.out.print("入队元素：");
    27.                     int element = input.nextInt();
    28.                     AQ.addQueue(element);
    29.                     break;
    30.                 case 'g':
    31.                     System.out.println("出队元素是：" + AQ.getQueue());
    32.                     break;
    33.                 case 'p':
    34.                     AQ.rearQueue();
    35.                     break;
    36.                 case 's':
    37.                     AQ.showQueue();
    38.                     break;
    39.                 case 'e':
    40.                     System.out.println("成功退出...");
    41.                     flag = false;
    42.                     break;
    43.                 default:
    44.                     System.out.println("输入不合法，请重新输入~");
    45.             }
    46.  
    47.         }
    48.     }
    49.  
    50. }
    51.  
    52. class CircleQueue{
    53.     private int rear;
    54.     private int front;
    55.     private int size;
    56.     private int[] arr;
    57.  
    58.     //构造
    59.     public CircleQueue(int maxsize){
    60.         size = maxsize + 1;
    61.         arr = new int[size];
    62.         rear = 0;
    63.         front = 0;
    64.     }
    65.  
    66.     //判满
    67.     public boolean isFull(){
    68.         return (rear + 1) % size == front;
    69.     }
    70.  
    71.     //判空
    72.     public boolean isEmpty(){
    73.         return rear == front;
    74.     }
    75.  
    76.     //入队
    77.     public void addQueue(int element){
    78.         if(isFull()){
    79.             //throw new RuntimeException("队列已满！");
    80.             System.out.println("队列已满！");
    81.             return;
    82.         }
    83.         arr[rear] = element;
    84.         rear = (rear +1) % size;
    85.         System.out.println("入队成功！");
    86.     }
    87.  
    88.     //出队
    89.     public int getQueue(){
    90.         if(isEmpty()){
    91.             throw new RuntimeException("队列已空！");
    92.         }
    93.         int ans = arr[front];
    94.         front = (front + 1) % size;
    95.         return ans;
    96.     }
    97.  
    98.     //展示队列
    99.     public void showQueue(){
    100.         if(isEmpty()){
    101.             System.out.println("队列为空，没有数据~");
    102.             return;
    103.         }
    104.         System.out.println("队列展示：");
    105.         for(int i = front ; i < front + getSize(); i++){
    106.             System.out.println(arr[i % size]);
    107.             //System.out.println(arr[i]);
    108.         }
    109. //        System.out.println("front:" + front);
    110. //        System.out.println("getsize:" + getSize());
    111.     }
    112.     public int getSize(){
    113.         return (rear + size -front) % size;
    114.     }
    115.  
    116.     //peek
    117.     public void rearQueue(){
    118.         if(isEmpty()){
    119.             System.out.println("队列为空，peek不了啦~");
    120.             return;
    121.         }
    122.         System.out.println("队头元素是：" + arr[front]);
    123.     }
    124.  
    125.     //
    126.  
    127. }

  • 相关阅读:
    [附源码]计算机毕业设计springboot疫情防控平台
    python-第12章 魔法方法
    图的拓扑排序(入门篇)
    快速弄懂C++中的深拷贝和浅拷贝
    [附源码]计算机毕业设计JAVA医院床位管理系统
    Codeforces Round #811 (Div. 3) ABC题解
    Transformation 和 Action 常用算子
    快速增长的庞大市场：Jelurida非洲分部助力金融包容性方案
    Elasticsearch 如何实现时间差查询？
    Android之使用GirdLayoutManager时候给Item设置边距
  • 原文地址：https://blog.csdn.net/Hokachi/article/details/127875769