Java数组队列
小黎的培培笔录 人气:0一、队列
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) % maxSize end = (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 指向的下一个位置的确定,队列头和尾的位置可以回过头来,那么就能实现循环,而位置的确定,需要用到取余这个算法,前面的列子可以看出,指向发生变化时都是用的取余算法来确定位置,这个是数组中常见的一种算法,可以记住。
加载全部内容