专业做股权众筹的网站,摄影图片网站,做网站莱芜,做网站费用分摊入什么科目文章目录队列简介数组模拟队列#xff08;无法复用#xff09;数组模拟环形队列#xff08;可复用#xff09;队列简介
队列是一个有序列表#xff0c;可以用数组或是链表来实现。
遵循先入先出的原则。即先存入队列的数据#xff0c;先取出#xff0c;后存入的后取出…
文章目录队列简介数组模拟队列无法复用数组模拟环形队列可复用队列简介
队列是一个有序列表可以用数组或是链表来实现。
遵循先入先出的原则。即先存入队列的数据先取出后存入的后取出。
示意图(使用数组模拟队列示意图) 有两个分别指向头部和尾部的“指针”。 数组模拟队列无法复用
1、实现思路
队列本身是有序列表若使用数组的结构来存储队列的数据则队列数组的声明如下图其中maxSize是该队列的最大容量。
因为队列的输出、输入是分别从前后端来处理因此需要两个变量front及rear分别记录队列前后端的下标front会随着数据输出而改变而rear则是随着数据输入而改变如图所示 当我们将数据存入队列时称为addQueueaddQueue的处理需要有两个步骤 ①将尾指针往后移。 ②若尾指针rear小于队列的最大下标maxSize-1则将数据存入rear 所指的数组元素中否则无法存入数据。
rear1当front rear[空] rearmaxSize-1[队列满]
2、代码实现
①数组实现队列类
class ArrQueue {private int maxSize; //队列数组最大容量private int front; //指向队列头部private int rear; //指向队列尾部private int[] queue;//创造队列的构造器public ArrQueue(int maxSize){this.maxSize maxSize;queue new int[maxSize];front -1; //其实是队列第一个元素的前一个索引rear -1; //最后一个元素的索引}//判断是否满public boolean isFull(){return rear maxSize - 1;}//判断是否空public boolean isEmpty(){return front rear;}//添加元素public void addQueue(int n){if (isFull()){System.out.println(队列已经满了无法添加);return;}else {rear;queue[rear] n;}}//取出元素public int getQueue(){if (isEmpty()){throw new RuntimeException(队列为空无元素可取);}else {front;return queue[front];}}//显示队列public void showQueue(){if (isEmpty()){System.out.println(队列为空没有元素可显示);return;}for (int i : queue){System.out.println(i);}}//显示头数据public void headQueue(){if (isEmpty()){throw new RuntimeException(队列为空没有头数据);}int i front;System.out.println(queue[i]);}}②测试类
import java.util.Scanner;/*** Author: Yeman* Date: 2021-10-11-22:02* Description:*/
public class ArrayQueueTest {public static void main(String[] args) {//创建一个队列ArrQueue arrQueue new ArrQueue(3);//创建一个用户输入Scanner scanner new Scanner(System.in);//创建一个功能菜单char key ;boolean isShow true;while (isShow){System.out.println(s:显示队列);System.out.println(a:添加数据);System.out.println(g:取出数据);System.out.println(h:显示头数据);System.out.println(e:退出程序);key scanner.next().charAt(0);switch (key){case s :arrQueue.showQueue();break;case a :System.out.println(请输入一个数);int value scanner.nextInt();arrQueue.addQueue(value);break;case g :try {System.out.println(arrQueue.getQueue());} catch (Exception e) {e.printStackTrace();}break;case h :try {arrQueue.headQueue();} catch (Exception e) {e.printStackTrace();}break;case e :isShow false;break;}}System.out.println(程序退出...);}
} 数组模拟环形队列可复用
对前面的数组模拟队列的优化充分利用数组。将数组看做是一个环形的即取出之后有位置可以空出来添加。(通过取模的方式来实现即可)
分析说明: ①尾索引的下一个为头索引时表示队列满即将队列容量空出一个作为约定。在作判断队列满的时候需要注意(rear 1) % maxSize front [满] ②rear front [空]
1、思路如下: ①front 变量的含义调整front 指向队列的第一个元素, 也就是说arr[front]就是队列的第一个元素front的初始值为0。 ②rear 变量的含义调整rear 指向队列的最后一个元素的后一个位置因为希望空出一个空间做为约定rear的初始值0。 ③当队列满时条件是(rear 1) % maxSize front [满] ④对队列为空的条件是rear front[空] ⑤当我们这样分析队列中有效的数据的个数(rear maxSize - front) % maxSize ⑥我们就可以在原来的队列上修改得到一个环形队列
2、代码实现
①数组实现环形队列类
class ArrQueue {private int maxSize; //队列数组最大容量private int front; //指向队列头部队列第一个元素的索引private int rear; //指向队列尾部队列最后一个元素的后一个索引private int[] queue;//创造队列的构造器public ArrQueue(int maxSize){this.maxSize maxSize;queue new int[maxSize];}//判断是否满public boolean isFull(){return (rear 1) % maxSize front;}//判断是否空public boolean isEmpty(){return front rear;}//添加元素public void addQueue(int n){if (isFull()){System.out.println(队列已经满了无法添加);return;}else {queue[rear] n;rear (rear 1) % maxSize;}}//取出元素public int getQueue(){if (isEmpty()){throw new RuntimeException(队列为空无元素可取);}else {int data queue[front];front (front 1) % maxSize;return data;}}//显示队列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,queue[i % maxSize]);}}//求当前队列有效数据个数public int size(){return (rear maxSize - front) % maxSize;}//显示头数据public void headQueue(){if (isEmpty()){throw new RuntimeException(队列为空没有头数据);}System.out.println(queue[front]);}}②测试类
import java.util.Scanner;/*** Author: Yeman* Date: 2021-10-11-22:02* Description:*/
public class ArrayQueueTest {public static void main(String[] args) {//创建一个队列ArrQueue arrQueue new ArrQueue(3); //说明该环形队列的最大有效数据为2//创建一个用户输入Scanner scanner new Scanner(System.in);//创建一个功能菜单char key ;boolean isShow true;while (isShow){System.out.println(s:显示队列);System.out.println(a:添加数据);System.out.println(g:取出数据);System.out.println(h:显示头数据);System.out.println(e:退出程序);key scanner.next().charAt(0);switch (key){case s :arrQueue.showQueue();break;case a :System.out.println(请输入一个数);int value scanner.nextInt();arrQueue.addQueue(value);break;case g :try {System.out.println(arrQueue.getQueue());} catch (Exception e) {e.printStackTrace();}break;case h :try {arrQueue.headQueue();} catch (Exception e) {e.printStackTrace();}break;case e :isShow false;break;}}System.out.println(程序退出...);}
}
