大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
一、什么是队列
队列是一种特殊的线性表。
队列元素的进出遵循“先进先出”原则:即只允许在前端(front)也就是队头进行删除操作,而只能在后端(rear)也就是队尾进行插入操作。
如图所示:
- 队列的最大长度为MaxSize,最大下标为MaxSize-1
- 入队时队头下标不变而队尾下标改变,出队时则相反
二、模拟队列
1.简单的使用数组模拟队列:
/**
* @Author:huang
* @Date:2020-06-11 16:28
* @Description:用数组模拟队列
*/
public class Queue {
//队列最大长度
private int maxSize;
//存放数据的数组
private Object[] arr;
//头指针,指向队头的元素的前一个位置
private int front;
//尾指针,指向队尾的元素所在位置
private int rear;
//构造器
public Queue(int size) {
this.maxSize = size;
this.arr = new Object[maxSize];
this.front = -1;
this.rear = -1;
}
/**
* 判断队列是否为空
*
* @return
*/
public boolean isEmpty() {
//当头指针和尾指针相等时队列为空
return rear == front;
}
/**
* 判断队列是否已满
* @return
*/
public boolean isFull(){
//当尾指针等于maxSize-1时队列满
return rear == maxSize - 1;
}
/**
* 入队
* @param item 入队元素
* @return
*/
public int addQueue(Object item) {
//判断队列是否已满
if (isFull()) {
throw new RuntimeException("队列已满!");
}
//尾指针后移
rear++;
arr[rear] = item;
return rear;
}
/**
* 出队
* @return
*/
public Object quitQueue() {
//判断队列是否为空
if (isEmpty()) {
throw new RuntimeException("队列为空!");
}
//头指针后移
front++;
return arr[front];
}
}
2.解决“内存溢出”
咋一眼看上去没问题,但是实际上随着入队和出队操作,头指针和尾指针会不断后移,最后都到达maxSize-1的位置,此时即使实际上有空闲空间也无法往里面添加数据了。
如果要解决这个问题,可以这样改进:
当入队的时候进行一次判断,如果尾指针已经移动到maxSize-1的位置,并且头指针不在-1位置,也就是队列仍然还有空位,就触发一次数据迁移。
打个比方,如果队列长度为6,现在头指针在3,尾指针在5,触发数据迁移后下标3-5的数据移动到0-2去,然后把头指针移到0,尾指针移到2。
基于这个逻辑,只需要改变一下addQueue()
入队方法即可:
/**
* 入队
* @param item 入队元素
* @return
*/
public int addQueue(Object item) {
//判断队列是已满还是只是尾指针到头
if (isFull()) {
//队列已满
if (front == -1){
throw new RuntimeException("队列已满!");
}else {
//尾指针到头,触发数据迁移
for (int i = front; i < rear; i++) {
arr[i - front] = arr[i];
}
//移动指针
rear = rear - front;
front = -1;
}
}
//尾指针后移
rear++;
arr[rear] = item;
return rear;
}
虽然问题解决了,但是频繁的移动数据会消耗性能,为此仍需要加以改进:
当尾指针到头以后,如果头指针前还有空闲空间,尾指针应当能移动到头指针之前的位置,也就是队头元素出队了,空出的空间将可以放在队尾被元素入队。
打个比方,就相当于原本的队列是一条直线,走到头就没了,现在要把头和尾连接到一起,让它变成循环队列。
三、循环队列
对于循环队列,有两个问题需要考虑,一个是下标,另一个是队空和队满的判断条件
1.环形队列的下标计算
由于队头元素出队后空间即用于队尾元素入队,所以很可能出现长度5的队列,头指针在1,尾指针在4,这个时候在按照原来的思路用rear+1去入队就会下标越界,因此需要进行取余操作,也就是(rear+1)% maxSize
,这样获取下标的问题就解决了。
2.环形队列的状态判断
由于队列变为环形,所以front=rear即可能是队满也可能是队空,针对这个问题有两种思路:
第一种是添加一个变量来记录队列中元素的数量,以区分front=rear时是队满还队空;
第二种是在rear后预留一个空位,通过计算判断rear+1后是否等于front以判断队满还是队空;
这里先用第二种来实现一下:
-
队空的时候就是
front=rear
-
队满的时候就是
rear+1=front
,考虑到多次操作后指针可能跑了不止一圈,rear和front可能会大于maxSize,故也需要进行取余操作,所以正确的公式是(rear+1)%maxSize = front%maxSize
3.代码实现
/**
* @Author:huang
* @Date:2020-06-14 16:13
* @Description:环形队列
*/
public class CricleQueue {
//队列最大长度
private int maxSize;
//存放数据的数组
private Object[] arr;
//头指针,指向队头的元素的位置
private int front;
//尾指针,指向队尾的元素的位置
private int rear;
public CricleQueue(int maxSize) {
//由于需要在尾指针后空一位作为队满队空的区分,所以实际大小是maxSize+1
this.maxSize = maxSize + 1;
this.arr = new Object[maxSize + 1];
this.front = 0;
this.rear = 0;
}
/**
* 判断队列是否为空
*
* @return
*/
public boolean isEmpty() {
//当头指针和尾指针相等时队列为空
return rear == front;
}
/**
* 判断队列是否已满
* @return
*/
public boolean isFull(){
//头尾指针+1并取余时相等时队列满
return (rear + 1) % maxSize == front;
}
/**
* 入队
* @param item
*/
public void addQueue(Object item) {
if (isFull()){
throw new RuntimeException("队列已满!");
}
arr[rear] = item;
rear = (rear + 1) % maxSize;
}
/**
* 出队
* @return
*/
public Object quitQueue() {
if (isEmpty()){
throw new RuntimeException("队列为空!");
}
Object item = arr[front];
front = (front + 1) % maxSize;
return item;
}
}
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/170819.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...