数据结构note3:队列的实现——循环数组队列

54 阅读 0 评论 36 点赞

我是靠谱客的博主妩媚马里奥，最近开发中收集的这篇文章主要介绍数据结构note3:队列的实现——循环数组队列，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

 * 用循环数组实现队列
 * 队列：从尾入队，从头出队。
 * rear-1指向尾元素
 * front指向头元素
 */
public class CircleArrayQueue {

    public static void main(String[] args) {
        CircleArrayQueue circleArrayQueue = new CircleArrayQueue(3);
        System.out.println(circleArrayQueue.getSize());//队列数据个数
        System.out.println(circleArrayQueue.isEmpty());//是否为空
        circleArrayQueue.addQueue(1);//加入元素
        circleArrayQueue.addQueue(2);
        circleArrayQueue.addQueue(3);
        System.out.println(circleArrayQueue.getSize());
        circleArrayQueue.showQueue();//输出队列
        System.out.println(circleArrayQueue.getQueue());//出队，并返回队首front的元素。
        System.out.println(circleArrayQueue.getSize());
        circleArrayQueue.showQueue();

    }

    private int maxSize;//数组最大容量
    private int front;//头指针，指向第一个元素。
    private int rear;//尾指针，指向最后一个元素的后一个元素。
    private int arr[];//存放数据的数组

    /**
     * 队列有入队和出队功能，需要判断队是否为空
     */

    //初始化数组
    public CircleArrayQueue(int arrMaxSize){
//        front = 0;//初始指向第一个元素         系统默认为0
//        rear = 0;//初始指向第一个元素（第一个元素前一个元素是最后一位）
        maxSize = arrMaxSize + 1;//默认数组空一个位置，所以需要创建一个大一位的数组，后一位预留，什么都不放。
        arr = new int[maxSize];
    }

    //是否满。判断条件是：(rear + 1)%maxSize == front
    //原因：本次设计空出了一位数组元素，解释在下一个方法上
    // 如果数组满了，rear+1就是front的下标。
    //%maxSize是因为，当最后一个元素存入时，rear指向最后一个元素（设计为不存元素的位置），rear+1会超出数组下标，需要%maxSize.
    //也就是说，当front(第一个元素)下标=0时，rear+1必须%maxSize才为0，否则rear+1=maxsize。数组下标越界。
    public boolean isFull(){
        return (rear+1)%maxSize == front;
    }

    //是否为空
    //为什么要在设计时空出最后一个元素后一位？
    //因为不空出来的话，判断队列满（rear%maxSize = front）和队列空（front = rear）重复，所以要留出一位不使用的空间。
    public boolean isEmpty(){
        //front默认指向第一个元素，rear默认指向最后一个元素的后一位。
        // 当从队尾出队到最后一位后一位时，front(从front出队)=rear。
        return rear == front;
    }

    //数据入队
    public boolean addQueue(int element){
        if (isFull()){
            System.out.println("队列已满，无法加入数据！");
            return false;
        }
        arr[rear] = element;
        //循环队列，必须对索引进行取余
        rear = (rear + 1)%maxSize;
        return true;
    }

    //取出数据，并出队
    public int getQueue(){
        if (isEmpty()){
            throw new RuntimeException("数组为空！无法取出数据");
        }
        //要取出数据，必须先保存arr[front]的值，把front后移
        int firstValue = arr[front];
        front = (front + 1)%maxSize;//取余原理相同，当front是数组最后一个元素时，+1会等于maxSize,数组下标越界
        return firstValue;
    }

    //遍历队列，显示队列的所有数据
    public void showQueue(){
        if (isEmpty()){
            System.out.println("队列是空的，没有数据！");
            return;
        }
        //遍历需要从front开始遍历，遍历有效数据的个数（多少个元素）
        for (int i = front; i < front + getSize(); i++) {
            //把i取余，跨过数组下标0就重新确定数组下标
            System.out.println("第"+i+"个元素："+arr[i%maxSize]);
        }
    }

    //获得队列中所有数据的个数
    public int getSize(){
        //rear是最后一个元素后一位，front是第一位，相减得出rear和front队列中间的数据个数。
        //maxSize - front：rear跨过数组下标0时，maxSize-front=数组中front到数组最后一个下标maxSize-1之间的数据个数。
        //+rear：把maxSize-front的个数，加上rear的个数（从下标0到下标rear之间的元素个数），等于总的队列的数据个数。
        //(maxSize-front+rear)是队列总的数据个数。
        // %maxSize是因为当front和rear都在数组下标0-(maxSize-1)时，队列数据总个数=rear-front。%maxSize可以把这两种情况合并简化。
        return (maxSize-front+rear)%maxSize;
    }


    // 显示头元素
    public int headQueue() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空，没有数据！");
        }
        return arr[front];
    }

}