哲学专业特色建设网站,东营住房和城乡建设厅官网,wordpress 4.7.8,广告设计需要学多久文章目录 一#xff1a;队列1.1 队列的概念1.2 队列的介绍1.3 队列示意图 二#xff1a;数组模拟队列2.1 介绍2.2 思路2.3 代码实现2.3.1 定义队列基本信息2.3.2 初始化队列2.3.3 判断队列是否满#xff0c;是否为空2.3.4 添加数据到队列2.3.5 获取队列数据#xff0c;出队… 文章目录 一队列1.1 队列的概念1.2 队列的介绍1.3 队列示意图 二数组模拟队列2.1 介绍2.2 思路2.3 代码实现2.3.1 定义队列基本信息2.3.2 初始化队列2.3.3 判断队列是否满是否为空2.3.4 添加数据到队列2.3.5 获取队列数据出队列2.3.6 显示队列所有数据2.3.7 显示队列头数据2.3.8 源码奉上 2.4 测试ArrayQueue2.5 问题分析并优化 三数组模拟环形队列3.1 分析3.2 思路3.3 代码实现 一队列
1.1 队列的概念
队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出的特点。入队列进行插入操作的一端称为队尾 。出队列进行删除操作的一端称为队头。
例如比如生活中排队买东西先排队的先购买
1.2 队列的介绍
队列是一个有序列表可以用数组或是链表来实现。遵循先入先出的原则。即先存入队列的数据要先取出。后存入的要后取出
1.3 队列示意图 二数组模拟队列
2.1 介绍 队列本身是有序列表若使用数组的结构来存储队列的数据则队列数组的声明如下图, 其中 maxSize 是该队列的最大容量。 因为队列的输出、输入是分别从前后端来处理因此需要两个变量 front及 rear分别记录队列前后端的下标front 会随着数据输出而改变而 rear则是随着数据输入而改变如图所示:
2.2 思路
当我们将数据存入队列时称为”addQueue”addQueue 的处理需要有两个步骤思路分析
将尾指针往后移rear1 , 当front rear 【空】若尾指针 rear 小于队列的最大下标 maxSize-1则将数据存入 rear所指的数组元素中否则无法存入数据。 rear maxSize - 1[队列满]
注 rear 是队列最后[含] front 是队列最前元素[不含]
2.3 代码实现
2.3.1 定义队列基本信息 /*** 最大容量*/private int maxSize;/*** 队列头*/private int front;/*** 队列尾*/private int rear;/*** 该数组用于存放数据*/private int[] arr;2.3.2 初始化队列
/*** 初始化队列构造器** param arrMaxSize*/public ArrayQueue(int arrMaxSize) {maxSize arrMaxSize;arr new int[arrMaxSize];//指向队列头部的前一个位置不包含头部front -1;//指向队列尾部具体数据rear -1;}2.3.3 判断队列是否满是否为空
/*** 判断队列是否满** return*/public boolean isFull() {return rear maxSize - 1;}/*** 判断队列是否为空** return*/public boolean isEmpty() {return front rear;}2.3.4 添加数据到队列
public void addQueue(int n) {//判断队列是否满满了就无法添加数据if (isFull()) {System.out.println(队列满了无法添加数据);return;}//添加数据让rear后移rear;arr[rear] n;}2.3.5 获取队列数据出队列 /*** 获取队列数据出队列** return*/public int getQueue() {//判断队列是否为空if (isEmpty()) {throw new RuntimeException(队列为空无法取出数据);}front;return arr[front];}2.3.6 显示队列所有数据 /*** 显示队列所有数据*/public void showQueue() {//判断队列是否为空if (isEmpty()) {System.out.println(队列为空没有数据);}for (int i 0; i arr.length; i) {System.out.printf(arr[%d]%d\n, i, arr[i]);}}2.3.7 显示队列头数据 /*** 显示队列头数据** return*/public int headQueue() {//判断队列是否为空if (isEmpty()) {throw new RuntimeException(队列为空没有数据);}return arr[front 1];}2.3.8 源码奉上 /*** 队列头部输出数据尾部输入数据*/
class ArrayQueue {/*** 最大容量*/private int maxSize;/*** 队列头*/private int front;/*** 队列尾*/private int rear;/*** 该数组用于存放数据*/private int[] arr;/*** 初始化队列构造器** param arrMaxSize*/public ArrayQueue(int arrMaxSize) {maxSize arrMaxSize;arr new int[arrMaxSize];//指向队列头部的前一个位置不包含头部front -1;//指向队列尾部具体数据rear -1;}/*** 判断队列是否满** return*/public boolean isFull() {return rear maxSize - 1;}/*** 判断队列是否为空** return*/public boolean isEmpty() {return front rear;}/*** 添加数据到队列*/public void addQueue(int n) {//判断队列是否满满了就无法添加数据if (isFull()) {System.out.println(队列满了无法添加数据);return;}//添加数据让rear后移rear;arr[rear] n;}/*** 获取队列数据出队列** return*/public int getQueue() {//判断队列是否为空if (isEmpty()) {throw new RuntimeException(队列为空无法取出数据);}front;return arr[front];}/*** 显示队列所有数据*/public void showQueue() {//判断队列是否为空if (isEmpty()) {System.out.println(队列为空没有数据);}for (int i 0; i arr.length; i) {System.out.printf(arr[%d]%d\n, i, arr[i]);}}/*** 显示队列头数据** return*/public int headQueue() {//判断队列是否为空if (isEmpty()) {throw new RuntimeException(队列为空没有数据);}return arr[front 1];}}2.4 测试ArrayQueue
public class ArrayQueueDemo {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(h(head):查看头队列数据);key scanner.next().charAt(0);switch (key) {case s:queue.showQueue();break;case a:System.out.println(输入一个数字);int value scanner.nextInt();queue.addQueue(value);break;case g:try {int res queue.getQueue();System.out.printf(取出的数据为%d\n,res);} catch (Exception e) {System.out.println(e.getMessage());}break;case h:try {int res queue.headQueue();System.out.printf(队列头数据为%d\n,res);} catch (Exception e) {System.out.println(e.getMessage());}case e:scanner.close();loop false;default:break;}}System.out.println(程序退出);}}2.5 问题分析并优化
问题目前数组使用一次就无法使用没有达到复用的效果 优化将数组改成环形队列进行取模
三数组模拟环形队列
3.1 分析
对前面的数组模拟队列的优化充分利用数组。因此将数组看做是一个环形的。(通过取模的方式来实现即可)
3.2 思路
front的含义做出如下调整front就指向队列的第一个元素即arr[front]就是队列的第一个元素。rear的含义做出如下调整rear指向队列最后一个元素的后一个位置。空出一个空间做约定。队列满的条件rear1%maxSize front;队列空的条件rear front;front和rear的初始值都为0队列中有效数据个数rear maxSize - front% maxSize;
3.3 代码实现
package com.sysg.dataStructuresAndAlgorithms.queue;import java.util.Scanner;public class CircleArrayQueueDemo {public static void main(String[] args) {//长度为4有效长度为3有一个预留的空间CircleArrayQueue queue new CircleArrayQueue(4);//接收用户输入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(h(head):查看头队列数据);key scanner.next().charAt(0);switch (key) {case s:queue.showQueue();break;case a:System.out.println(输入一个数字);int value scanner.nextInt();queue.addQueue(value);break;case g:try {int res queue.getQueue();System.out.printf(取出的数据为%d\n,res);} catch (Exception e) {System.out.println(e.getMessage());}break;case h:try {int res queue.headQueue();System.out.printf(队列头数据为%d\n,res);} catch (Exception e) {System.out.println(e.getMessage());}case e:scanner.close();loop false;default:break;}}System.out.println(程序退出);}
}class CircleArrayQueue {/*** 最大容量*/private int maxSize;/*** 队列头* 1. front的含义做出如下调整front就指向队列的第一个元素即arr[front]就是队列的第一个元素。*/private int front;/*** 队列尾* 2. rear的含义做出如下调整rear指向队列最后一个元素的后一个位置。空出一个空间做约定。*/private int rear;/*** 该数组用于存放数据*/private int[] arr;/*** 初始化队列构造器** param arrMaxSize*/public CircleArrayQueue(int arrMaxSize) {maxSize arrMaxSize;arr new int[arrMaxSize];front 0;rear 0;}/*** 判断队列是否满** return*/public boolean isFull() {//例front 1,rear 5,maxSize 5,此时队列就满了return (rear 1) % maxSize front;}/*** 判断队列是否为空** return*/public boolean isEmpty() {return front rear;}/*** 添加数据到队列*/public void addQueue(int n) {//判断队列是否满满了就无法添加数据if (isFull()) {System.out.println(队列满了无法添加数据);return;}//直接将数据加入arr[rear] n;//将rear后移这里必须考虑取模rear (rear 1) % maxSize;}/*** 获取队列数据出队列** return*/public int getQueue() {//判断队列是否为空if (isEmpty()) {throw new RuntimeException(队列为空无法取出数据);}//这里需要分析出front是指向队列的第一个元素//1.先把front的值保存到一个临时的变量//2.将front后移,考虑取模//3.将临时变量保存int value arr[front];front (front 1) % maxSize;return value;}/*** 显示队列所有数据*/public void showQueue() {//判断队列是否为空if (isEmpty()) {System.out.println(队列为空没有数据);}//从front开始遍历遍历多少个元素for (int i front; i front getSize(); i) {System.out.printf(arr[%d]%d\n, i % maxSize, arr[i % maxSize]);}}/*** 获取有效数据大小* return*/public int getSize() {return (rear maxSize - front) % maxSize;}/*** 显示队列头数据** return*/public int headQueue() {//判断队列是否为空if (isEmpty()) {throw new RuntimeException(队列为空没有数据);}return arr[front];}}
