普通队列实现
import java.util.Scanner;
/**
* @author Rainful
* @create 2021/05/28
*/
class Main2{
public static void main(String[] args){
// 创建输入实例
Scanner sc = new Scanner(System.in);
System.out.println("请输入队列的大小");
int arrMaxLength;
try {
arrMaxLength = sc.nextInt();
} catch (Exception e) {
System.out.println("输入有误, 默认长度为3");
arrMaxLength = 3;
}
ArrQueueDemo2 queue = new ArrQueueDemo2(arrMaxLength);
boolean flag = true;
while (flag){
System.out.println("a 增加一个数据");
System.out.println("g 弹出一个数据");
System.out.println("h 打印头部数据");
System.out.println("p 打印全部数据");
System.out.println("e 退出程序");
char c = sc.next().charAt(0);
switch (c) {
case 'a' -> {
if (queue.isFull()){
System.out.println("队列已满");
continue;
}
System.out.println("请输入数据");
queue.addQueue(sc.nextInt());
}
case 'g' -> {
try{
queue.getQueue();
} catch (Exception e){
System.out.println(e.getMessage());
}
}
case 'h' -> {
try{
queue.printHeadQueue();
} catch (Exception e){
System.out.println(e.getMessage());
}
}
case 'p' -> {
try{
queue.printQueue();
} catch (Exception e){
System.out.println(e.getMessage());
}
}
case 'e' -> {
System.out.println("程序关闭");
sc.close();
flag = false;
}
}
}
}
}
class ArrQueueDemo2{
private int arrMaxlength;
private int tailCount = -1;
private int[] queue;
// 接收输入 创建队列
public ArrQueueDemo2(int arrMaxLength) {
this.arrMaxlength = arrMaxLength;
queue = new int[this.arrMaxlength];
}
// 判断队列是否为空
public boolean isEmpty(){
return this.tailCount == -1;
}
// 判断队列是否已满
public boolean isFull(){
return this.tailCount == this.arrMaxlength - 1;
}
// add 增加一个数据
public void addQueue(int num){
this.tailCount++;
queue[this.tailCount] = num;
}
// get 弹出头部数据
public void getQueue(){
if (isEmpty()){
throw new RuntimeException("队列为空");
}
System.out.println(queue[0]);
this.tailCount--;
for(int i = 0; i < this.arrMaxlength - 1; i++){
queue[i] = queue[i + 1];
}
queue[queue.length -1] = 0;
}
// head 打印头部数据
public void printHeadQueue(){
if (isEmpty()){
throw new RuntimeException("队列为空");
}
System.out.println("头部数据为: " + queue[0]);
}
// print 打印队列全部数据
public void printQueue(){
if (isEmpty()){
throw new RuntimeException("队列为空");
}
for (int n : queue){
System.out.printf("%d ", n);
}
System.out.println();
}
}
环形队列实现
- 主要特点:
- 环形队列特点，双指针分别指向头部和尾部
- 当头部和尾部指针增加时，需要对增加后的变量取模，因为指针可能是从最后一位跳到第一位指向
- 数组的有效长度是 (尾部数据+全长+头部数据) % 全长
- 队列是否已满的判断是 (尾部数据+1) % 全长 == 头部数据
import java.util.Scanner;
class CircleArrDemo{
public static void main(String[] args){
CircleArr arr = new CircleArr(6);
Scanner sc = new Scanner(System.in);
boolean flag = true;
while (flag){
System.out.println("请选择一个选项:");
System.out.println("a: 增加一个数");
System.out.println("g: 弹出一个数");
System.out.println("h: 打印头部数据");
System.out.println("p: 打印全部数据");
System.out.println("e: 停止程序");
char c = sc.next().charAt(0);
switch (c){
case 'a':
if (arr.isFull()){
System.out.println("队列已满");
continue;
}
System.out.println("请输入数据");
int num = sc.nextInt();
arr.addNum(num);
break;
case 'g':
try{
arr.getNum();
}catch(Exception e){
System.out.println(e.getMessage());
}
break;
case 'h':
try{
arr.printHeadNum();
}catch(Exception e){
System.out.println(e.getMessage());
}
break;
case 'p':
try{
arr.printNum();
}catch(Exception e){
System.out.println(e.getMessage());
}
break;
case 'e':
System.out.println("程序关闭");
sc.close();
flag = false;
break;
default:
System.out.println("您输入的选项有误");
break;
}
}
}
}
class CircleArr{
// front永远指向数组的第一个元素
private int front = 0;
// tail永远指向数组的最后一个元素的后面一个位置
// (指向当前元素会有bug，就是当没有元素的时候front和tail指向一样。增加第一个元素的时候也是一样的)
private int tail = 0;
int[] circleArr;
int maxArrSize;
// 初始化数组
public CircleArr(int num){
this.maxArrSize = num;
this.circleArr = new int[this.maxArrSize];
}
// 判断是否已满
public boolean isFull(){
return (this.tail + 1) % this.maxArrSize == this.front;
}
// 判断是否为空
public boolean isEmpty(){
return this.front == this.tail;
}
// 统计有效元素个数
public int getEffetiveNum(){
return (this.tail + this.maxArrSize - this.front) % this.maxArrSize;
}
// add增加一个数
public void addNum(int num){
// 增加
this.circleArr[this.tail] = num;
// front和tail的增加都需要考虑到如果是最后一个数增加一个数
// 那么就会回到0位，所以是先++ 后取模
this.tail = ++this.tail % this.maxArrSize;
}
// get弹出一个数
public void getNum() throws RuntimeException{
if (isEmpty()){
throw new RuntimeException("队列为空");
}
// 弹出
System.out.println(this.circleArr[this.front] + "被弹出");
this.front = ++this.front % this.maxArrSize;
}
// 打印头部数据
public void printHeadNum() throws RuntimeException{
if (isEmpty()){
throw new RuntimeException("队列为空");
}
System.out.println(this.circleArr[this.front] + "是头部数据");
}
// 打印全部数据
public void printNum() throws RuntimeException{
if (isEmpty()){
throw new RuntimeException("队列为空");
}
for (int i = 0; i < getEffetiveNum(); i++){
System.out.println("arr["+i+"] = " + this.circleArr[(this.front + i) % this.maxArrSize] + ";");
}
}
}