队列
程序员文章站
2022-03-08 18:59:40
...
队列是一个有序列表,可以用数组或是链表来实现。遵循先入先出的原则。
数组模拟环形队列
【1】队列本身是有序列表,若使用数组的结构来存储队列数据,队列数组的声明如下,其中 maxSize 是该队列的最大容量;
【2】因为队列的输入输出是分别从头和尾来处理的,因此需要两个变量 front(头)=0 和 tail(尾)=0 ,tail会随着数据的输入而变化,front 会随着数据的输出而变化。
【3】为了充分利用数组,例如上图:当tail == maxSize 时,可以继续向 index = 0 的空下标中存放数据。此时就将数组看做一个环形数组(通过取模的方式来实现)。
分析环形数组实现思路:【1】尾(tail)索引的下一个为头(front)索引表示队列为满(因为判断空和判断满冲突,因此需要空出一个格子来做一个约定,相当于最多只能存放 maxSize - 2 的数据,浪费一个格子)这里判断队列满的公式:(tail+1)%maxSize == front ;用一张图来说明问题:
代码实现如下:
package com.algorithms;
import java.util.Scanner;
/**
* Created by Administrator on 2019/11/2 0002.
*/
public class CircleQueue {
//定义一个数组
private int[] arr;
//数组的最大值
private int maxSize;
//头指针
private int front;
//尾指针
private int tail;
//创建一个带参的构造器,出入队列的大小
public CircleQueue(int maxSize){
this.maxSize = maxSize;
arr = new int[maxSize];
}
//数据测试
public static void main(String[] args) {
CircleQueue circleQueue = new CircleQueue(5);
System.out.println("根据提示输入相关值");
Scanner in = new Scanner(System.in);
while (true){
System.out.println("s:显示");
System.out.println("o:输入");
System.out.println("p:输出");
System.out.println("h:头出");
String next = in.next();
switch (next){
case "s" : circleQueue.list(); break;
case "o" :
System.out.println("请输入一个数");
int i = in.nextInt();
circleQueue.offer(i);
break;
case "p" :
int poll = circleQueue.poll();
System.out.println(poll);
break;
case "h" :
int peek = circleQueue.peek();
System.out.println(peek);
break;
}
}
}
//判断队列是否已满,根据我们的约定来,虽然它还能存放一个元素。
//这里面没几个难点。。。这算一个**********************
public boolean isFull(){
return (tail + 1) % maxSize == front;
}
//插入方法
public void offer(int num){
if(isFull()){
throw new RuntimeException("队列已满");
}
arr[tail]=num;
//不能直接 ++ 否则可以数据越界
//这里面没几个难点。。。这算一个**********************
tail = (tail + 1) % maxSize;
}
//判断队列是否为空
public boolean isEmpty(){
return tail == front;
}
public int poll(){
if(isEmpty()){
throw new RuntimeException("队列为空");
}
int temp = arr[front];
//不能直接 ++ 否则可以数据越界
front = (front + 1) % maxSize;
return temp;
}
//查看队列的大小
public int size(){
//tail+maxSize 是防止队列存满后,tail=2 在 front=3 的前面这种为负数的情况
// %maxSize 是防止计算的结果大于 maxSize
//这里面没几个难点。。。这算一个**********************
return (tail+maxSize-front)%maxSize;
}
//循环查看所有元素信息
public void list(){
for(int i = front;i< front + size();i++){
System.out.printf("arr[%d]==%d\n",i%maxSize,arr[i%maxSize]);
}
}
//查看栈顶元素
public int peek(){
return arr[front];
}
}
----如果喜欢,点个 红心♡ 支持以下,谢谢----