外贸公司网站搭建,建医疗网站步骤,wordpress插件卸载,株洲网络学院队列的介绍队列以一种先入先出(FIFO)的线性表#xff0c;还有一种先入后出的线性表(FILO)叫做栈。教科书上有明确的定义与描述。类似于现实中排队时的队列(队尾进#xff0c;队头出)#xff0c;队列只在线性表两端进行操作#xff0c;插入元素的一端称为表尾#xff0c;删…队列的介绍队列以一种先入先出(FIFO)的线性表还有一种先入后出的线性表(FILO)叫做栈。教科书上有明确的定义与描述。类似于现实中排队时的队列(队尾进队头出)队列只在线性表两端进行操作插入元素的一端称为表尾删除(取出)元素的一端称为表头。分别对应于 入队和出队操作。存储结构· 线性存储结构称为顺序队列使用数组实现· 链式存储结构称为链队使用链表实现。图解入队操作图解出队操作队列的使用场景数组模拟顺序队列代码实现/** * All rights Reserved, Designed By https://www.tulingxueyuan.com/ * Title: ArrayQueue.java * Package com.tuling.queue2 * Description: * author: 小白 * Date 2019年11月11日 下午5:54:51 * version V1.0 * Copyright: */ package com.tuling.queue2;/** * ClassName ArrayQueue * Description * Author 北京图灵学院 * Date 2019年11月11日 下午5:54:51 */public class ArrayQueue {//定义一个数组用来模拟队列存储数据private Integer[] arr;//定义一个变量用来指向队列头private int front;//定义一个变量用来指向队列尾private int rear;/** * * Title: ArrayQueue * Description: 构造方法 * param queueSize队列初始化容量。 * throws */public ArrayQueue(int queueSize) {if(queueSize 0) {throw new IllegalArgumentException(初始化容量不能小于0);}arr new Integer[queueSize];front 0;rear 0;}/** * * Title: addQueue * Description: 入队操作 * 1、首先判断队列容量情况 * 2、如果队列未满队列头不变向队列尾下标位置插入数据同时队列尾1 * param: param num * return: void * throws */public void addQueue(int num) {if(isFull()) {throw new IllegalArgumentException(队列已满);}arr[rear] num;rear;}/** * * Title: isFull * Description: 判断队列是否已满 * return: boolean * throws */public boolean isFull() {return rear arr.length;}/** * * Title: getQueue * Description: 出队操作 * 1、先判读当前队列是否为空 * 2、每次从队列头开始出队出队一个元素队列头1 * param: * return: int * throws */public int getQueue() {if(isEmpty()) {throw new IllegalArgumentException(队列为空);}return arr[front];}/** * * Title: isEmpty * Description: 判断当前队列是否为空 * return: boolean * throws */public boolean isEmpty() {return front rear;}/** * * Title: showQueue * Description:显示队列的所有数据 * param: * return: void * throws */public void showQueue() {if(isEmpty()) {throw new IllegalArgumentException(队列为空);}for (int i front; i rear; i) {System.out.println(i -- arr[i]);}}}/** * All rights Reserved, Designed By https://www.tulingxueyuan.com/ * Title: ArrayQueueDemo.java * Package com.tuling.queue2 * Description: * author: 小白 * Date 2019年11月11日 下午6:22:00 * version V1.0 * Copyright: */ package com.tuling.queue2;/** * ClassName ArrayQueueDemo * Description * Author 北京图灵学院 * Date 2019年11月11日 下午6:22:00 */public class ArrayQueueDemo {/** * Title: main * Description: * param: param args * return: void * throws */public static void main(String[] args) {ArrayQueue aq new ArrayQueue(5);aq.addQueue(5);aq.addQueue(8);aq.addQueue(7);aq.showQueue();System.out.println(------------------------------------);aq.addQueue(2);aq.addQueue(9);//aq.addQueue(9);aq.showQueue();System.out.println(------------------------------------);System.out.println(出队);aq.getQueue();aq.showQueue();System.out.println(------------------------------------);System.out.println(出队);aq.getQueue();aq.showQueue();System.out.println(------------------------------------);System.out.println(出队);aq.getQueue();aq.showQueue();System.out.println(------------------------------------);System.out.println(出队);aq.getQueue();aq.showQueue();System.out.println(------------------------------------);System.out.println(出队);aq.getQueue();aq.showQueue();}}顺序队列的溢出现象· 下溢现象当队列为空时做出队运算产生的溢出现象。下溢是正常现象常用作程序控制转移的条件。· 真上溢现象当队列满时做进栈运算产生空间溢出的现象。真上溢是一种出错状态应设法避免。· 假上溢现象由于入队和出队操作中头尾指针只增加不减小致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远 远小于向量空间的规模时也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为假上溢现象。数组模拟环形队列为了解决顺序队列中假上溢的现象同时更好的利用内存空间我们将其实现为环形队列。理解环形队列首先我们要说明的是循环队列仍然是基于数组实现的。但是为了形象化的说明问题我们如下图所示1 图中有两个指针(其实就是两个整数型变量因为在这里有指示作用所以这里理解为指针)front、rear,一个指示队头一个指示队尾。2 rear和front互相追赶着这个追赶过程就是队列添加和删除的过程如果rear追到head说明队列满了如果front追到rear说明队列为空。3 我们把它掰弯用的是求余这样两个值就不会跑出最大范围并且可以实现弯曲的效果所以说对于循环队列我们必须给定最大值。这其实是我们臆想的我们要做的就是利用循环来解决空间浪费的问题。环形队列的实现过程· 当添加一个元素时,(rear1)%MAXQSIZE; //理解为什么求余· 当删除一个元素时,(front1)%MAXQSIZE//理解为什么求余· 当rearfront的时候队列可能是满也可能是空。· 因为存在满和空两种情况我们需要分别判断· 满当队列添加元素到rear的下一个元素是head的时候也就是转圈子要碰头了我们就认为队列满了。(rear1)%MAXSIZEQ.front· 空当队列删除元素到headrear的时候我们认为队列空了。rearfront,不一定为0环形队列代码实现CircularQueue.java 类代码如下/** * All rights Reserved, Designed By https://www.tulingxueyuan.com/ * Title: CircularQueue.java * Package com.tuling.circular * Description: * author: 北京图灵学院 * date: 2019年11月13日 下午5:13:16 * version V1.0 * Copyright: */package com.tuling.circular;/** * ClassName CircularQueue * Description * Author 北京图灵学院 */public class CircularQueue {//该数组模拟环形队列存储数据private Integer[] arr;//该变量指向队头private int front;//该变量指向队尾private int rear;//该变量表示当前队列的最大容量private int maxSize;//该变量表示当前队列有效数据的个数private int elementCount;/** * * param queueSize:队列的初始容量 */public CircularQueue(int queueSize) {if(queueSize 0) {throw new IllegalArgumentException(初始化容量不能小于0);}arr new Integer[queueSize];maxSize queueSize;front 0;rear 0;elementCount0;}/** * * Title: addQueue * Description:入队操作 * 思路 * 1、判断队列是否已满 * 2、向队尾插入数据 * 3、将有效数据的个数 1 * param: num * return: void * throws */public void addQueue(int num) {if(isFull()) {throw new IllegalArgumentException(队列已满);}//队列未满可以继续入队操作//想队尾插入数据arr[rear] num;//移动尾指针rear (rear 1) % maxSize;elementCount1;}/** * * Title: isFull * Description:判断当前队列是否已满 * 判满条件 * 1、空出一个元素位置区别队列判空的条件 * 2、保证队尾指针的范围在数组下标范围内解决方案对Maxsize取余 * (rear 1) % maxSize front * param: * return: boolean * throws */public boolean isFull() {return (rear 1) % maxSize front;}/** * * Title: showQueue * Description:显示队列当中的所有数据 * param: * return: void * throws */public void showQueue() {if(isEmpty()) {throw new IllegalArgumentException(队列为空);}for(int i front; i (frontelementCount);i) {System.out.println((i%maxSize) -- arr[i%maxSize]);}}/** * * Title: isEmpty * Description:判断当前队列是否为空 * param: * return: boolean * throws */public boolean isEmpty() {return front rear;}/** * * Title: getQueue * Description: 出队操作 * 思路出队需要操作队头后移还需要注意队头的值范围。 * 1、先用一个临时变量存储当前队头 * 2、将队头后移 * front (front 1) % maxSize * 3、将有效数据个数 -1 * 4、return * param: * return: int * throws */public int getQueue() {if(isEmpty()) {throw new IllegalArgumentException(队列为空);}int tempHead arr[front];front (front 1) % maxSize;elementCount-1;return tempHead;}/** * * Title: showHead * Description:显示当前队列头不进行出队操作 * param: * return: void * throws */public void showHead() {if(isEmpty()) {throw new IllegalArgumentException(队列为空);}System.out.println(当前队列的队列头为 front -- arr[front]);}}测试代码/** * All rights Reserved, Designed By https://www.tulingxueyuan.com/ * Title: CircularQueueDemo.java * Package com.tuling.circular * Description: * author: 北京图灵学院 * date: 2019年11月13日 下午5:30:43 * version V1.0 * Copyright: */package com.tuling.circular;/** * ClassName CircularQueueDemo * Description * Author 北京图灵学院 */public class CircularQueueDemo {/** * Title: main * Description: * param: param args * return: void * throws */public static void main(String[] args) {CircularQueue cq new CircularQueue(5);System.out.println(--------------------------1.入队操作-----------------------------);cq.addQueue(5);cq.addQueue(8);cq.addQueue(7);cq.addQueue(2);//cq.addQueue(9);cq.showQueue();System.out.println(--------------------------2.入队操作-----------------------------);System.out.println(出队 cq.getQueue());cq.showHead();System.out.println(出队 cq.getQueue());cq.showHead();System.out.println(出队 cq.getQueue());cq.showHead();System.out.println(出队 cq.getQueue());System.out.println(--------------------------3.入队操作-----------------------------);cq.addQueue(5);cq.addQueue(8);cq.addQueue(7);cq.addQueue(2);cq.showQueue();}}
