java数据结构，一个案例带你用数组模拟队列，环形队列！

谁借莪１个温暖的怀抱￠ 2022-09-04 09:49 165阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY5MjcwNQ_size_16_color_FFFFFF_t_70]

### 目录 ###

*  队列
 *   *  使用数组模拟队列
     *  使用数组模拟环形队列

--------------------

# 队列 #

*  队列是一个有序列表，可以用`数组(顺序存储)`或是`链表(链式存储)`来实现。
 *  遵循`先入先出`的原则。即：先存入队列的数据，要先取出。后存入的要后取出。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY5MjcwNQ_size_16_color_FFFFFF_t_70 1]

--------------------

## 使用数组模拟队列 ##

*  队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图，其中maxSize是该队列的最大容量。
 *  因为队列的输出，输入是分别从前后端来处理，因此需要两个变量front及rear分别记录队列前后端的下标，front会随着数据输出从而改变，而rear则是随着数据输入而改变。

> **如图所示：**  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY5MjcwNQ_size_16_color_FFFFFF_t_70 2]

**思路分析：**

> **当我们将数据存入队列时称为 `addQueue`，`addQueue` 的处理需要有两个步骤**

1.  将尾指针往后移：`rear+1`，当`front == rear[空]`
2.  若尾指针 `rear` 小于队列的最大下标 `maxSize - 1`，则将数据存入 `rear` 所指的数组元素中，否则无法存入数据。`rear == maxSize -1[队列满]`。

**代码实现：**

> **使用数组模拟队列，编写一个ArrayQueue类**

class ArrayQueue{
        
       
            private int maxSize; //表示数组的最大容量
            private int front; //队列头
            private int rear; //队列尾
            private int [] arr; //该数组用于存放数据，模拟队列
    
            //创建队列的构造器
            public ArrayQueue(int arrMaxSize){
        
                this.maxSize=arrMaxSize;
                this.arr=new int[this.maxSize];
                this.front=-1; //指向队列头部，分析出front是指向队列头的前一个位置。
                this.rear=-1; //指向队列尾，指向队列尾的数据(就是队列中最后一个数据)。
            }
    
            //判断队列是否满
            public boolean isFull(){
        
                return this.rear == this.maxSize-1;
            }
    
            //判断队列是否为空
            public boolean isEmpty(){
        
                return this.rear == this.front;
            }
    
            //添加数据到队列
            public void addQueue(int n){
        
                if (isFull()){
        
                    System.out.println("队列满，不能加入数据");
                    return;
                }
                this.rear++; //让rear后移
                this.arr[rear]=n;
            }
            
            //获取队列的数据，出队列
            public int getQueue(){
        
                //判断队列是否为空
                if (isEmpty()){
        
                    //通过抛出异常
                    throw new RuntimeException("队列空，不能取数据");
                }
                front++; //front后移
                return arr[front];
            }
    
            //显示队列的所有数据
            public void showQueue(){
        
                if (isEmpty()){
        
                    System.out.println("队列空，没有数据");
                }
                for (int i=0;i<arr.length;i++){
        
                    System.out.printf("arr[%d]=%d\n",i,arr[i]);
                }
            }
    
            //显示队列的头数据，注意：不是取数据
            public int headQueue(){
        
                //判断
                if (isEmpty()){
        
                    throw new RuntimeException("队列空的，没有数据");
                }
                return arr[front+1];
            }
        }

> **对模拟队列进行测试**

public static void main(String[] args) {
        
            ArrayQueue arrayQueue= new ArrayQueue(3);
            Scanner inpunt =new Scanner(System.in);
            Boolean b=true;
            do {
        
                switch (inpunt.nextInt()){
        
                    case 1:{
        
                        try {
        
                            System.out.println("显示队列所有数据");
                            arrayQueue.showQueue();
                        }catch (Exception e){
        
                            e.printStackTrace();
                        }
                        break;
                    }
                    case 2:{
        
                        System.out.println("添加数据到队列");
                        arrayQueue.addQueue(inpunt.nextInt());
                        break;
                    }
                    case 3:{
        
                        try {
        
                            System.out.println("显示队列的头数据");
                            int headQueue = arrayQueue.headQueue();
                            System.out.println("队列头："+headQueue);
                        }catch (Exception e){
        
                            e.printStackTrace();
                        }
                        break;
                    }
                    case 4:{
        
                        try {
        
                            System.out.println("从队列中取数据");
                            int queueQueue = arrayQueue.getQueue();
                            System.out.println("取数据："+queueQueue);
                        }catch (Exception e){
        
                            e.printStackTrace();
                        }
                        break;
                    }
                    default:{
        
                        b=false;
                    }
                }
            }while (b);
        }

*  测试1：添加数据并显示队列所有数据 `可以看出现在队列中添加了三个数据分别为 10,20,30`

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY5MjcwNQ_size_16_color_FFFFFF_t_70 3]

*  测试2：查看头数据，然后取出数据后，再次查看头数据 `因为队列遵循先进先出的原则，这边取完数据再查看队列，头数据为第二次添加的数据。`

![在这里插入图片描述][2021062023253819.png]

*  测试3：取出所有数据在添加数据。`注意看这里，当我们数据取完后，在添加数据就会出现问题。`  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY5MjcwNQ_size_16_color_FFFFFF_t_70 4]

> **问题分析及优化：**
> 
>  *  目前我们的数组使用一次就不能用了，没有达到复用的效果。
>  *  我们可以将这个数组使用算法改进成一个环形的队列。

--------------------

## 使用数组模拟环形队列 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY5MjcwNQ_size_16_color_FFFFFF_t_70 5]  
**思路分析**

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

**代码实现**

> 对前面的数组模拟队列进行优化，充分利用数组，因此将数组看作是一个环形的。(通过取模的方式来实现即可)

class CircleArray{
        
        private int maxSize; //表示数组的最大容量
        //front变量的含义做一个调整，front就指向队列的第一个元素，也就是说 arr[front]就是队列的第一个元素，front的初始值 = 0；
        private int front;
        //rear 变量的含义也做一个调整，rear指向队列的最后一个元素的最后一个位置。因为希望空出一个空间做为约定。rear的初始值也 = 0;
        private int rear;
        private int [] arr; //该数组用于存放数据，模拟队列
    
    
        public CircleArray(int arrMaxSize){
        
            maxSize = arrMaxSize;
            arr = new int[maxSize];
        }
    
        //判断队列是否满
        public boolean isFull(){
        
            return (rear + 1) % maxSize == front;
        }
    
        //判断队列是否为空
        public boolean isEmpty(){
        
            return this.rear == this.front;
        }
    
        //添加数据到队列
        public void addQueue(int n){
        
            if (isFull()){
        
                System.out.println("队列满，不能加入数据");
                return;
            }
            //直接将数据加入
            arr[rear] = n;
            //将 rear 后移，这里必须考虑去模
            rear = (rear + 1) % maxSize;
        }
    
        //获取队列的数据，出队列
        public int getQueue(){
        
            //判断队列是否为空
            if (isEmpty()){
        
                //通过抛出异常
                throw new RuntimeException("队列空，不能取数据");
            }
            /**
             *   这里需要分析出 front 是指向队列的第一个元素
             *   1.先把 front 对应的值保留到一个临时变量
             *   2.将 front 后移，考虑取模
             *   3.将临时保存的变量返回
             */
            int value = arr[front];
            front = (front + 1) % maxSize;
            return value;
        }
    
        //显示队列的所有数据
        public void showQueue(){
        
            //遍历
            if (isEmpty()){
        
                throw  new RuntimeException("队列空，没有数据");
            }
            //思路：从front开始遍历，遍历多少个元素
            for (int i= front; i < front + size();i++){
        
                System.out.printf("arr[%d]=%d\n",i % maxSize,arr[i % maxSize]);
            }
        }
    
        //求出当前队列有效数据的个数
        public int size(){
        
            return (rear + maxSize - front) % maxSize;
        }
    
    
        //显示队列的头数据，注意：不是取数据
        public int headQueue(){
        
            //判断
            if (isEmpty()){
        
                throw new RuntimeException("队列空的，没有数据");
            }
            return arr[front];
        }
    
    }

> **对环形队列进行测试**

public static void main(String[] args) {
        
            //测试数组模拟环形队列
            CircleArray circleArray= new CircleArray(4);  //设置4,其队列的有效数据最大是3
            Scanner inpunt =new Scanner(System.in);
            Boolean b=true;
            do {
        
                switch (inpunt.nextInt()){
        
                    case 1:{
        
                        try {
        
                            System.out.println("显示队列所有数据");
                            circleArray.showQueue();
                        }catch (Exception e){
        
                            e.printStackTrace();
                        }
                        break;
                    }
                    case 2:{
        
                        System.out.println("添加数据到队列");
                        circleArray.addQueue(inpunt.nextInt());
                        break;
                    }
                    case 3:{
        
                        try {
        
                            System.out.println("显示队列的头数据");
                            int headQueue = circleArray.headQueue();
                            System.out.println("队列头："+headQueue);
                        }catch (Exception e){
        
                            e.printStackTrace();
                        }
                        break;
                    }
                    case 4:{
        
                        try {
        
                            System.out.println("从队列中取数据");
                            int queueQueue = circleArray.getQueue();
                            System.out.println("取数据："+queueQueue);
                        }catch (Exception e){
        
                            e.printStackTrace();
                        }
                        break;
                    }
                    default:{
        
                        b=false;
                    }
                }
            }while (b);
        }

*  测试1往环形队列中添加数据  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY5MjcwNQ_size_16_color_FFFFFF_t_70 6]
 *  测试2 从环形队列中取数据  
    ![在这里插入图片描述][20210703153035186.png]
 *  测试3 取数据后重新添加数据  
    ![在这里插入图片描述][20210703153101911.png]

--------------------

**更多精彩文章请访问 [Cs挽周][Cs]** ！![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY5MjcwNQ_size_16_color_FFFFFF_t_70 7]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY5MjcwNQ_size_16_color_FFFFFF_t_70]: /images/20220829/92b0a332824c420f80f6f1613dd5534e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY5MjcwNQ_size_16_color_FFFFFF_t_70 1]: /images/20220829/116f28ed60db42d9afb69f3aad50af12.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY5MjcwNQ_size_16_color_FFFFFF_t_70 2]: /images/20220829/099952668d67442193b4f882cadbd182.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY5MjcwNQ_size_16_color_FFFFFF_t_70 3]: /images/20220829/5155deb77b134305896058980e1da1fe.png
[2021062023253819.png]: /images/20220829/5bf59615df1743889a58b0f868363ca8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY5MjcwNQ_size_16_color_FFFFFF_t_70 4]: /images/20220829/5d001e78d337409d8db73c5bbeda6c4e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY5MjcwNQ_size_16_color_FFFFFF_t_70 5]: /images/20220829/8628d722bd334f5c8695c8b9e928ed45.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY5MjcwNQ_size_16_color_FFFFFF_t_70 6]: /images/20220829/1925f3941af649b5ae9adda0de98925b.png
[20210703153035186.png]: /images/20220829/2f7f9e7edd344cf7818de57a28e4672a.png
[20210703153101911.png]: /images/20220829/521df7eb84df4074b3e6aebcd2718574.png
[Cs]: https://blog.csdn.net/weixin_45692705?spm=1011.2124.3001.5343
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY5MjcwNQ_size_16_color_FFFFFF_t_70 7]: /images/20220829/f217f73b85024873970e198ff9b35c5c.png