- 浏览: 80236 次
- 性别:
- 来自: 北京
文章分类
最新评论
-
KeatsLee:
这篇文章是自己总结的吗?还是来自某本书,麻烦告知一下。觉得很经 ...
Java IO -
di1984HIT:
写的不错啊。
hive 实现多行转一行处理方法 -
di1984HIT:
大数据量分析。
hive海量数据--统计一年网站各个产品的UV
“队列”这个单词是英国人说的“排”。在英国“排队”的意思就是站到一排当中去。计算机科学中,队列是一种数据结构,有点类似栈,只是在队列中第一个插入的数据项也会最先被移除,而在栈中,最后插入的数据项最先移除。队列的作用就像电影院前的人们站成的排一样:第一个进入附属的人将最先到达队头买票。最后排队的人最后才能买到票。
队列和栈一样也被用作程序员的工具。它也可以用于模拟真实世界的环境,例如模拟人们在银行里排队等待,飞机等待起飞,或者因特网络上数据包等待传送。
在计算机操作系统里,有各种队列在安静地工作着。打印作业在打印队列中等待打印。当在键盘上敲击时,也有一个存储键入内容的队列。同样,如果使用文字处理程序敲击一个键,而计算机又暂时要做其它的事,敲击的内容不会丢失,它会排在队列中等待,直到文字处理程序有时间来读取它。利用队列保证了键入内容在处理时其顺序不会改变。
队列的基本操作
队列的两个基本操作是inserting(插入)一个数据项,即把一个数据项放入队尾,另一个是removing(移除)一个数据项,即移除队头的数据项。这类似于电影爱好者排队买票时先排到队尾,然后到达队头买票后离开队列。
栈中的插入和移除数据项方法的命名是很标准,称为push和pop。队列的方法至今没有标准化的命名。“插入”可以称为put、add或enque,而“删除”可以叫delete、get或deque。插入数据项的队尾,也可以叫作back、tail或end。而移除数据项的队头,也可以叫head。下面将使用insert、remove、front和rear。
插入将值插入队尾,同时队尾箭头增加一,指向新的数据项。
数据项被移除后,同时队头指针增加一。通常实现队列时,删除的数据项还会保存在内存中,只是它不能被访问了,因为队头指针已经移到它的下一个位置了。
和栈中的情况不同,队列中的数据项不总是从数组的0下标处开始。移除了一些数据项后,队头指针会指向一个较高的下标位置。
查看操作返回队头数据项的值,然而并不从队中删除这个数据项。
要是想从空队列中移除一个数据项或想在已经满的队列中插入一个数据项,应用程序都要提示出错消息。
循环队列
当在队列中插入一个新数据项,队头的Rear箭头向上移动,移向数组下标大的位置。移除数据项时,队尾Front指针也会向上移动。这种设计可能和人们直观察觉相反,因为人们在买电影票排队时,队伍总是向前移动的,当前面的人买完票离开队伍后,其他人都向前移动。计算机中在队列里删除一个数据项后,也可以将其他数据项都向前移动,但这样做的效率很差。相反,我们通过队列中队头和队尾指针的移动保持所有数据项的位置不变。
这样设计的问题是队尾指针很快就会移到数组的末端。虽然在数组的开始部分有空的数据项单元,这是移除的数据项的位置,但是由于因为队尾指针不能再向后移动了,因此也不能再插入新的数据项,这该怎么办?
环绕式处理
为了避免队列不满却不能插入新数据项的问题,可以让队头队尾指针绕回到数组开始的位置。这就是循环队列(有时也称为“缓冲环”)。
指针回绕的过程:在队列中插入足够多的数据项,使队尾指针指向数组的未端。再删除几个数组前端的数据项。现在插入一个新的数据项。就会看到队尾指针从未端回绕到开始处的位置。新的数据项将插入这个位置。
插入更多的数据项。队尾指针如预计的那样向上移动。注意在队尾指针回绕之后, 它现在处在队头指针的下面,这就颠倒了初始的位置。这可以称为“折断的序列”:队列中的数据项存在数组两个不同的序列中。
删除足够多的数据项后,队头指针也回绕。这时队列的指针回到了初始运行时的位置状态,队头指针在队尾指针的下面。数据项也恢复为单一的连续的序列。
队列的Java代码
Queue.java程序创建了一个Queue类,它有insert()、remove()、peek()、isEmpty()和size()方法。
package 栈和队列;
class Queue{
private int maxSize;
private long[] queArray;
private int front;
private int rear;
private int nItems;
public Queue(int s){
maxSize=s;
queArray=new long[maxSize];
front=0;
rear=-1;
nItems=0;
}
public void insert(long j){
if(rear==maxSize-1)
rear=-1;
queArray[++rear]=j;
nItems++;
}
public long remove(){
long temp=queArray[front++];
if(front==maxSize)
front=0;
nItems--;
return temp;
}
public long peekFront(){
return queArray[front];
}
public boolean isEmpty(){
return (nItems==0);
}
public boolean ifFull(){
return (nItems==maxSize);
}
public int size(){
return nItems;
}
}
程序实现的Queue类中不但有front(队头)和rear(队尾)字段,还有队列中当前数据项的个数:nItems。
Insert()方法运行的前提条件是队列不满。在Main()中没有显示这个方法,不过通常应该先调用isFull()方法并且返回false后,才调用insert()方法。(更通用的做法是在insert()方法中加入检查队列是否满的判定,如果出现向已满队列里插入数据项的情况就抛出异常。)
一般情况,插入操作是rear(队尾指针)加一后,在队尾指针所指的位置处插入新的数据。但是,当rear指针指向数组的顶端,即maxSize-1位置的时候,在插入数据项之前,它必须回绕到数组的底端。回绕操作把rear设置为-1,因此当rear加1后,它等于0,是数组底端的下标值,最后nItem加一。
Remove()方法运行的前提条件是队列不空,在调用这个方法之前应该调用isEmpty()方法确保队列不空,或者在remove()方法里加入这种出错检查的机制。
移除(remove)操作总是由front指针得到队头数据项的值,然后将front加一。但是,如果这样做使front的值超过数组的顶端,front就必须绕回到数组下标为0的位置上。作这种检验的同时,先将返回值临时存储起来。最后nItem减一。
Peek()方法简单易懂:它返回front指针所指数据项的值。有些队列的实现也允许查看队列队尾数据项的值;比如这些方法可称为peekFront()、peekRear()、或者只是front()和rear()。
isEmpty()、isFull()和size()方法的实现都依赖于nItems字段,它们分别返回nItems是否等于0,是否等于maxSize,或者返回它本身值。
在Queue类中包含数据项计数字段nItems会使insert()和remove()方法增加一点额外的操作,因为insert()和remove()方法必须分别递增和递减这个变量值。这可能算不上额外的开销,但是如果处理大量的插入和移除操作,这就可能会影响性能了。
因为,一些队列的实现不使用数据项计数的字段,而是通过front和rear来计算出队列是否空或者满以及数据项的个数。如果这样做,isEmpty()、ifFull()和size()例程会相当复杂,因为就像前面讲过的那样,数据项的序列或者被折成两段,或者是连续的一段。
而且,一个奇怪的问题出现了。当队列满的时候,front和rear指针取一定的位置,但是当队列为空时,也可能呈现相同的位置关系。于是在同一时间,队列似乎可能是满的,也可能是空的。这个问题的解决方法是:让数组容量比队列数据项个数的最大值学要大一。
队列和栈一样也被用作程序员的工具。它也可以用于模拟真实世界的环境,例如模拟人们在银行里排队等待,飞机等待起飞,或者因特网络上数据包等待传送。
在计算机操作系统里,有各种队列在安静地工作着。打印作业在打印队列中等待打印。当在键盘上敲击时,也有一个存储键入内容的队列。同样,如果使用文字处理程序敲击一个键,而计算机又暂时要做其它的事,敲击的内容不会丢失,它会排在队列中等待,直到文字处理程序有时间来读取它。利用队列保证了键入内容在处理时其顺序不会改变。
队列的基本操作
队列的两个基本操作是inserting(插入)一个数据项,即把一个数据项放入队尾,另一个是removing(移除)一个数据项,即移除队头的数据项。这类似于电影爱好者排队买票时先排到队尾,然后到达队头买票后离开队列。
栈中的插入和移除数据项方法的命名是很标准,称为push和pop。队列的方法至今没有标准化的命名。“插入”可以称为put、add或enque,而“删除”可以叫delete、get或deque。插入数据项的队尾,也可以叫作back、tail或end。而移除数据项的队头,也可以叫head。下面将使用insert、remove、front和rear。
插入将值插入队尾,同时队尾箭头增加一,指向新的数据项。
数据项被移除后,同时队头指针增加一。通常实现队列时,删除的数据项还会保存在内存中,只是它不能被访问了,因为队头指针已经移到它的下一个位置了。
和栈中的情况不同,队列中的数据项不总是从数组的0下标处开始。移除了一些数据项后,队头指针会指向一个较高的下标位置。
查看操作返回队头数据项的值,然而并不从队中删除这个数据项。
要是想从空队列中移除一个数据项或想在已经满的队列中插入一个数据项,应用程序都要提示出错消息。
循环队列
当在队列中插入一个新数据项,队头的Rear箭头向上移动,移向数组下标大的位置。移除数据项时,队尾Front指针也会向上移动。这种设计可能和人们直观察觉相反,因为人们在买电影票排队时,队伍总是向前移动的,当前面的人买完票离开队伍后,其他人都向前移动。计算机中在队列里删除一个数据项后,也可以将其他数据项都向前移动,但这样做的效率很差。相反,我们通过队列中队头和队尾指针的移动保持所有数据项的位置不变。
这样设计的问题是队尾指针很快就会移到数组的末端。虽然在数组的开始部分有空的数据项单元,这是移除的数据项的位置,但是由于因为队尾指针不能再向后移动了,因此也不能再插入新的数据项,这该怎么办?
环绕式处理
为了避免队列不满却不能插入新数据项的问题,可以让队头队尾指针绕回到数组开始的位置。这就是循环队列(有时也称为“缓冲环”)。
指针回绕的过程:在队列中插入足够多的数据项,使队尾指针指向数组的未端。再删除几个数组前端的数据项。现在插入一个新的数据项。就会看到队尾指针从未端回绕到开始处的位置。新的数据项将插入这个位置。
插入更多的数据项。队尾指针如预计的那样向上移动。注意在队尾指针回绕之后, 它现在处在队头指针的下面,这就颠倒了初始的位置。这可以称为“折断的序列”:队列中的数据项存在数组两个不同的序列中。
删除足够多的数据项后,队头指针也回绕。这时队列的指针回到了初始运行时的位置状态,队头指针在队尾指针的下面。数据项也恢复为单一的连续的序列。
队列的Java代码
Queue.java程序创建了一个Queue类,它有insert()、remove()、peek()、isEmpty()和size()方法。
package 栈和队列;
class Queue{
private int maxSize;
private long[] queArray;
private int front;
private int rear;
private int nItems;
public Queue(int s){
maxSize=s;
queArray=new long[maxSize];
front=0;
rear=-1;
nItems=0;
}
public void insert(long j){
if(rear==maxSize-1)
rear=-1;
queArray[++rear]=j;
nItems++;
}
public long remove(){
long temp=queArray[front++];
if(front==maxSize)
front=0;
nItems--;
return temp;
}
public long peekFront(){
return queArray[front];
}
public boolean isEmpty(){
return (nItems==0);
}
public boolean ifFull(){
return (nItems==maxSize);
}
public int size(){
return nItems;
}
}
程序实现的Queue类中不但有front(队头)和rear(队尾)字段,还有队列中当前数据项的个数:nItems。
Insert()方法运行的前提条件是队列不满。在Main()中没有显示这个方法,不过通常应该先调用isFull()方法并且返回false后,才调用insert()方法。(更通用的做法是在insert()方法中加入检查队列是否满的判定,如果出现向已满队列里插入数据项的情况就抛出异常。)
一般情况,插入操作是rear(队尾指针)加一后,在队尾指针所指的位置处插入新的数据。但是,当rear指针指向数组的顶端,即maxSize-1位置的时候,在插入数据项之前,它必须回绕到数组的底端。回绕操作把rear设置为-1,因此当rear加1后,它等于0,是数组底端的下标值,最后nItem加一。
Remove()方法运行的前提条件是队列不空,在调用这个方法之前应该调用isEmpty()方法确保队列不空,或者在remove()方法里加入这种出错检查的机制。
移除(remove)操作总是由front指针得到队头数据项的值,然后将front加一。但是,如果这样做使front的值超过数组的顶端,front就必须绕回到数组下标为0的位置上。作这种检验的同时,先将返回值临时存储起来。最后nItem减一。
Peek()方法简单易懂:它返回front指针所指数据项的值。有些队列的实现也允许查看队列队尾数据项的值;比如这些方法可称为peekFront()、peekRear()、或者只是front()和rear()。
isEmpty()、isFull()和size()方法的实现都依赖于nItems字段,它们分别返回nItems是否等于0,是否等于maxSize,或者返回它本身值。
在Queue类中包含数据项计数字段nItems会使insert()和remove()方法增加一点额外的操作,因为insert()和remove()方法必须分别递增和递减这个变量值。这可能算不上额外的开销,但是如果处理大量的插入和移除操作,这就可能会影响性能了。
因为,一些队列的实现不使用数据项计数的字段,而是通过front和rear来计算出队列是否空或者满以及数据项的个数。如果这样做,isEmpty()、ifFull()和size()例程会相当复杂,因为就像前面讲过的那样,数据项的序列或者被折成两段,或者是连续的一段。
而且,一个奇怪的问题出现了。当队列满的时候,front和rear指针取一定的位置,但是当队列为空时,也可能呈现相同的位置关系。于是在同一时间,队列似乎可能是满的,也可能是空的。这个问题的解决方法是:让数组容量比队列数据项个数的最大值学要大一。
发表评论
-
设置JVM启动属性,设置tomcat远程调试端口
2013-02-12 17:08 984在eclipse中设置启动属性,或者在命令行运行时设置 ... -
Mysql不能连接
2011-01-11 11:07 1061com.mysql.jdbc.CommunicationsEx ... -
Java IO
2011-01-04 12:08 2243本篇主要讲述IO相关的 ... -
[J2SE]Map.Entry 类使用简介(转)
2010-12-10 09:30 855你是否已经对每次从Map中取得关键字然后再取得相应的值感觉厌倦 ... -
比较分析Vector,Arraylist,Hashtable,HashMap数据结构
2010-12-09 09:15 795线性表,链表,哈希表 ... -
JAVA jvm 参数 -Xms -Xmx -Xmn -Xss
2010-11-04 14:40 1166常见配置举例 堆大小 ... -
Error listenerStart
2010-11-04 14:37 807近日浏览论坛,发现好多人提问,都说在运行web程序时,服务器报 ... -
jvm内存调优经验总结
2010-11-04 14:37 819[color=blue][/color][size=x-sma ... -
java的final和static区别
2010-10-19 10:30 826final定义的变量可以看 ... -
Java设计模式中的11种
2010-10-14 17:35 805一:设计模式是最重要 ... -
Lucene源码分析-- Analyzer
2010-08-02 15:09 1292本文主要分析一下 Lucene输入部分——Analyzer(分 ... -
ik-analyzer
2010-08-02 15:05 971IKAnalyzer是一个开源的,基于java语言开发的轻量级 ... -
Apache Tika文档处理工具
2010-08-02 13:58 2882随着计算机使用的日益普及以及互联网的无处不在,现在有各种语言的 ... -
JDK性能优化
2010-07-29 10:35 1582jvm的server版和client版在上面的表中,我们看到有 ... -
JDK和JRE的区别
2010-07-29 09:49 835简单的说JDK是面向开发人员使用的SDK,它提供了Java的开 ... -
JAVA Process类的简单学习
2010-07-08 14:59 1352(1)执行简单的DOS命令,如打开一个记事本 ... -
Java的多线程程序设计要点
2010-07-07 09:15 6551.多线程中有主内存和 ... -
Java打包指南-JAR文件包及jar命令详解
2010-07-06 17:28 771常常在网上看到有人询问:如何把 java 程序编译成 .exe ... -
javac编译包及包引用文件
2010-07-06 17:27 2266javac和java是sun提供的编译java文件和执行cla ... -
JAVA RMI实现过程分析
2010-07-06 14:35 1727JAVA RMI 快速入门实例 本实例为参考多篇文章写就而成 ...
相关推荐
java队列实现(顺序队列、链式队列、循环队列)
java定时器、多线程(池)、java队列的demodemo,下载看看看吧
这是一个java队列实现的全部工程文件,包含了所有代码,具体的设计文档在上传的另外文件中。这个工程能够实现所有队列的操作,运行没有问题。设计的是在应用程序上的基于界面的队列操作的实现。
java 队列使用,次例子是一个模拟网络爬虫工作大致流程的小例子,里面没有具体的爬取的实现,只是对爬取的流程的模拟,使用到了java 的 ArrayBlockingQueue、ConcurrentHashMap、 这2个类和java 的 volatile 关键字...
队列实现,数据结构作业练习参考,Java实现,环境eclipes1.8
用java 队列 链表 栈不少老师大作业布置的就是这个,需要的同学就放心下载吧
NULL 博文链接:https://hoochiang.iteye.com/blog/1858476
java定时器+多线程(池)+java队列Demo
实现多线程队列抢购等功能源码,Java多线程总结之线程安全队列Queue
使用Java队列存储对象。 LinkedList创建队列。 offer()插入 poll()遍历并移除
java队列Java系列2021.pdf
下面小编就为大家分享一篇java队列实现方法(顺序队列,链式队列,循环队列),具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
java实现队列执行任务,限制线程执行的个数
数据结构Java队列PPT学习教案.pptx
java多线程模拟队列实现排队叫号,多线程模拟排队叫号取号 java多线程模拟队列实现排队叫号,多线程模拟排队叫号取号
主要介绍了Java 队列实现原理及简单实现代码的相关资料,需要的朋友可以参考下
用java语言中的数组来实现队列,其中扩容方法为在原数组的基础上乘以2,另外也测试了用java中Vector类实现队列。
redis 案例。包含, 队列操作, socket通信, 以及 socket 和 redis 配合 redis 案例。包含, 队列操作, socket通信, 以及 socket 和 redis 配合
用Java实现一个队列
用LinkedList实现一个队列的所有操作: 入队\出队\求队列长度\判断队列是否为空\打印队列等