Java 自定义队列Queue:
队列的抽象数据类型就是一个容器,其中的对象排成一个序列,我们只能访问和取出排在最前端( Front)的对象,只能在队列的尾部( Rear)插入新对象。正是按照这一规则,才能保证最先被插入的对象首先被删除( FIFO)。java本身是有自带Queue类包,为了达到学习目的已经更好深入了解Queue队列,自己动手自建java Queue类是个很好的学习开始:
基于数组的实现
„ 顺序数组
借助一个定长数组 Q 来存放对象,即可简单地实现队列。那么,为了符合 FIFO 准则,应该如何表示和记录队列中各对象的次序呢?
一种自然的办法就是仿照栈的实现,以 Q[0]作为队首,其它对象顺序往后存放。然而如此一来,每次首元素出队之后,都需要将后续的所有元素向前顺移一个单元若队长为 n,这项工作需要O(n)时间,因此效率很低。
„ 循环数组
为了避免数组的整体移动,可以引入如下两个变量 f 和 r:
f:始终等于 Q 的首元素在数组中的下标,即指向下次出队元素的位置
r:始终等于 Q 的末元素的下标加一,即指向下次入队元素的位置
一开始, f = r = 0,此时队空。每次有对象入队时,将其存放于 Q[r],然后 r 加一,以指向下一单元。对称地,每次有对象出队之后,也将 f 加一,指向新的队首元素。这样,对 front()、 enqueue()和 dequeue()方法的每一次调用都只需常数时间。
然而,这还不够。细心的读者或许已经注意到,按照上述约定,在队列的生命期内, f 和 r 始终在单调增加。因此,若队列数组的容量为 N,则在经过 N 次入队操作后, r 所指向的单元必然超出数组的范围;在经过 N 次出队操作后, f 所指向的单元也会出现类似的问题。
解决上述问题的一种简便方法,就是在每次 f 或 r 加一后,都要以数组的长度做取模运算,以保证其所指单元的合法性。就其效果而言,这就相当于把数组的头和尾相联,构成一个环状结构。
基于上述构想,可以得到如 下所示java代码:
Queue类:
package com.queue;import java.util.Arrays;/**
*
* @author gannyee
*
*/publicclassQueue {// Define capacity constant: CAPACITYprivatestaticfinalint CAPACITY =1024;// Define capacity of queueprivatestaticint capacity;// Front of queueprivatestaticint front;// Tail of queueprivatestaticint tail;// Array for queueprivatestatic Object[] array;// Constructor of Queue classpublicQueue() {this.capacity = CAPACITY;
array =new Object[capacity];
front = tail =0;
}// Get size of queuepublicstaticintgetSize() {if (isEmpty())return0;elsereturn (capacity + tail - front) % capacity;
}// Whether is emptypublicstaticbooleanisEmpty() {return (front == tail);
}// put element into the end of queuepublicstaticvoidenqueue(Object element)throws ExceptionQueueFull {if (getSize() == capacity -1)thrownew ExceptionQueueFull("Queue is full");
array[tail] = element;
tail = (tail +1) % capacity;
}// get element from queuepublicstatic Objectdequeue()throws ExceptionQueueEmpty {
Object element;if (isEmpty())thrownew ExceptionQueueEmpty("Queue is empty");
element = array[front];
front = (front +1) % capacity;return element;
}// Get the first element for queuepublicstatic ObjectfrontElement()throws ExceptionQueueEmpty {if (isEmpty())thrownew ExceptionQueueEmpty("Queue is empty");return array[front];
}// Travel all elements of queuepublicstaticvoidgetAllElements() {
Object[] arrayList =new Object[getSize()];for (int i = front,j =0; j < getSize(); i ++,j ++) {
arrayList[j] = array[i];
}
System.out.println("All elements of queue: "
+ Arrays.toString(arrayList));
}
}
自定义ExceptionStackEmpty异常类:
package com.queue;publicclassExceptionQueueEmptyextendsException {// ConstructorpublicExceptionQueueEmpty() {
}// Constructor with parameterspublicExceptionQueueEmpty(String mag) {
System.out.println(mag);
}
}
自定义ExceptionStackFull异常类
package com.queue;publicclassExceptionQueueFullextendsException {// ConstructorpublicExceptionQueueFull() {
}// Constructor with parameterspublicExceptionQueueFull(String mag) {
System.out.println(mag);
}
}
测试类:
packagecom.queue;/**
* QueueTest
* @author gannyee
*
*/
public class QueueTest {
public static void main(String[] args) {
// TODO Auto-generated method stub
Queue queue = new Queue();
System.out.println("The size of queue is: " + queue.getSize());
System.out.println("Is empty: " + queue.isEmpty());
try {
queue.enqueue(8);
queue.enqueue(3);
queue.enqueue(5);
queue.enqueue(7);
queue.enqueue(9);
queue.getAllElements();
System.out.println("The size of queue is: " + queue.getSize());
System.out.println("Is empty: " + queue.isEmpty());
System.out.println("The front element of queue: "
+ queue.frontElement());
System.out.println(queue.dequeue());
System.out.println(queue.dequeue());
System.out.println(queue.dequeue());
System.out.println(queue.dequeue());
System.out.println(queue.dequeue());
System.out.println("The size of queue is: " + queue.getSize());
System.out.println("Is empty: " + queue.isEmpty());
} catch (ExceptionQueueFull e) {
// TODO Auto-generated catch block
e.printStackTrace();
} catch (ExceptionQueueEmpty e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
测试结果:
The sizeof queueis:0Isempty:true
All elementsof queue: [8,3,5,7,9]
The sizeof queueis:5Isempty:false
The front elementof queue:883579
The sizeof queueis:0Isempty:true
队列的应用:
孩提时的你是否玩过“烫手山芋”游戏:一群小孩围成一圈,有一个刚出锅的山芋在他们之间传递。其中一个孩子负责数数,每数一次,拿着山芋的孩子就把山芋转交给右边的邻居。一旦数到某个特定的数,拿着山芋的孩子就必须退出,然后重新数数。如此不断,最后剩下的那个孩子就是幸运者。通常,数数的规则总是从 1 开始,数到 k 时让拿着山芋的孩子出列,然后重新从 1 开始。Josephus问题可以表述为: n 个孩子玩这个游戏,最后的幸运者是谁?
为了解答这个问题,我们可以利用队列结构来表示围成一圈的n个孩子。一开始,假定对应于队列首节点的那个孩子拿着山芋。然后,按照游戏的规则,把“土豆”向后传递到第k个孩子(交替进行k次dequeue()和k次enqueue()操作),并让她出队( dequeue())。如此不断迭代,直到队长(getSize())为 1。
Java代码如下:
package com.queue;publicclass QueueBuilder {// Building string type array for queuepublicstatic Queue queueBuild(String[] str) {
Queuequeue =new Queue();for (int i =0; i < str.length; i++) {try {queue.enqueue(str[i]);
}catch (ExceptionQueueFull e) {// TODO Auto-generated catch block
e.printStackTrace();
}
}returnqueue;
}// Weed out the kth kid who get the sweet potatopublicstatic String gameWiner(Queuequeue,int k)
throws ExceptionQueueFull, ExceptionQueueEmpty {if (queue.isEmpty())return null;while (queue.getSize() >1) {queue.getAllElements();// Output recently queuefor (int i =0; i < k -1; i++)queue.enqueue(queue.dequeue());
System.out.println("\n\t" +queue.dequeue() +": Weep out");
}return (String)queue.dequeue();
}
}
package com.queue;publicclass QueueGame {publicstaticvoidmain(String[] args) throws ExceptionQueueFull, ExceptionQueueEmpty {// TODO Auto-generated method stub
String[] kid = {"Alice","Bob","Cindy","Doug","Ed","Fred","Gene","Hope","Irene","Jack","Kim","Lance","Mike","Nancy","Ollie"};
QueueBuilder qb =new QueueBuilder();
System.out.println("The luck dog is: " + qb.gameWiner(qb.queueBuild(kid),5));
}
}
测试结果:
All elementsof queue: [Alice, Bob, Cindy, Doug, Ed, Fred, Gene, Hope, Irene, Jack, Kim, Lance, Mike, Nancy, Ollie]
Ed: weepoutAll elementsof queue: [Fred, Gene, Hope, Irene, Jack, Kim, Lance, Mike, Nancy, Ollie, Alice, Bob, Cindy, Doug]
Jack: weepoutAll elementsof queue: [Kim, Lance, Mike, Nancy, Ollie, Alice, Bob, Cindy, Doug, Fred, Gene, Hope, Irene]
Ollie: weepoutAll elementsof queue: [Alice, Bob, Cindy, Doug, Fred, Gene, Hope, Irene, Kim, Lance, Mike, Nancy]
Fred: weepoutAll elementsof queue: [Gene, Hope, Irene, Kim, Lance, Mike, Nancy, Alice, Bob, Cindy, Doug]
Lance: weepoutAll elementsof queue: [Mike, Nancy, Alice, Bob, Cindy, Doug, Gene, Hope, Irene, Kim]
Cindy: weepoutAll elementsof queue: [Doug, Gene, Hope, Irene, Kim, Mike, Nancy, Alice, Bob]
Kim: weepoutAll elementsof queue: [Mike, Nancy, Alice, Bob, Doug, Gene, Hope, Irene]
Doug: weepoutAll elementsof queue: [Gene, Hope, Irene, Mike, Nancy, Alice, Bob]
Nancy: weepoutAll elementsof queue: [Alice, Bob, Gene, Hope, Irene, Mike]
Irene: weepoutAll elementsof queue: [Mike, Alice, Bob, Gene, Hope]
Hope: weepoutAll elementsof queue: [Mike, Alice, Bob, Gene]
Mike: weepoutAll elementsof queue: [Alice, Bob, Gene]
Bob: weepoutAll elementsof queue: [Gene, Alice]
Gene: weepout
The luck dogis: Alice
文章参考:数据结构与算法( Java 描述)邓俊辉 著
转载请注明出处,谢谢!
http://blog.csdn.net/github_27609763/article/details/46434301