队列

1.什么是队列

  队列是有序列表，遵循先入先出的原则，可以用数组和链表来实现，也属于抽象数据类型（ADT）,加入和删除的操作发生在不同的两端，。队列的概念就好比乘火车时排队买票，先到的人先买到票，买完后就从前端离开，二队伍的后端又陆续有新的乘客加入。

2.队列的分类及实现

   2.1 数组实现

     2.1.1 单向队列

     实现思路：因为队列的输入和输出是从两端去处理，因此需要两个变量分别记录队列前后端的下标，front 会随着输出的数据而发生变化，rear会随着输入的数据而发生变化，maxSize 表示队列中最大的容量， int arr[] 表示用于存放队列的数组。

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; //指向队列头部，分析出front是指向队列头的前一个位置
        rear = -1;  //指向队列尾，指向队列尾的数据(即就是队列最后一个数据)
    }

    //判断队列是否为空
    public boolean isEmply() {
        return front == rear;
    }

    //判断队列是否满
    public boolean isFull() {
        return rear == maxSize - 1;
    }

    //向队列中加入数据---->>>rear
    public void addQueue(int a) {
        if (isFull()) {
            System.out.println("队列已满，不可以加入数据@@@@@@@@@@@@@@@");
            return;
        }
        rear++;
        arr[rear] = a;
    }

    //移除队列中的数据
    public int deleteQueue() {
        if (isEmply()) {
            throw new RuntimeException("队列空，不能取数据");
        }
        front++;
        return arr[front];
    }

    //展示队列中的数据
    public void showQueue() {
        if (isEmply()) {
            throw new RuntimeException("队列空，不能取数据");
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.printf("arr[%d]=%d
", i, arr[i]);
        }
    }

    //获得队列中的头数据
    public int headQueue() {
        if (isEmply()) {
            throw new RuntimeException("队列空，不能取数据");
        }
        return arr[front + 1];
    }

}

     2.1.2 环形队列

  单向队列的不足：前面我们讲到单向队列，我们会发现在队列中加入和删除数据时，因为队列需要两个指针 front ,rear来指向它的底部和顶端。所以当rear=n(队列容量满时)，会产生一个问题，如图下图所示：

 从图中可以看出明明队列中还有Q(1)和Q(2)两个空间，当rear=4,所以会认为队列已满，新的数据data5不能加入，这时候环形队列出场了。

实现思路：

 在环形队列中最多只允许存放n-1个数据（也就是牺牲最后一个空间），front 就指向队列的第一个元素，指向队列的最后一个元素的后一个位置，maxSize 队列的最大容量，arr存放队列的数组。如下图分析：

 可以看出判断环形对列满（rear+1）% maxSize,判断队列为空 front =rear

class CirQueue{
  private int maxSize; //队列的最大容量
  private int front;// front 就指向队列的第一个元素, 也就是说 arr[front] 就是队列的第一个元素
  private int rear;//rear 指向队列的最后一个元素的后一个位置. 因为希望空出一个空间做为约定
  private int arr[] ;//存放队列的数组

  public CirQueue(int arrMaxSize){
      maxSize=arrMaxSize;
      arr=new int[maxSize];
      front=0;
      rear=0;
  }

     /**
     * 判断队列是否满
     */
    public boolean isFull(){
         return (rear+1)%maxSize==front;
    }
    /**
     * 判断队列是否为空
     */
    public boolean isEmply(){
        return front==rear;
    }

     /**
     * 向队列中添加元素
     */
    public void addQueue(int a){
     if (isFull()){
         System.out.println("队列已满！！！");
         return;
     }
     arr[rear]=a;
     rear=(rear+1) % maxSize;
    }

    /**
     * 向队列取元素
     */
    public  int deleteQueue(){
        if (isEmply()){
            System.out.println("队列为空");
        }
        int intVal=arr[front];
        front=(front+1) % maxSize;
        return intVal;

    }

    /**
     * 显示队列中的数据
     */
    public void showQueue(){
        if (isEmply()){
            System.out.println("队列为空");
            return;
        }
        for (int i = front; i <front+size() ; i++) {
            System.out.printf("arr[%d]=%d
",i%maxSize,arr[i%maxSize]);
        }
    }

    /**
     * 判断队列中有效的个数
     */
    public int size(){
        return (rear+maxSize-front)%maxSize;
    }

    public int headQueue(){
        if (isEmply()){
            System.out.println("队列不能为空");
        }
        return arr[front];
    }
}

每天进步一丢丢

完成。