数组实现Java 自定义Queue队列及应用操作

数组实现Java 自定义Queue队列及应用操作

数组实现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 加一，http://以指向下一单元。对称地，每次有对象出队之后，也将 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, AlexhdIice, 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

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;

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。