數(shù)組實(shí)現(xiàn)Java 自定義Queue隊(duì)列及應(yīng)用操作

更新時(shí)間：2021年06月07日 10:33:48 作者：YatKam

這篇文章主要介紹了數(shù)組實(shí)現(xiàn)Java 自定義Queue隊(duì)列及應(yīng)用操作，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教

數(shù)組實(shí)現(xiàn)Java 自定義Queue隊(duì)列及應(yīng)用

Java 自定義隊(duì)列Queue:

隊(duì)列的抽象數(shù)據(jù)類型就是一個(gè)容器，其中的對(duì)象排成一個(gè)序列，我們只能訪問和取出排在最前端（ Front）的對(duì)象，只能在隊(duì)列的尾部（ Rear）插入新對(duì)象。

正是按照這一規(guī)則，才能保證最先被插入的對(duì)象首先被刪除（ FIFO）。

java本身是有自帶Queue類包，為了達(dá)到學(xué)習(xí)目的已經(jīng)更好深入了解Queue隊(duì)列，自己動(dòng)手自建java Queue類是個(gè)很好的學(xué)習(xí)開始：

基于數(shù)組的實(shí)現(xiàn)

„ 順序數(shù)組

借助一個(gè)定長(zhǎng)數(shù)組 Q 來存放對(duì)象，即可簡(jiǎn)單地實(shí)現(xiàn)隊(duì)列。那么，為了符合 FIFO 準(zhǔn)則，應(yīng)該如何表示和記錄隊(duì)列中各對(duì)象的次序呢？

一種自然的辦法就是仿照棧的實(shí)現(xiàn)，以 Q[0]作為隊(duì)首，其它對(duì)象順序往后存放。然而如此一來，每次首元素出隊(duì)之后，都需要將后續(xù)的所有元素向前順移一個(gè)單元若隊(duì)長(zhǎng)為 n，這項(xiàng)工作需要O(n)時(shí)間，因此效率很低。

„ 循環(huán)數(shù)組

為了避免數(shù)組的整體移動(dòng)，可以引入如下兩個(gè)變量 f 和 r：

f：始終等于 Q 的首元素在數(shù)組中的下標(biāo)，即指向下次出隊(duì)元素的位置

r：始終等于 Q 的末元素的下標(biāo)加一，即指向下次入隊(duì)元素的位置

一開始， f = r = 0，此時(shí)隊(duì)空。每次有對(duì)象入隊(duì)時(shí)，將其存放于 Q[r]，然后 r 加一，以指向下一單元。對(duì)稱地，每次有對(duì)象出隊(duì)之后，也將 f 加一，指向新的隊(duì)首元素。這樣，對(duì) front()、 enqueue()和 dequeue()方法的每一次調(diào)用都只需常數(shù)時(shí)間。

然而，這還不夠。細(xì)心的讀者或許已經(jīng)注意到，按照上述約定，在隊(duì)列的生命期內(nèi)， f 和 r 始終在單調(diào)增加。因此，若隊(duì)列數(shù)組的容量為 N，則在經(jīng)過 N 次入隊(duì)操作后， r 所指向的單元必然超出數(shù)組的范圍；在經(jīng)過 N 次出隊(duì)操作后， f 所指向的單元也會(huì)出現(xiàn)類似的問題。

解決上述問題的一種簡(jiǎn)便方法，就是在每次 f 或 r 加一后，都要以數(shù)組的長(zhǎng)度做取模運(yùn)算，以保證其所指單元的合法性。就其效果而言，這就相當(dāng)于把數(shù)組的頭和尾相聯(lián)，構(gòu)成一個(gè)環(huán)狀結(jié)構(gòu)。

基于上述構(gòu)想，可以得到如下所示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);
    }
}

測(cè)試類:

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();
        }
    }
}

測(cè)試結(jié)果：

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

隊(duì)列的應(yīng)用：

孩提時(shí)的你是否玩過“燙手山芋”游戲：一群小孩圍成一圈，有一個(gè)剛出鍋的山芋在他們之間傳遞。其中一個(gè)孩子負(fù)責(zé)數(shù)數(shù)，每數(shù)一次，拿著山芋的孩子就把山芋轉(zhuǎn)交給右邊的鄰居。一旦數(shù)到某個(gè)特定的數(shù)，拿著山芋的孩子就必須退出，然后重新數(shù)數(shù)。如此不斷，最后剩下的那個(gè)孩子就是幸運(yùn)者。通常，數(shù)數(shù)的規(guī)則總是從 1 開始，數(shù)到 k 時(shí)讓拿著山芋的孩子出列，然后重新從 1 開始。Josephus問題可以表述為： n 個(gè)孩子玩這個(gè)游戲，最后的幸運(yùn)者是誰？

為了解答這個(gè)問題，我們可以利用隊(duì)列結(jié)構(gòu)來表示圍成一圈的n個(gè)孩子。一開始，假定對(duì)應(yīng)于隊(duì)列首節(jié)點(diǎn)的那個(gè)孩子拿著山芋。然后，按照游戲的規(guī)則，把“土豆”向后傳遞到第k個(gè)孩子（交替進(jìn)行k次dequeue()和k次enqueue()操作），并讓她出隊(duì)（ dequeue()）。如此不斷迭代，直到隊(duì)長(zhǎng)（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));
    }
}

測(cè)試結(jié)果：

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

自定義簡(jiǎn)單Queue

隊(duì)列及其特點(diǎn)

隊(duì)列是人為認(rèn)為的一種數(shù)據(jù)結(jié)構(gòu),并不是計(jì)算機(jī)內(nèi)存中真正存儲(chǔ)的,所以隊(duì)列的實(shí)現(xiàn)是對(duì)順序結(jié)構(gòu)或者鏈?zhǔn)酱鎯?chǔ)的一種封裝

特點(diǎn)：先進(jìn)先出，通常有兩個(gè)方法入隊(duì):enqueue() 出隊(duì):dequeue()

這里寫圖片描述

基于單向鏈表實(shí)現(xiàn)隊(duì)列

注:上一節(jié)我們自定義了鏈表,此文隊(duì)列底層運(yùn)用上節(jié)的LinkedList

package com.tangbaobao.queue;
import com.tangbaobao.LinkedList.MyLinkedList;
/**
 * 用單向鏈表隊(duì)列
 *
 * @author 唐學(xué)俊
 * @create 2018/03/11
 **/
public class MyQueue {
    private int size;
    MyLinkedList linkedList = null;
    /**
     * 入隊(duì)
     *
     * @param value
     */
    public void enqueue(int value) {
        if (linkedList == null) {
            linkedList = new MyLinkedList();
        }
        linkedList.add(value);
        size++;
    }
    /**
     * 出隊(duì)
     *
     * @return
     */
    public Object dequeue() {
        Object value = 0;
        if (linkedList != null) {
            //每次彈出隊(duì)列的頭
            value = linkedList.get(0);
            linkedList.removeAt(0);
            size--;
        } else {
            try {
                throw new Exception("隊(duì)列中沒有元素");
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
        return value;
    }
    /**
     * 返回隊(duì)列大小
     *
     * @return
     */
    public int size() {
        return size;
    }
}

基于ArrayList實(shí)現(xiàn)隊(duì)列

package com.tangbaobao.queue;
import java.util.ArrayList;
import java.util.List;
/**
 * 基于List實(shí)現(xiàn)隊(duì)列
 *
 * @author 唐學(xué)俊
 * @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("隊(duì)列中沒有元素");
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
        return value;
    }
    /**
     * 返回隊(duì)列大小
     *
     * @return
     */
    public int size() {
        return size;
    }
}

實(shí)現(xiàn)了比較簡(jiǎn)單的隊(duì)列，尤其調(diào)用了封裝好的數(shù)據(jù)結(jié)構(gòu)，只需知道新的數(shù)據(jù)結(jié)構(gòu)怎么工作，實(shí)現(xiàn)起來比較簡(jiǎn)單。希望能給大家一個(gè)參考，也希望大家多多支持腳本之家

您可能感興趣的文章: