数组模拟实现环形队列

目录

前言

一、什么是队列?

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

三 . 数组模拟环形队列

总结

前言 

笔者: 最爱吃兽奶

博文内容: 数据结构队列的模拟实现

这篇博客理解起来或许没有那么简单,我尽力讲的容易理解一点,接下来跟我一起去看看吧!

一、什么是队列?

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

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

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

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

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

图解:

分析: 队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如上图, 其中 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 后移
}

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

三 . 数组模拟环形队列

思路如下:

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

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

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

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 
            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;
    }
}

总结

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

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