Java中队列的表述 (超详细)

wuchangjian2021-11-05 18:58:14编程学习

一 . 什么是队列

           队列,和一样,也是一种对数据的"存"和"取"有严格要求的线性存储结构。

           队列的两端都"开口",要求数据只能从一端进,从另一端出,如所示:

队列存储结构

          队列中数据的进出要遵循 "先进先出" 的原则

二 . 队列的实现方式

        1.实现有两种方式 

             1.1. 顺序队列  :存储结构为数组的形式 

             1.2. 链队列  :存储结构为链表的形式

       2 . 实现思路

             2.1 队列的输入输出 是分别从前后端来控制的 ,所以需要两个变量来标记前后端 ,

                 还需要存储数据的格式 以及容量

                      前端队列头 front            队列尾  rear   (都指向 第一个元素之前)

                     最大容量 MaxSize

                

这里出队里后会造成前面的空间浪费  怎么改进呢 ? 改变变量的含义 下面有详细        

 3 . 代码实现顺序队列

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; //表示头部变量指向 队列头的第一个位置之前;
	    rear=-1;
	 }
	//判断队列是否为满
	public boolean isFull() {
		return rear==maxSize-1;
	}
	
	//判断队列是否是空的
	public boolean isEmpty() {
		return rear==front;
	}
	
	//给队列添加数据  入队列
	public void addQueue(int nums) {
		//判断是否满了
		if(isFull()) {
			System.out.println("队列元素满了,不能添加数据---");
		 return;
		}
		rear++;
		arr[rear]=nums;
	  }
	
	//取出数据 ,出队列
	 public int getQueue() {
		 //判断是否为空
		 if(isEmpty()) {
			 throw new RuntimeErrorException(null, "队列为空,不能取数据");
		 }
		 front++;
		 //取出数据后,重新的复制原来的位置 才是删除去除,但空间不能利用了
		 int s=  arr[front];
		 arr[front]=0;
		 return s;
	 }
	
	//打印队列的所有数据
	 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 :指向队列的第一个元素  (默认初始为0)(原来是第一个元素后一个位置)

   Rear : 指向队列的最后一个元素后一个位置默认初始为0)(原来是包含后一个位置)

存储形式

 

  主要改进 就是对空间能够利用 

   空出一个空间作为约定位置

     空队列为  Front==rear;

     此时队列满时条件  (rear+1)%maxSize==Front;

     队列中有效的数字 (rear+maxSize-Front)%maxsize

 代码实现

class CircleQueue{
	//这个类表示模拟的队列
	private int maxSize; // 最大容量
	private int front; //开始队列头
	private int rear;  //队列尾
	private int [] arr;  //数组存放数据
	
	//构造方法表示能够创建出一个队列  ,传入一个容量
	public CircleQueue(int arrMaxSize) {
		maxSize=arrMaxSize;
	    arr=new int[maxSize];
	    front=0; //表示头部变量指向 队列头的第一个位置
	    rear=0;
	 }
	//判断队列是否为满
	public boolean isFull() {
		return  (rear+1) % maxSize==front;
	}
	
	//判断队列是否是空的
	public boolean isEmpty() {
		return  rear==front;
	}
	
	//给队列添加数据  入队列
	public void addQueue(int nums) {
		//判断是否满了
		if(isFull()) {
			System.out.println("队列元素满了,不能添加数据---");
		 return;
		}
		
	 //rear++  这里的rear意义改变了,不需要后移位置再赋值
		arr[rear]=nums;
		rear = (rear+1)%maxSize;
	  }
	
	//取出数据 ,出队列
	 public int getQueue() {
		 //判断是否为空
		 if(isEmpty()) {
			 throw new RuntimeErrorException(null, "队列为空,不能取数据");
		 }
		 //front++  ,front此时存的就是第一个元素
		 //取出数据后,重新的赋值原来的位置 才是删除去除
		 int s=  arr[front];
		 arr[front]=0;
		 front=(front+1)%maxSize;
		 return s;
	 }
	
	//打印队列的所有数据
	 public void showQueue() {
		 if(isEmpty()) {
			System.out.println("数列为空,不能查看"); 
			return;
		 }
		 for (int i = front; i < front+Size(); i++) {
			System.out.printf("arr[%d]=%d\n",i%maxSize,arr[i%maxSize]);
		}
	 }
	 
	 //求当前的队列有效数字
	 public int Size() {
		 
		 return (rear+maxSize-front)%maxSize;
	 }
	 
	 
}

测试代码  (这里的思想一定要学会)

public class ArryQueueTest {
	
	public static void main(String[] args) {
		//创建构造的队列
	ArrayQueue queue = new ArrayQueue(3);
	
	//创建出一个菜单,直接能提示给用户;
	char key=' ';  //接受用户输入数据
	Scanner scanner= new Scanner(System.in);
	boolean loop=true;
	
	while(loop) {
		
		System.out.println("s(show) :显示队列数据");
		System.out.println("e(exit) :退出程序");
		System.out.println("a(add)  :添加数据");
		System.out.println("g(get)  :获得队列数据");
		System.out.println("i(isFull):显示队列是否满了");
	
		key=scanner.next().charAt(0); //获得接受字符串;
	
		switch(key) {
		case 's' : queue.showQueue(); break;
		case 'e' : 
			        scanner.close();
			         loop=false; break;
		case 'a' : 
			    System.out.println("输入一个数据");
			    int nums = scanner.nextInt();
		     	queue.addQueue(nums);
			    break;
		case 'g' :
			try {
			   int res = queue.getQueue(); 
			   System.out.printf("取得的数据为%d\n",res);
			  }catch (Exception e) {
				System.out.println(e.getMessage());
			}
			break;
		case 'i' : queue.isFull(); break;
		
		 }
	 }
	
	System.out.println("退出程序");
	}

}

  

相关文章

【基础入门题025】二次方程的实数根

【基础入门题025】二次方程的实数根

【基础入门题】2021.11.21 求一元二次方程ax²+bx+c...

零基础玩转C语言系列第四章——编程重点内容之函数

目录 一、什么是函数 二、C语言中函数的分类 1.库函数 2.自定义函数 三、...

分布式锁概述

  分布式锁简介: 在同一个JVM内部,大家往往采用syn...

发表评论    

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。