数组模拟实现环形队列

一时失言乱红尘 2024-03-26 23:17 72阅读 0赞

**目录**

前言

一、什么是队列?

二、数组模拟非环形队列的实现

三 . 数组模拟环形队列

总结

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

## 前言 ##

> 笔者: 最爱吃兽奶
> 
> 博文内容: 数据结构队列的模拟实现
> 
> 这篇博客理解起来或许没有那么简单,我尽力讲的容易理解一点,接下来跟我一起去看看吧!
> 
> ![c051e87c3ca54507b3dd458999e0d7a3.jpeg][]

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

## 一、什么是队列? ##

队列是一种特殊的线性数据结构，它遵循**先进先出**（First In First Out，FIFO）的原则。队列可以看作是一种排队的数据结构，类似于现实生活中的排队。在队列中，新元素被添加到队列的末尾，而从队列中移除元素的操作只能从队列的前端进行。

![18ea790aef80458ca55f6d1df4688e15.png][]

上图八个小球按序号依次入队列

队列有两个基本操作：入队（enqueue）和出队（dequeue）。入队操作将一个元素添加到队列的末尾，而出队操作则从队列的前端移除一个元素。除了入队和出队操作，队列还可以支持其他操作，如获取队列的长度、判断队列是否为空等。

队列的应用场景:银行排队案例

![ab3a95d35e2545b99840774f5c4cac62.png][]

## 二、数组模拟非环形队列的实现 ##

图解:

![c0f32c53e7ec4797b319b20d7b9496b4.png][]

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

代码实现:

下面给出基础代码,入队列/出队列的方法我们单独来实现

>     public class QueueDemo {
>         private int capacity;
>         private int front;
>         private int rear;
>         private int[] Queue;
>         
>         public QueueDemo(int capacity){
>             this.capacity = capacity;
>             Queue = new int[capacity];
>             front = -1;
>             rear = -1;
>         }
>     }
> 
>     // 判断队列是否已满
>     private Boolean IsFull(){
>         return rear == capacity-1;
>     }
>     
>     // 判断队列是否为空
>     private Boolean IsEmpty(){
>         return rear == front;
>     }

入队列

>     public void addQueue(int data) throws Exception {
>         if(IsFull()){
>             throw new RuntimeException("队列已满,无法插入新的数据");
>         }
>         arr[++rear] = data;
>     }

出队列

>     public void getQueue(){
>         if(IsEmpty()){
>             throw new RuntimeException("队列为空,无法出队列!");
>         }
>         front++;// front 后移
>     }

问题分析: 可以清楚地看到上面队列并不是可重复利用队列,而实际上的队列则是可以重复利用的,在这里引出环形队列。

## 三 . 数组模拟环形队列 ##

![f6024b1d7f874d948b3b9f24f992f3fc.png][]

思路如下:

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

为什么要留出一个空间作为约定?

如果不留一个空间作为约定,队满和队空的条件就一样了,我们无法区分队满还是队空,所以要留出一个空间作为约定

![baea3b23283d47b9b6cf619e17757ab7.png][]

![efedf378faf54eec9413c75474da71ff.png][] ![f736dd3767304f8e8d0b74bec4bf1961.png][]

下面给出代码具体实现

public class circleQueue {
        private int QueueSize;// 队列容量
        private int front;// 队列首部
        private int rear;// 队列尾部
        private int[] arr;// 该数组用于存放数据,模拟队列
    
        // 构造器
        public circleQueue(int maxSize){
            QueueSize = maxSize;
            front = 0;// 指向队列头部,指向队列头的第一个位置
            rear = 0;// 指向队列尾部,指向队列尾部最后一个元素的下一个位置
            // 约定预留一个空间,如果不预留空间,满和空的条件将会重合
            arr = new int[maxSize];
        }
    
        // 判断是否为空
        public boolean isNull(){
            return rear == front;
        }
    
        // 判断是否已满
        public boolean isFull(){
            return (rear+1)% QueueSize == front;
        }
    
        // 入队列
        public void addQueue(int n){
            if(isFull()){
                throw new RuntimeException("队列已满,不能在增加数据");
            }
            arr[rear] = n;
            rear = (rear+1)%QueueSize;
        }
    
        // 出队列
        public int getQueue(){
            if(isNull()){
                throw new RuntimeException("队列为空,不能取数据");
            }
            int value = arr[front];
            front = (front+1)%QueueSize;
            return value;
        }
    
        // 显示队列
        public void showQueue(){
            if(isNull()){
                throw new RuntimeException("队列为空");
            }
            for (int i = front; i <front+getSize() ; i++) {
                System.out.printf("arr[%d] = %d ",i%QueueSize,arr[i%QueueSize]);
            }
        }
    
        // 显示队列的头数据(不是取数据)
        public void showHead(){
            if(isNull()){
                throw new RuntimeException("队列为空");
            }
            System.out.println("头数据为"+arr[front]);
        }
    
        public int getSize(){
            return (rear-front+QueueSize)%QueueSize;
        }
    }

## 总结 ##

大家有条件还是敲一敲比较好,能看明白是一回事,敲出来又是另一回事。

其中%是关键,这一点需要自己理解,光打字解释解释不清楚,大家重点理解一下。

[c051e87c3ca54507b3dd458999e0d7a3.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/11/36b62edca861403d87472222f2edbd33.png
[18ea790aef80458ca55f6d1df4688e15.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/11/4cf9027955304d158f42ad59a0495928.png
[ab3a95d35e2545b99840774f5c4cac62.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/11/64a9b1253b074a5190aa3697434f33f2.png
[c0f32c53e7ec4797b319b20d7b9496b4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/11/c2e38803f88c4b11831b7fcc833bdb5a.png
[f6024b1d7f874d948b3b9f24f992f3fc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/11/15bcb876662c4569bf0f8883fa8a47ea.png
[baea3b23283d47b9b6cf619e17757ab7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/11/2ba1ed01d542482d81f7ee99612e4d02.png
[efedf378faf54eec9413c75474da71ff.png]: https://img-blog.csdnimg.cn/efedf378faf54eec9413c75474da71ff.png
[f736dd3767304f8e8d0b74bec4bf1961.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/11/0a00bc7bed674b1395c4adb17adc37ec.png