前天写了栈的实现,今天到队列了,好像明天要期中考试,还是三科,次奥,考吧考吧,五一三天已经贡献给你们了,考成什么样我也认了,毕竟智商在这里。说好的一天来一发,不要说我水,其实我还真的是水,上个学期数据结构课打酱油,这个学期又自己抱本书从第一页开始恭恭敬敬地学,不敢跳过一个字。估计是脑子里面灌浆了。上学期不认真。前车之鉴,希望筒子们好好的把数据结构学好。希望老夫子还为时不晚。
队列和栈一样也是一种很基本的数据结构,队列的用途很多,下面是两个例子。
第一个例子就是CPU资源的竞争问题。在具有多个终端的计算机系统中,有多个用户需要使用CPU各自运行自己的程序, 它们分别通过各自终端向操作系统提出使用CPU的请求,操作系统按照每个请求在时间上的先后顺序,将其排成一个队列,每次把CPU分配给队头用户使用,当相应的程序运行结束,则令其出队,再把CPU分配给新的队头用户,直到所有用户任务处理完毕。
第二个例子就是主机与外部设备之间速度不匹配的问题。以主机和打印机为例来说明,主机输出数据给打印机打印 ,主机输出数据的速度比打印机打印的速度要快得多,若直接把输出的数据送给打印机打印,由于速度不匹配,显然是不行的。所以解决的方法是设置一个打印数据缓冲区,主机把要打印输出的数据依此写如到这个缓冲区中,写满后就暂停输出,继而去做其它的事情,打印机就从缓冲区中按照先进先出的原则依次取出数据并打印,打印完后再向主机发出请求,主机接到请求后再向缓冲区写入打印数据,这样利用队列既保证了打印数据的正确,又使主机提高了效率。
通过上面的两个例子我们知道队列和栈之间的本质的区别了。栈是遵循先进后出,而队列则是遵循先进先出。由于它的先进先出,导致当队头的元素出来之后,队头的指针会上移,往队尾插入元素的时候队尾的指针也是往上移,这个和我们平时的生活经验可能不一样,以我们平时的生活经验,排队买票,队头的人买完票之后,后面的人会向前补上来,这一补可是所有的人都要往前移动一个位置,这在计算机的队列中就相当于要后面的所有元素都要往前进一个位置,这个开销是很大的,所以,计算机中的队列没有采取这样的方法。但是这样之后另外一个问题又出来了,当 把队头的元素移走之后,队头上移,我们知道,队列插入元素是从后面插入的,这就造成了队头前面的内存空出来了,而且还不能用了,因为我们不能把元素从队头插进去。于是乎,聪明的人们想到了循环队列这种东西。当队尾插不进去,队头前面又还有空位的时候,就把队尾下调到队头前面的位置,但记住他还是队尾,如此下去,就不会担心内存的浪费了。下面用图来解释一下:
通过上面的两个图,应该能知道循环队列是怎么实现的了,就多了一个判断,哥哥画图可画了一个多小时。。。。
下面贴出代码,注释详细:
package 环形数组队列; public class CricleQueue { /* * 对列的长度 */ private int maxSize; /* * 队列数组 */ private long[] queueArray; /* * 头下标(指针) */ private int front; /* * 尾下标(指针) */ private int rear; /* * 队列中元素的个数 */ private int nElement; /* * 构造方法,初始化各种数据 */ public CricleQueue(int maxSize) { this.maxSize = maxSize; queueArray = new long[maxSize]; rear = -1; front = 0; nElement = 0; } /* * 在队列的尾部插入一个元素 */ public void insert(long value) { if(rear==maxSize-1){ rear = -1; } queueArray[++rear] = value; nElement++; } /* * 删除队头的元素 */ public long remove() { long temp = queueArray[front++]; if(front==maxSize) { front = 0; } nElement--; return temp; } /* * 判断队列是否为空 */ public boolean isEmpty() { return nElement==0; } /* * 判断队列是否为满 */ public boolean isFull() { return nElement==maxSize; } /* * 查看队头元素 */ public long peekF() { return queueArray[front]; } /* * 查看元素个数 */ public int qSize() { return nElement; } public static void main(String[] args) { CricleQueue cq = new CricleQueue(5); System.out.println("队列是否为空:"+cq.isEmpty()); //插入元素 cq.insert(1); cq.insert(2); cq.insert(3); System.out.println("队列是否满了:"+cq.isFull()); cq.insert(4); cq.insert(5); System.out.println("队列中元素个数:"+cq.qSize()); System.out.println("队列是否满了:"+cq.isFull()); System.out.println("对头的元素为:"+cq.peekF()); //移除两个元素 cq.remove(); cq.remove(); System.out.println("队列中元素个数:"+cq.qSize()); System.out.println("对头的元素为:"+cq.peekF()); //插入两个元素 cq.insert(6); cq.insert(7); System.out.println("队列中元素个数:"+cq.qSize()); System.out.println("队列是否满了:"+cq.isFull()); //移除四个元素 cq.remove(); cq.remove(); cq.remove(); cq.remove(); System.out.println("队列中元素个数:"+cq.qSize()); System.out.println("对头的元素为:"+cq.peekF()); } }
输出结果:
队列是否为空:true 队列是否满了:false 队列中元素个数:5 队列是否满了:true 对头的元素为:1 队列中元素个数:3 对头的元素为:3 队列中元素个数:5 队列是否满了:true 队列中元素个数:1 对头的元素为:7
就这样,队列的内存就不会被浪费掉了,只要里面有空的位置你就可以插入元素。
相关推荐
该C程序使用循环队列实现了N行杨辉三角的输出,实现简单。 使用VC进行编译即可。
数据结构-基本算法-循环队列(学生时代源码,调试可运行)
c语言实现的循环队列,附代码,标准实验报告
数据结构与算法C++实现 循环顺序队列的初始化,求长度,入队,出队 适合大二初学数据结构与算法 程序有详细备注,可直接运行 顺序表
利用循环队列来实现银行排队系统,对进入队列的客户分为VIP和普通客户,其中VIP优先出队。能实现的功能如下1.新客户排队等待服务 2.客户离开排队服务 3.查询当前客户前面还有几人 4.查询截止目前总共办理多少客户 注...
用循环队列编写求k阶斐波那契序列中前n+1项(f0,,f1,f2,…,fn)的算法,满足fn,而fn +1>max,max为某个约定的常数,所用循环队列的容量为k,且算法结束时,留在队列中的元素为所求k阶斐波那契序列中的最后k项
主要介绍了C++数据结构与算法之双缓存队列实现方法,结合实例形式分析了双缓存队列的原理、实现方法与相关注意事项,需要的朋友可以参考下
主要实现循环队列的初始化,入队,出队,求队的长度等算法
算法-理论基础- 队列- 循环队列(包含源程序).rar
4阶斐波那契序列如下:f0=f1=f2=0, f3=1,…,fi=fi-1+fi-2+fi-3+fi-4,利用容量为k=4的循环队列,构造序列的前n+1项(f0, f1 , f2 ,… fn ),要求满足fn ≤200而fn+1 >200。
以循环链表表示队列,只设置一个尾指针,指向队尾结点,不设置头指针。 要求具有下列接口,并写出主程序测试各个接口: ...写一算法实现从循环队列创建一个栈,使队头为栈顶,队尾为栈底,算法最后要求队列保持不变。
C语言实现多级反馈队列调度算法-计算机操作系统实验。C语言实现多级反馈队列调度算法-计算机操作系统实验。
用c语言实现的循环队列代码
本文件是对操作系统进程多级反馈队列调度算法的设计与实现,算法以txt的形式输入输出,其中包含设计报告
设计一个算法,用一个栈s将-一个队列Q逆置: (1)要求采用顺序栈和循环队列来实现。 (2)要求采用链栈和链队列来实现。
【资源说明】 1、该资源内项目代码都是经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业...基于C++实现SJF短优先算法+HRRN高响应比优先调度算法+多级反馈队列调度算法源码.zip
操作系统中多级反馈队列调度算法 C语言模拟实现
1.任意输入队列长度和队列中的元素值,构造一个顺序循环队列,对其进行清空、插入新元素、返回队头元素以及删除队头元素操作。 2.约瑟夫环的实现:设有n个人围坐在圆桌周围,现从某个位置 i 上的人开始报数,数到 ...
对循环队列的基本操作的c算法实现做了详细的编写,运行通过,里面还附有验证程序,保证算法的正确性。里面有的是动态申请空间的结构,克服了浪费空间的缺点。
基于TIA博途的循环队列(FIFO)先进先出SCL语言程序算法(V15版本)