数据结构Java实现07----队列：顺序队列&顺序循环队列、链式队列、顺序优先队列
一、队列的概念：
队列（简称作队，Queue）也是一种特殊的线性表，队列的数据元素以及数据元素间的逻辑关系和线性表完全相同，其差别是线性表允许在任意位置插入和删除，而队列只允许在其一端进行插入操作在其另一端进行删除操作。
队列中允许进行插入操作的一端称为队尾，允许进行删除操作的一端称为队头。队列的插入操作通常称作入队列，队列的删除操作通常称作出队列。
下图是一个依次向队列中插入数据元素a0,a1,...,an-1后的示意图：
上图中，a0是当前 队头数据元素，an-1是当前 队尾数据元素。
为了避免当只有一个元素时，对头和队尾重合使得处理变得麻烦，所以引入两个指针：front指针指向队头元素，rear指针指向队尾元素的下一个位置，这样的话，当front指针等于rear时，此队列不是还剩一个元素，而是空队列。
二、队列的抽象数据类型：
数据集合：
队列的数据集合可以表示为a0,a1,…,an-1，每个数据元素的数据类型可以是任意的类型。
操作集合：
（1）入队列append(obj)：把数据元素obj插入队尾。
（2）出队列delete()：把队头数据元素删除并由函数返回。
（3）取队头数据元素getFront()：取队头数据元素并由函数返回。
（4）非空否isEmpty()：非空否。若队列非空，则函数返回false，否则函数返回true。
三、循环顺序队列：
线性表有顺序存储和链式存储，队列是一种特殊的线性表，同样也存在这两种存储方式。我们先来看一下队列的顺序存储。
1、顺序队列的“假溢出”：
上图中，front指针指向队头元素，rear指针指向队尾元素的下一个位置。图(d)中b、c、d出队后，front指针指向元素e，rear指针在数组外面。假设这个队列的总个数不超过5个，但目前如果接着入队的话，因数组末尾元素已经被占用，再向后加就会产生数组越界的错误，可实际上队列在下标为0、1、2、3、4的地方还是空闲的，我们把这种现象叫做“假溢出”。
2、循环顺序队列：
所以解决假溢出的办法就是后面满了，就再从头开始，也就是头尾相接的循环。我们把队列的这种逻辑上首尾相连的顺序存储结构称为循环队列。
如何判断循环队列究竟是空的还是满的：
现在问题又来了，我们之前说，空队列时，front指针等于rear指针，那么现在循环队列满的时候，也是front等于rear，那么如何判断循环队列究竟是空的还是满的？有如下办法：
办法1：设置一个标志位flag。初始时置flag=0；每当入队列操作成功就置flag=1；每当出队列操作成功就置flag=0。则队列空的判断条件为：rear == front && tag==0；队列满的判断条件为：rear = = front && tag= =1。办法2：保留一个元素的存储空间。此时，队列满时的判断条件为 (rear + 1) % maxSize == front；队列空的判断条件还是front == rear。办法3：设计一个计数器count，统计队列中的元素个数。此时，队列满的判断条件为：count > 0 && rear == front ；队列空的判断条件为count == 0。我们在接下来的代码中采用方法3来实现。
3、代码实现：(循环顺序队列的创建)
(1)Queue.java:(队列接口)
1//队列接口2publicinterfaceQueue {34//入队5publicvoidappend(Object obj)throwsException;67//出队8publicObject delete()throwsException;910//获得队头元素11publicObject getFront()throwsException;1213//判断对列是否为空14publicbooleanisEmpty();15}
(2)CircleSequenceQueue.java:（循环顺序队列）
1//循环顺序队列2publicclassCircleSequenceQueueimplementsQueue {34staticfinalintdefaultSize = 10;//默认队列的长度5intfront;//队头6intrear;//队尾7intcount;//统计元素个数的计数器8intmaxSize;//队的最大长度9Object[] queue;//队列1011publicCircleSequenceQueue() {12init(defaultSize);13}1415publicCircleSequenceQueue(intsize) {16init(size);17}1819publicvoidinit(intsize) {20maxSize =size;21front = rear = 0;22count = 0;23queue =newObject[size];24}2526@Override27publicvoidappend(Object obj)throwsException {28//TODO Auto-generated method stub29if(count > 0 && front ==rear) {30thrownewException("队列已满！");31}32queue[rear] =obj;33rear = (rear + 1) %maxSize;34count++;35}3637@Override38publicObject delete()throwsException {39//TODO Auto-generated method stub40if(isEmpty()) {41thrownewException("队列为空！");42}43Object obj =queue[front];44front = (front + 1) %maxSize;45count--;46returnobj;47}4849@Override50publicObject getFront()throwsException {51//TODO Auto-generated method stub52if(!isEmpty()) {53returnqueue[front];54}else{55returnnull;56}57}5859@Override60publicbooleanisEmpty() {61//TODO Auto-generated method stub62returncount == 0;63}6465}
(3)Test.java:
1publicclassTest {2publicstaticvoidmain(String[] args)throwsException {34CircleSequenceQueue queue =newCircleSequenceQueue();5queue.append("a");6queue.append("b");7queue.append("c");8queue.append("d");9queue.append("e");10queue.append("f");1112queue.delete();13queue.delete();1415queue.append("g");1617while(!queue.isEmpty()) {18System.out.PRintln(queue.delete());19}20}21}
运行效果：
4、循环队列应用：
使用顺序循环队列和多线程实现一个排队买票的例子。而且，我们只允许这个队伍中同时排队的只有10个人，那就需要用到队列了。
生产者（等候买票）
消费者 (买票离开)
这里面我们需要用到上面的Queue.java类和CircleSequenceQueue.java类。
代码结构：
(3)WindowQueue.java:
1//卖票窗口2publicclassWindowQueue {34//卖票的队列5intmaxSize = 10;6CircleSequenceQueue queue =newCircleSequenceQueue(maxSize);7intnum = 0;//统计卖票的数量，一天最多卖100张票。8booleanisAlive =true;//判断是否继续卖票。910//排队买票11publicsynchronizedvoidproducer()throwsException {12if(queue.count <maxSize) {13queue.append(num++);//等待买票的数量加114System.out.println("第" + num + "个客户排队等待买票！");15this.notifyAll();//唤醒卖票的线程16}else{17try{18System.out.println("队列已满...请等待！");19this.wait();//队列满时，排队买票线程等待。20}catch(Exception ex) {21ex.printStackTrace();22}23}24}2526//卖票27publicsynchronizedvoidconsumer()throwsException {28if(queue.count > 0) {29Object obj =queue.delete();30inttemp =Integer.parseInt(obj.toString());31System.out.println("第" + (temp + 1) + "个客户买到票离开队列！");32//如果当前队列为空，并且卖出票的数量大于等于100，说明卖票结束33if(queue.isEmpty() &&this.num >= 100) {34this.isAlive =false;35}36this.notifyAll();//唤醒排队买票的线程。37}else{38try{39System.out.println("队列已空...请等待！");40this.wait();//队列空时，卖票线程等待。41}catch(Exception ex) {42ex.printStackTrace();43}44}45}46}
(4)Producer.java:
1//买票者2publicclassProducerimplementsRunnable {34WindowQueue queue;56publicProducer(WindowQueue queue) {7this.queue =queue;8}910@Override11publicvoidrun() {12//TODO Auto-generated method stub13while(queue.num < 100) {14try{15queue.producer();16}catch(Exception ex) {17ex.printStackTrace();18}19}20}2122}
(5)Consumer.java:
//卖票者publicclassConsumerimplementsRunnable {
WindowQueue queue;publicConsumer(WindowQueue queue) {this.queue =queue;
}
@Overridepublicvoidrun() {//TODO Auto-generated method stubwhile(queue.isAlive) {try{
queue.consumer();
}catch(Exception ex) {
ex.printStackTrace();
}
}
}
}
(6)test.java:
1publicclassTest {23publicstaticvoidmain(String[] args)throwsException {45WindowQueue queue =newWindowQueue();67Producer p =newProducer(queue);//注意一定要传同一个窗口对象8Consumer c =newConsumer(queue);910//排队买票线程11Thread pThread =newThread(p);12//卖票线程13Thread cThread =newThread(c);1415pThread.start();//开始排队买票16cThread.start();//开始卖票17}1819}
注意第07行的注释。
运行效果：
四、链式队列：
链式队列其实就是特殊的单链表，只不过它只能尾进头出而已。链式队列的存储结构如下图所示：
1、链式队列的实现：
(1)Node.java:结点类
1//结点类2publicclassNode {34Object element;//数据域5Node next;//指针域67//头结点的构造方法8publicNode(Node nextval) {9this.next =nextval;10}1112//非头结点的构造方法13publicNode(Object obj, Node nextval) {14this.element =obj;15this.next =nextval;16}1718//获得当前结点的后继结点19publicNode getNext() {20returnthis.next;21}2223//获得当前的数据域的值24publicObject getElement() {25returnthis.element;26}2728//设置当前结点的指针域29publicvoidsetNext(Node nextval) {30this.next =nextval;31}3233//设置当前结点的数据域34publicvoidsetElement(Object obj) {35this.element =obj;36}3738publicString toString() {39returnthis.element.toString();40}41}
(2)Queue.java:
1//队列接口2publicinterfaceQueue {34//入队5publicvoidappend(Object obj)throwsException;67//出队8publicObject delete()throwsException;910//获得队头元素11publicObject getFront()throwsException;1213//判断对列是否为空14publicbooleanisEmpty();15}
(3)LinkQueue.java:
1publicclassLinkQueueimplementsQueue {23Node front;//队头4Node rear;//队尾5intcount;//计数器67publicLinkQueue() {8init();9}1011publicvoidinit() {12front = rear =null;13count = 0;14}1516@Override17publicvoidappend(Object obj)throwsException {18//TODO Auto-generated method stub19Node node =newNode(obj,null);2021//如果当前队列不为空。22if(rear !=null) {23rear.next = node;//队尾结点指向新结点24}2526rear = node;//设置队尾结点为新结点2728//说明要插入的结点是队列的第一个结点29if(front ==null) {30front =node;31}32count++;33}3435@Override36publicObject delete()throwsException {37//TODO Auto-generated method stub38if(isEmpty()) {39newException("队列已空！");40}41Node node =front;42front =front.next;43count--;44returnnode.getElement();45}4647@Override48publicObject getFront()throwsException {49//TODO Auto-generated method stub50if(!isEmpty()) {51returnfront.getElement();52}else{53returnnull;54}55}5657@Override58publicbooleanisEmpty() {59//TODO Auto-generated method stub60returncount == 0;61}6263}
(4)Test.java:
1publicclassTest {23publicstaticvoidmain(String[] args)throwsException {45LinkQueue queue =newLinkQueue();6queue.append("a");7queue.append("b");8queue.append("c");9queue.append("d");10queue.append("e");11queue.append("f");1213queue.delete();14queue.delete();1516queue.append("g");1718while(!queue.isEmpty()) {19System.out.println(queue.delete());20}21}22}
运行效果：
2、链式队列的应用：
题目：
编写一个判断一个字符串是否是回文的算法。
思路：
设字符数组str中存放了要判断的字符串。把字符数组中的字符逐个分别存入一个队列和栈中，然后逐个出队和出栈比较出队的字符与出栈的字符是否相同，若全部相等则该字符串为回文。
代码实现：
这里面需要用到上面一段中的LinkQueue类。代码结构如下：
(4)Stack.java:栈接口
1//栈接口2publicinterfaceStack {34//入栈5publicvoidpush(Object obj)throwsException;67//出栈8publicObject pop()throwsException;910//获得栈顶元素11publicObject getTop()throwsException;1213//判断栈是否为空14publicbooleanisEmpty();15}
(5)LinkStack.java:
1publicclassLinkStackimplementsStack {23Node head;//栈顶指针4intsize;//结点的个数56publicLinkStack() {7head =null;8size = 0;9}1011@Override12publicObject getTop()throwsException {13//TODO Auto-generated method stub14returnhead.getElement();15}1617@Override18publicbooleanisEmpty() {19//TODO Auto-generated method stub20returnhead ==null;21}2223@Override24publicObject pop()throwsException {25//TODO Auto-generated method stub26if(isEmpty()) {27thrownewException("栈为空！");28}29Object obj =head.getElement();30head =head.getNext();31size--;32returnobj;3334}3536@Override37publicvoidpush(Object obj)throwsException {38//TODO Auto-generated method stub39head =newNode(obj, head);40size++;41}4243}
(6)Test.java:测试类
1publicclassTest {23publicstaticvoidmain(String[] args)throwsException {45String str1 = "ABCDCBA";//是回文6String str2 = "ABCDECAB";//不是回文78try{9if(Test.isHuiWen(str1)) {10System.out.println(str2 + ":是回文！");11}else{12System.out.println(str2 + ":不是回文！");13}14}catch(Exception ex) {15ex.printStackTrace();16}17}181920//方法：判断字符串是否回文21publicstaticbooleanisHuiWen(String str)throwsException {22intn =str.length();23LinkStack stack =newLinkStack();//创建堆栈24LinkQueue queue =newLinkQueue();//创建队列25for(inti = 0; i < n; i++) {26stack.push(str.subSequence(i, i + 1));//把字符串每个字符压进堆栈27queue.append(str.subSequence(i, i + 1));//把字符串每个字符压入队列28}29while(!queue.isEmpty() && !stack.isEmpty()) {30if(!queue.delete().equals(stack.pop())) {//出队列，出栈，同时判断是否相同31returnfalse;32}33}3435returntrue;36}3738}
3、循环队列和链式队列的比较：
（1）从时间上看，它们的基本操作都是常数时间，即O(1)的。不过循环队列是事先申请好空间，使用期间不释放；而链式队列，每次申请和释放结点也会存在一定的时间开销，如果入栈和出栈比较频繁，则两者还是有细微的差别。
（2）从空间上看，循环队列必须有一个固定的长度，所以就有了存储元素个数和空间浪费的问题。而链式队列不存在这个问题，尽管它需要一个指针域，会产生一些空间上的开销，但也可以接受。所以在空间上，链式队列更加灵活。
总结：总的来说，在可以确定队列长度的最大值的情况下，建议用循环队列，如果你无法估计队列的长度，那就用链式队列。
五、优先级队列：
优先级队列是带有优先级的队列。
用顺序存储结构实现的优先级队列称作顺序优先级队列。
用链式存储结构存储的优先级队列称作链式优先级队列。
顺序优先级队列和顺序循环队列相比主要有两点不同：
（1）对于顺序优先级队列来说，出队列操作不是把队头数据元素出队列，而是把队列中优先级最高的数据元素出队列。（入队操作没区别）
（2）对于顺序优先级队列来说，数据元素由两部分组成，一部分是原先意义上的数据元素，另一部分是优先级。通常设计优先级为int类型的数值，并规定数值越小优先级越高。
1、顺序优先队列的实现：
设计顺序优先级队列分为两个类：
数据元素类
优先级队列类
代码实现：
(1)Element.java:
1//优先级队列元素类2publicclassElement {34privateObject element;//数据5privateintpriority;//优先级67publicElement(Object obj,intpriority) {8this.element =obj;9this.priority =priority;10}1112publicObject getElement() {13returnelement;14}1516publicvoidsetElement(Object element) {17this.element =element;18}1920publicintgetPriority() {21returnpriority;22}2324publicvoidsetPriority(intpriority) {25this.priority =priority;26}2728}
(2)Queue.java:
1//队列接口2publicinterfaceQueue {34//入队5publicvoidappend(Object obj)throwsException;67//出队8publicObject delete()throwsException;910//获得队头元素11publicObject getFront()throwsException;1213//判断对列是否为空14publicbooleanisEmpty();15}
(3)PrioritySequenceQueue.java:
1//优先级队列2publicclassPrioritySequenceQueueimplementsQueue {34staticfinalintdefaultSize = 10;//默认队列长度5intfront;//队头6intrear;//队尾7intcount;//计数器8intmaxSize;//队列最大长度9Element[] queue;//队列1011publicPrioritySequenceQueue() {12init(defaultSize);13}1415publicPrioritySequenceQueue(intsize) {16init(size);17}1819publicvoidinit(intsize) {20maxSize =size;21front = rear = 0;22count = 0;23queue =newElement[size];24}2526@Override27publicvoidappend(Object obj)throwsException {28//TODO Auto-generated method stub29//如果队列已满30if(count >=maxSize) {31thrownewException("队列已满！");32}33queue[rear] =(Element) obj;34rear++;35count++;36}3738@Override39publicObject delete()throwsException {40//TODO Auto-generated method stub41if(isEmpty()) {42thrownewException("队列为空！");43}44//默认第一个元素为优先级最高的。45Element min = queue[0];46intminIndex = 0;47for(inti = 0; i < count; i++) {48if(queue[i].getPriority() <min.getPriority()) {49min =queue[i];50minIndex =i;51}52}5354//找的优先级别最高的元素后，把该元素后面的元素向前移动。55for(inti = minIndex + 1; i < count; i++) {56queue[i - 1] = queue[i];//移动元素57}58rear--;59count--;60returnmin;61}6263@Override64publicObject getFront()throwsException {65//TODO Auto-generated method stub66if(isEmpty()) {67thrownewException("队列为空！");68}69//默认第一个元素为优先级最高的。70Element min = queue[0];71intminIndex = 0;72for(inti = 0; i < count; i++) {73if(queue[i].getPriority() <min.getPriority()) {74min =queue[i];75minIndex =i;76}77}78returnmin;79}8081@Override82publicbooleanisEmpty() {83//TODO Auto-generated method stub84returncount == 0;85}8687}
2、代码测试：
设计一个程序模仿操作系统的进程管理问题。进程服务按优先级高的先服务，优先级相同的先到先服务的原则管理。
模仿数据包含两个部分：进程编号和优先级。如下有五个进程：
1 30
2 20
3 40
4 20
5 0 ----------优先级最高，先服务
(4)Test.java:
1publicclassTest {23publicstaticvoidmain(String[] args)throwsException {45PrioritySequenceQueue queue =newPrioritySequenceQueue();6Element temp;78//五个进程入队9queue.append(newElement(1, 30));10queue.append(newElement(2, 20));11queue.append(newElement(3, 40));12queue.append(newElement(4, 20));13queue.append(newElement(5, 0));1415//按照优先级出队。16System.out.println("编号 优先级");17while(!queue.isEmpty()) {18temp =(Element) queue.delete();19System.out.println(temp.getElement() + " " +temp.getPriority());20}21}22}
运行效果：