數(shù)組實現(xiàn)Java 自定義Queue隊列及應用操作
數(shù)組實現(xiàn)Java 自定義Queue隊列及應用
Java 自定義隊列Queue:
隊列的抽象數(shù)據類型就是一個容器，其中的對象排成一個序列，我們只能訪問和取出排在最前端（ Front）的對象，只能在隊列的尾部（ Rear）插入新對象。
正是按照這一規(guī)則，才能保證最先被插入的對象首先被刪除（ FIFO）。
java本身是有自帶Queue類包，為了達到學習目的已經更好深入了解Queue隊列，自己動手自建java Queue類是個很好的學習開始：
基于數(shù)組的實現(xiàn)
„ 順序數(shù)組
借助一個定長數(shù)組 Q 來存放對象，即可簡單地實現(xiàn)隊列。那么，為了符合 FIFO 準則，應該如何表示和記錄隊列中各對象的次序呢？
一種自然的辦法就是仿照棧的實現(xiàn)，以 Q[0]作為隊首，其它對象順序往后存放。然而如此一來，每次首元素出隊之后，都需要將后續(xù)的所有元素向前順移一個單元若隊長為 n，這項工作需要O(n)時間，因此效率很低。
„ 循環(huán)數(shù)組
為了避免數(shù)組的整體移動，可以引入如下兩個變量 f 和 r：
f：始終等于 Q 的首元素在數(shù)組中的下標，即指向下次出隊元素的位置
r：始終等于 Q 的末元素的下標加一，即指向下次入隊元素的位置
一開始， f = r = 0，此時隊空。每次有對象入隊時，將其存放于 Q[r]，然后 r 加一，以指向下一單元。對稱地，每次有對象出隊之后，也將 f 加一，指向新的隊首元素。這樣，對 front()、 enqueue()和 dequeue()方法的每一次調用都只需常數(shù)時間。
然而，這還不夠。細心的讀者或許已經注意到，按照上述約定，在隊列的生命期內， f 和 r 始終在單調增加。因此，若隊列數(shù)組的容量為 N，則在經過 N 次入隊操作后， r 所指向的單元必然超出數(shù)組的范圍；在經過 N 次出隊操作后， f 所指向的單元也會出現(xiàn)類似的問題。
解決上述問題的一種簡便方法，就是在每次 f 或 r 加一后，都要以數(shù)組的長度做取模運算，以保證其所指單元的合法性。就其效果而言，這就相當于把數(shù)組的頭和尾相聯(lián)，構成一個環(huán)狀結構。
基于上述構想，可以得到如 下所示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
隊列的應用：
孩提時的你是否玩過“燙手山芋”游戲：一群小孩圍成一圈，有一個剛出鍋的山芋在他們之間傳遞。其中一個孩子負責數(shù)數(shù)，每數(shù)一次，拿著山芋的孩子就把山芋轉交給右邊的鄰居。一旦數(shù)到某個特定的數(shù)，拿著山芋的孩子就必須退出，然后重新數(shù)數(shù)。如此不斷，最后剩下的那個孩子就是幸運者。通常，數(shù)數(shù)的規(guī)則總是從 1 開始，數(shù)到 k 時讓拿著山芋的孩子出列，然后重新從 1 開始。Josephus問題可以表述為： n 個孩子玩這個游戲，最后的幸運者是誰？
為了解答這個問題，我們可以利用隊列結構來表示圍成一圈的n個孩子。一開始，假定對應于隊列首節(jié)點的那個孩子拿著山芋。然后，按照游戲的規(guī)則，把“土豆”向后傳遞到第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
隊列及其特點
隊列是人為認為的一種數(shù)據結構,并不是計算機內存中真正存儲的,所以隊列的實現(xiàn)是對順序結構或者鏈式存儲的一種封裝
特點：先進先出，通常有兩個方法 入隊:enqueue() 出隊:dequeue()
基于單向鏈表實現(xiàn)隊列
注:上一節(jié)我們自定義了鏈表,此文隊列底層運用上節(jié)的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實現(xiàn)隊列
package com.tangbaobao.queue;
import java.util.ArrayList;
import java.util.List;
/**
* 基于List實現(xiàn)隊列
*
* @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;
}
}
實現(xiàn)了比較簡單的隊列，尤其調用了封裝好的數(shù)據結構，只需知道新的數(shù)據結構怎么工作，實現(xiàn)起來比較簡單。希望能給大家一個參考，也希望大家多多支持腳本之家
相關文章
在Eclipse中部署Spring Boot/Spring Cloud應用到阿里云
這篇文章主要介紹了在Eclipse中部署Spring Boot/Spring Cloud應用到阿里云，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2018-12-12
SpringBoot2基于重復創(chuàng)建bean的問題及解決
這篇文章主要介紹了SpringBoot2基于重復創(chuàng)建bean的問題及解決方案，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-06-06
這篇文章主要介紹了Java long 轉成 String的實現(xiàn)，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-09-09
這篇文章主要給大家介紹了關于Java中new與clone操作對象的比較方法,在java中對象的誕生是我們開發(fā)人員new出來的,對象的使用也是我們開發(fā)人員進行操作的,需要的朋友可以參考下2024-07-07
基于Java Socket實現(xiàn)一個簡易在線聊天功能（一）
這篇文章主要給大家介紹基于Java Socket實現(xiàn)一個簡易在線聊天功能（一），分為客戶端和服務端兩段代碼，非常具有參考價值，感興趣的朋友一起學習吧2016-05-05
這篇文章主要介紹了線程池中使用spring aop事務增強,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-02-02
這篇文章主要為大家詳細介紹了Java實現(xiàn)微信發(fā)紅包，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-12-12
下面小編就為大家?guī)硪黄嘘PJava常見的誤解小結(來看一看)。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-05-05
這篇文章主要介紹了Java使用Socket判斷某服務能否連通代碼實例,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2019-11-11
在SpringBoot中使用jwt實現(xiàn)token身份認證的實例代碼
你還不會在SpringBoot中使用jwt實現(xiàn)token身份認證嗎,本文小編就給大家詳細的介紹一下在SpringBoot中使用jwt實現(xiàn)token身份認證的實例代碼,感興趣的同學可以自己動手試一試2023-09-09