数组实现环形队列 详细讲解（java）

数组实现环形队列 详细讲解

数组模拟环形队列

对前面的数组模拟队列的优化，将数组看做是一个环形的。(通过取模的方式来实现即可)

解题思路

1、既然是环形队列，那就一定有头有尾，有容量

2、既然是数组实现，那一定有个算法保证可以让数组循环起来

如图所示：
rear为7 ，front为0，实际的数据为7，是因为rear定义指向了最后一个元素的后一个位置，所以满数组的size变成了size-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 front = 0
6. 我们就可以在原来的队列上修改得到，一个环形队列

代码实现

package com.qf;import java.util.Scanner;public class CircleQueue {    private int maxSize;    private int front;    private int rear;    private int[] arr;    /     * 环形队列的实现     */    //初始化环型队列    public CircleQueue(int maxSize){ this.arr=new int[maxSize]; this.maxSize=maxSize; this.front=0; this.rear=0;    }    //队列是否已满    public boolean isFull(){ return (rear+1)%maxSize==front;    }    //队列是否为空    public boolean isEmpty(){ return rear==front;    }    //入队    public void addQueue(int num){ if (isFull()){     System.out.println("队列已满，请稍等~~~"); }else{     arr[rear]=num;     rear=(rear+1)%maxSize; }    }    //出队    public int outQueue(){ if (isEmpty()){     throw new RuntimeException("队列为空，不能出队~~"); } int outNum=arr[front]; System.out.println("出队的数值为："+outNum); front=(front+1)%maxSize; return outNum;    }    //循环队列有效元素    public void showQueue(){ if (isEmpty()){     throw new RuntimeException("队列为空~~"); } for (int i = front; i < front+size(); i++) {     System.out.printf(" " +arr[i%maxSize]); }    }    //得到对头的元素    public int getHeader(){ if (isEmpty()){     throw new RuntimeException("队列为空~~"); } System.out.println("对头元素："+arr[front%maxSize]); return arr[front%maxSize];    }    //得出有效元素的个数    public int size(){ return (rear+maxSize-front)%maxSize;    }    public static void main(String[] args) { CircleQueue queue = new CircleQueue(4); boolean loop=true; char sc=' '; while (loop){     System.out.println("e 跳出循环");     System.out.println("a 入队");     System.out.println("o 出队");     System.out.println("s 循环队列");     System.out.println("h 展示队头");     Scanner systemPut=new Scanner(System.in);     sc=systemPut.next().charAt(0);     switch (sc){  case 'a':      System.out.println("请输入数据：");      Scanner addNum=new Scanner(System.in);      int num = addNum.nextInt();      queue.addQueue(num);      break;  case 'o':      queue.outQueue();      break;  case 's':      queue.showQueue();      break;  case 'h':      queue.getHeader();      break;  case 'e':      loop=false;      break;  default :      break;     } }    }}