Java数组自定义Queue队列 数组实现Java 自定义Queue队列及应用操作
YatKam 人气:0数组实现Java 自定义Queue队列及应用
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 * */ public class Queue { // Define capacity constant: CAPACITY private static final int CAPACITY = 1024; // Define capacity of queue private static int capacity; // Front of queue private static int front; // Tail of queue private static int tail; // Array for queue private static Object[] array; // Constructor of Queue class public Queue() { this.capacity = CAPACITY; array = new Object[capacity]; front = tail = 0; } // Get size of queue public static int getSize() { if (isEmpty()) return 0; else return (capacity + tail - front) % capacity; } // Whether is empty public static boolean isEmpty() { return (front == tail); } // put element into the end of queue public static void enqueue(Object element) throws ExceptionQueueFull { if (getSize() == capacity - 1) throw new ExceptionQueueFull("Queue is full"); array[tail] = element; tail = (tail + 1) % capacity; } // get element from queue public static Object dequeue() throws ExceptionQueueEmpty { Object element; if (isEmpty()) throw new ExceptionQueueEmpty("Queue is empty"); element = array[front]; front = (front + 1) % capacity; return element; } // Get the first element for queue public static Object frontElement() throws ExceptionQueueEmpty { if (isEmpty()) throw new ExceptionQueueEmpty("Queue is empty"); return array[front]; } // Travel all elements of queue public static void getAllElements() { 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; public class ExceptionQueueEmpty extends Exception { // Constructor public ExceptionQueueEmpty() { } // Constructor with parameters public ExceptionQueueEmpty(String mag) { System.out.println(mag); } }
自定义ExceptionStackFull异常类
package com.queue; public class ExceptionQueueFull extends Exception { // Constructor public ExceptionQueueFull() { } // Constructor with parameters public ExceptionQueueFull(String mag) { System.out.println(mag); } }
测试类:
package com.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 size of queue is: 0
Is empty: true
All elements of queue: [8, 3, 5, 7, 9]
The size of queue is: 5
Is empty: false
The front element of queue: 8
8
3
5
7
9
The size of queue is: 0
Is empty: true
队列的应用:
孩提时的你是否玩过“烫手山芋”游戏:一群小孩围成一圈,有一个刚出锅的山芋在他们之间传递。其中一个孩子负责数数,每数一次,拿着山芋的孩子就把山芋转交给右边的邻居。一旦数到某个特定的数,拿着山芋的孩子就必须退出,然后重新数数。如此不断,最后剩下的那个孩子就是幸运者。通常,数数的规则总是从 1 开始,数到 k 时让拿着山芋的孩子出列,然后重新从 1 开始。Josephus问题可以表述为: n 个孩子玩这个游戏,最后的幸运者是谁?
为了解答这个问题,我们可以利用队列结构来表示围成一圈的n个孩子。一开始,假定对应于队列首节点的那个孩子拿着山芋。然后,按照游戏的规则,把“土豆”向后传递到第k个孩子(交替进行k次dequeue()和k次enqueue()操作),并让她出队( dequeue())。如此不断迭代,直到队长(getSize())为 1。
Java代码如下:
package com.queue; public class QueueBuilder { // Building string type array for queue public static Queue queueBuild(String[] str) { Queue queue = 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(); } } return queue; } // Weed out the kth kid who get the sweet potato public static String gameWiner(Queue queue, int k) throws ExceptionQueueFull, ExceptionQueueEmpty { if (queue.isEmpty()) return null; while (queue.getSize() > 1) { queue.getAllElements();// Output recently queue for (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; public class QueueGame { public static void main(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 elements of queue: [Alice, Bob, Cindy, Doug, Ed, Fred, Gene, Hope, Irene, Jack, Kim, Lance, Mike, Nancy, Ollie]
Ed: weep out
All elements of queue: [Fred, Gene, Hope, Irene, Jack, Kim, Lance, Mike, Nancy, Ollie, Alice, Bob, Cindy, Doug]Jack: weep out
All elements of queue: [Kim, Lance, Mike, Nancy, Ollie, Alice, Bob, Cindy, Doug, Fred, Gene, Hope, Irene]Ollie: weep out
All elements of queue: [Alice, Bob, Cindy, Doug, Fred, Gene, Hope, Irene, Kim, Lance, Mike, Nancy]Fred: weep out
All elements of queue: [Gene, Hope, Irene, Kim, Lance, Mike, Nancy, Alice, Bob, Cindy, Doug]Lance: weep out
All elements of queue: [Mike, Nancy, Alice, Bob, Cindy, Doug, Gene, Hope, Irene, Kim]Cindy: weep out
All elements of queue: [Doug, Gene, Hope, Irene, Kim, Mike, Nancy, Alice, Bob]Kim: weep out
All elements of queue: [Mike, Nancy, Alice, Bob, Doug, Gene, Hope, Irene]Doug: weep out
All elements of queue: [Gene, Hope, Irene, Mike, Nancy, Alice, Bob]Nancy: weep out
All elements of queue: [Alice, Bob, Gene, Hope, Irene, Mike]Irene: weep out
All elements of queue: [Mike, Alice, Bob, Gene, Hope]Hope: weep out
All elements of queue: [Mike, Alice, Bob, Gene]Mike: weep out
All elements of queue: [Alice, Bob, Gene]Bob: weep out
All elements of queue: [Gene, Alice]Gene: weep out
The luck dog is: Alice
自定义简单Queue
队列及其特点
队列是人为认为的一种数据结构,并不是计算机内存中真正存储的,所以队列的实现是对顺序结构或者链式存储的一种封装
特点:先进先出,通常有两个方法 入队:enqueue() 出队:dequeue()
基于单向链表实现队列
注:上一节我们自定义了链表,此文队列底层运用上节的LinkedList
package com.tangbaobao.queue; import com.tangbaobao.LinkedList.MyLinkedList; /** * 用单向链表队列 * * @author 唐学俊 * @create 2018/03/11 **/ public class MyQueue { private int size; MyLinkedList linkedList = null; /** * 入队 * * @param value */ public void enqueue(int value) { if (linkedList == null) { linkedList = new MyLinkedList(); } linkedList.add(value); size++; } /** * 出队 * * @return */ public Object dequeue() { Object value = 0; if (linkedList != null) { //每次弹出队列的头 value = linkedList.get(0); linkedList.removeAt(0); size--; } else { try { throw new Exception("队列中没有元素"); } catch (Exception e) { e.printStackTrace(); } } return value; } /** * 返回队列大小 * * @return */ public int size() { return size; } }
基于ArrayList实现队列
package com.tangbaobao.queue; import java.util.ArrayList; import java.util.List; /** * 基于List实现队列 * * @author 唐学俊 * @create 2018/03/11 **/ public class ListQueue { private int size; private List<Object> list = null; public void enqueue(int value) { if (list == null) { list = new ArrayList<>(); } list.add(value); size++; } public Object dequeue() { Object value = 0; if (list != null) { value = list.get(0); list.remove(0); size--; } else { try { throw new Exception("队列中没有元素"); } catch (Exception e) { e.printStackTrace(); } } return value; } /** * 返回队列大小 * * @return */ public int size() { return size; } }
实现了比较简单的队列,尤其调用了封装好的数据结构,只需知道新的数据结构怎么工作,实现起来比较简单。希望能给大家一个参考,也希望大家多多支持
加载全部内容