数组构造队列数组构造队列优化成循环队列总结

80 阅读 0 评论 53 点赞

我是靠谱客的博主难过金针菇，最近开发中收集的这篇文章主要介绍数组构造队列数组构造队列优化成循环队列总结，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

数组构造队列

class ArrayQueue{
        private int[] arr;
        private int maxSize = 10;  //队列容量,默认容量为10
        private int front;  //队头
        private int rear;   //队尾

        public ArrayQueue(){
            arr = new int[this.maxSize];
            front = rear = -1;
        }
        public ArrayQueue(int maxSize){
            this.maxSize = maxSize;
            arr = new int[this.maxSize];
            front = rear = -1;
        }
        //判断队列是否已满
        public Boolean isFull(){
            return rear == maxSize-1;
        }
        //判断队列是否为空
        public Boolean isEmpty(){
            return front==rear;
        }
        //数据入队
        public void enterQueue(int data){
            if(isFull()) throw new RuntimeException("队列以满");
            arr[++rear] = data;
        }
        //数据出队
        public int getQueue(){
            if (isEmpty()) throw new RuntimeException("队列为空");
            return arr[++front];
        }
        //显示队头数据
        public int ShowFrontQueue(){
            if(isEmpty()) throw new RuntimeException("队列为空");
            return arr[front+1];
        }
        //遍历队列
        public void traverseQueue(){
            if(isEmpty()) throw new RuntimeException("队列为空");
            for(int i=1;front+i<=rear;i++) System.out.println(arr[front+i]);
        }
    }

在上面的队列构造中，存在一个最大的问题就是，当数据入队到数组的最大容量后，此时rear=MaxSize-1，表示队列已满。数据出队后，前面的空间（图上变黄的地方）虽然空出来了，但是依然无法插入数据进去。这样构造的队列每个空间只能利用一次。

为了达到重复利用，需要优化成循环队列，允许队头和队尾围绕一个圈移动。

优化成循环队列

构造成环形队列不唯一，可根据实际情况构造。不同的设计在计算队列是否为空，是否已满的算法上存在不同。

构造第一种环形队列

class ArrayQueue{
    private int[] arr;
    private int maxSize = 10;  //队列容量,默认容量为10
    private int front;  //队头
    private int rear;   //队尾

    public ArrayQueue(){
        arr = new int[this.maxSize];
        front = rear = -1;
    }
    public ArrayQueue(int maxSize){
        this.maxSize = maxSize;
        arr = new int[this.maxSize];
        front = rear = -1;
    }
    //判断队列是否已满
    public Boolean isFull(){
        return (rear-front)%maxSize==0&&arr[0]!=0;  //值等于0表示此空间没有数据作为前提条件
    }
    //判断队列是否为空
    public Boolean isEmpty(){
        return (rear-front)%maxSize==0&&arr[0]==0;
    }
    //数据入队
    public void enterQueue(int data){
        if(isFull()) throw new RuntimeException("队列以满");
        rear = (rear+1)%maxSize;
        arr[rear] = data;
    }
    //数据出队
    public int getQueue(){
        if (isEmpty()) throw new RuntimeException("队列为空");
        front = (front+1)%maxSize;
        //出队把数据还原成0
        int temp = arr[front];
        arr[front] = 0;
        return temp;
    }
    //显示队头数据
    public int ShowFrontQueue(){
        if(isEmpty()) throw new RuntimeException("队列为空");
        return arr[(front+1)%maxSize];
    }
    //遍历整个数组
    public void traverseQueue(){
        if(isEmpty()) throw new RuntimeException("队列为空");
        for(int i=0;i<maxSize;i++) System.out.print(arr[i]+" ");
    }
}

构造第二种环形队列

class ArrayQueue{
    private int[] arr;
    private int maxSize = 10;  //队列容量,默认容量为10
    private int front;  //队头
    private int rear;   //队尾

    public ArrayQueue(){
        arr = new int[this.maxSize];
        front = rear = 0;
    }
    public ArrayQueue(int maxSize){
        this.maxSize = maxSize;
        arr = new int[this.maxSize];
        front = rear = 0;
    }
    //判断队列是否已满
    public Boolean isFull(){
        return (rear+1)%maxSize==front;  //值等于0表示此空间没有数据作为前提条件
    }
    //判断队列是否为空
    public Boolean isEmpty(){
        return rear == front;
    }
    //数据入队
    public void enterQueue(int data){
        if(isFull()) throw new RuntimeException("队列以满");
        arr[rear] = data;
        rear = (rear+1)%maxSize;
    }
    //数据出队
    public int getQueue(){
        if (isEmpty()) throw new RuntimeException("队列为空");
        int temp = arr[front];
        front = (front+1)%maxSize;
        return temp;
    }
    //显示队头数据
    public int ShowFrontQueue(){
        if(isEmpty()) throw new RuntimeException("队列为空");
        return arr[front];
    }
    //遍历整个数组
    public void traverseQueue(){
        if(isEmpty()) throw new RuntimeException("队列为空");
        for(int i=0;i<maxSize;i++) System.out.print(arr[i]+" ");
    }
}