目录
一、队列
1、基本介绍
2、示意图
3、队列的特点
二、数组模拟队列
1、数组队列初始化
2、判断方法
3、增删改查的方法
4、注意
三、数组模拟环形队列
1、初始化
2、判断方法
3、增删改查的方法
一、队列
1、基本介绍
队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。
2、示意图
3、队列的特点
先进先出:
在队列中插入一个队列元素称为入队,从队列中删除一个队列元素称为出队。因为队列只允许在一端插入,在另一端删除,所以只有最早进入队列的元素才能最先从队列中删除,故队列又被称为先进先出。
二、数组模拟队列
1、数组队列初始化
根据图示进行初始化:
class ArrayQueue{private int maxSize; //表示数组最大容量private int front; //队列头private int rear; //队列尾private int[] arr; //该数组用于存放数据,模拟队列//创建队列构造器,进行初始化public ArrayQueue(int arrMaxSize){maxSize = arrMaxSize;arr = new int[maxSize];front = -1; //front指向队列头的前一个位置rear = -1; //指向队列尾}}
2、判断方法
▶ 判断队列是否为空
front 是指向队列的头的前一个位置,rear是指向队列的尾,当front和rear重合时,队列为空。
public boolean isEmpty(){return rear == front;}
▶ 判断队列是否满
因为数组有最大容量,所以直接判断rear(队列尾)是否在数组的最后位置。数组的下标从零开始。
public boolean isFull(){return rear == maxSize - 1;}
3、增删改查的方法
▶ 向队列中添加数据,入队列
▷ 添加数据首先判断数组是否满,如果满,则无法添加数据,数组未满则只需要动 rear(进行尾部移动),rear先加一,然后在数组中存放数据。
//添加数据到队列public void addQueue(int n){//判断队列是否满if(isFull()){System.out.println("队列满,不能再添加");return;}rear++; //让rear后移arr[rear] = n;}
▶ 删除队列中数据,出队列
▷ 因为队列的特点先进先出,所以我们需要动队列的头,当然首先应该判断队列是否为空,为空则不能出队列;然后(front是指向队列头的前一个位置)先将front 加一到达队列的头的位置,再把这个值返回即可。有人可能会问队列的头呢?当front == -1时,数组下标为0 的数据为头,一旦front进行加一后,数组下标为1的数据就为头了,也就是当front进行变化后队列的头就变了。
//获取队列数据,出队列public int getQueue(){//判断队列是否为空if(isEmpty()){//通过抛出异常throw new RuntimeException("队列为空,不能获取数据");}front++; //front后移return arr[front];}
▶ 显示队列中所有数据
▷ 因为是数组模拟的队列,将数组进行遍历输出即可。
//显示队列的所有数据public void showQueue(){//判断是否为空if(isEmpty()){System.out.println("队列为空,没有数据");return;}//遍历for(int i = 0; i < arr.length ; i++){System.out.printf("arr[%d] = %d\n", i , arr[i] );}}
4、注意
这样的数组队列是不可逆的,当front在数组的末尾时,这个数组队列就不可用了,因为front 和 rear 不能循环到数组的前面去,所以这样的数组队列是非常局限的。而链表队列,就是队列是由单链表形成的,就没有数组大小的限制,可以无限的入队列和出队列,单链表的操作非常的简单,后续的文章会介绍。那么数组队列是否也可以无限入队列和出队列呢?当然可以,那么怎么可以实现呢?数组队列的局限在哪里?不就是front 和 rear 的指向不能回过头来指向数组的空位置。
只要解决了front 和 rear 能够返回到数组的空位置,是不是就能解决这个局限性的问题呢,因为出队列和入队列都是通过 front 和 rear 操作的。
三、数组模拟环形队列
1、初始化
数组的最大容量实际要少一个,因为我们要预留一个空位置,也就是任何时候数组要多一个空位置,便于我们循环。
class CircleTest{private int maxSize;//最大容量private int start;//表示队列的头private int end;//表示队列的尾的下一个,要预留一个空位private int[] arr;//数组用来存放数据public CircleTest(int maxSize){this.maxSize = maxSize;arr = new int[maxSize];//start和end默认初始化为0,所以不需要写}}
2、判断方法
▶ 判断队列是否为空
start是指向队列的头,end是指向队列的尾的下一个,当start和end重合时,队列为空。
public boolean isEmpty(){return start == end;}
▶ 判断队列是否满
因为此时的数组队列可以循环,所以判断是否满的方法要用算法,让队列尾位置下标加一对总容量取余即可,然后判断是否等于start,比如:end = 2 ,start = 3
计算 (end + 1)% maxSize = (2 + 1)% 4 = 3 ,计算结果等于start ,所以是满状态,因为前面说了要预留一个位置,所以容量为4,实际存放数据为3个。
public boolean isFull(){return (end + 1) % maxSize == start;;}
▶ 计算数组中的有效数据
计算有效数据我们要用到一种取余的算法,算法式: (end + maxSize - start) % maxSize ,用队列头加上总容量减去队列尾再对总容量取余。比如:end = 0 ,start = 3
时,有效数据为 (1 + 4 - 3)% 4 = 2,所以有效数据为2个。
public int size(){return (end + maxSize - start) % maxSize;}
3、增删改查的方法
▶ 向队列中添加数据,入队列
首先判断队列是否满,然后因为我们早已预留了一个位置(end指向的位置是空的),所以加入的数据位置可以直接加入到队列(arr[end] = n);环形队列是要无限循环下去的,所以在加入数据后,end 的指向不能直接加一,而要用算法计算end的下一个位置,此算法为:(end + 1) % maxSize
比如:start = 2,end = 3 ,此时添加一个数据 end 的位置移动到在哪里?
根据算法(end + 1) % maxSize = (3 + 1) % 4 = 0 ,所以 end 指向数组下标为0 的位置。如此,就形成了循环。
public void addData(int n){//先判断是否满if (isFull()){System.out.println("数据已满,无法添加");return;}//当前end的位置,加入元素arr[end] = n;//end指向下一个位置为(end + 1) % maxSizeend = (end + 1) % maxSize;}
▶ 删除队列中数据,出队列
首先判断是否为空,然后将要出队列的数据用一个中间变量暂存起来,然后将start 移动,移动到的位置和上面end 的移动方式相同,也是用取余算法:(start + 1) % maxSize 即可。
public int removeData(){//判断是否为空if(isEmpty()){throw new RuntimeException("数据为空,不能移除");}//先将数据暂存int temp = arr[start];//然后将start往后移到(start + 1) % maxSize的位置start = (start + 1) % maxSize;return temp;}
▶ 显示队列中所有数据
因为是循环队列,所以位置是无限变化的,所以每次for循环的开始位置为start 所在的位置,要循环的次数取决于数组中的有效数据的个数,及前面我们写的有效个数的算法拿来直接用( start + size() ),取余的方式 :i % maxSize ,可以时时确定数组数据的下标。
public void showData(){//判断是否为空if(isEmpty()){System.out.println("数据为空,不能显示");return;}for (int i = start; i < start + size() ; i++) {System.out.printf("arr[%d] = %d\n", i % maxSize,arr[i % maxSize]);}}
注意:
循环的关键点在于 start 和 end 指向的下一个位置的确定,队列头和尾的位置可以回过头来,那么就能实现循环,而位置的确定,需要用到取余这个算法,前面的列子可以看出,指向发生变化时都是用的取余算法来确定位置,这个是数组中常见的一种算法,可以记住。