『數(shù)據(jù)結(jié)構(gòu)與算法』—— 隊(duì)列

定義

有一定的業(yè)務(wù)需求就會(huì)有對(duì)應(yīng)的技術(shù)或數(shù)據(jù)結(jié)構(gòu)產(chǎn)生。我們都知道 CPU 的資源是有限的，任務(wù)的處理速度與線程個(gè)數(shù)并不是線性正相關(guān)。相反過(guò)多的線程反而會(huì)導(dǎo)致 CPU 頻繁切換，處理性能下降。所以線程池的大小一般都是綜合考慮處理任務(wù)的特點(diǎn)和硬件環(huán)境，來(lái)事先設(shè)置的。

隊(duì)列的特點(diǎn) 先進(jìn)先出，可以想象成排隊(duì)買(mǎi)票，先來(lái)的先買(mǎi)。最基本的操作就是 入隊(duì)和出隊(duì)，所以隊(duì)列跟棧一樣，也是一種 操作受限的線性數(shù)據(jù)結(jié)構(gòu)。

實(shí)現(xiàn)

類似棧，可以通過(guò)數(shù)組和鏈表試下，數(shù)組實(shí)現(xiàn)的隊(duì)列叫做 順序隊(duì)列，鏈表實(shí)現(xiàn)的隊(duì)列叫做 鏈?zhǔn)疥?duì)列。

順序隊(duì)列

核心思想在于，使用兩個(gè)下標(biāo)保存頭部和尾部的數(shù)據(jù)，也可以當(dāng)成標(biāo)識(shí)。因?yàn)槿腙?duì)是從屁股進(jìn)行插入，出隊(duì)是從頭部拿出數(shù)據(jù)，因此要記住頭尾的位置。

先來(lái)看一下簡(jiǎn)單的實(shí)現(xiàn)方式：

class ArrayQueue<T> {
    T[] items;
    int head;
    int tail;
    int count;

    ArrayQueue(int capacity) {
        items = (T[]) new Object[capacity];
        count = capacity;
    }

    boolean enqueue(T t) {
        if (tail == count) return false;
        items[tail] = t;
        tail ++;
        print("enqueue");
        return true;
    }

    T dequeue() {
        if (head == tail) return null;
        T t= items[head];
        items[head] = null;
        head ++;
        print("dequeue");
        return t;
    }

    void print(String mode) {
        System.out.println("mode:\t" + mode + " head:\t" + head + " tail:\t" + tail);
        for (int i = head; i < tail; i++) {
            System.out.print(items[i] + "");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        ArrayQueue<String> queue = new ArrayQueue<String>(6);
        queue.enqueue("1");
        queue.enqueue("2");
        queue.enqueue("3");
        queue.dequeue();
        queue.dequeue();
        queue.dequeue();
        queue.enqueue("5");
        queue.enqueue("6");
    }
}

運(yùn)行結(jié)果：

mode:   enqueue head:   0 tail: 1
1
mode:   enqueue head:   0 tail: 2
12
mode:   enqueue head:   0 tail: 3
123
mode:   dequeue head:   1 tail: 3
23
mode:   dequeue head:   2 tail: 3
3
mode:   dequeue head:   3 tail: 3

mode:   enqueue head:   3 tail: 4
5
mode:   enqueue head:   3 tail: 5
56

上述實(shí)現(xiàn)的方式有一個(gè)弊端，當(dāng) tail == n 的時(shí)候，就不能繼續(xù)插入數(shù)據(jù)，但是此時(shí)容器并沒(méi)有裝滿，只是不能繼續(xù)往后插入數(shù)據(jù)了。那這個(gè)時(shí)候就需要對(duì)容器進(jìn)行改變：數(shù)據(jù)搬移。單并不是每次入隊(duì)都需要遷移，為了優(yōu)化時(shí)間復(fù)雜度，可以在每次尾節(jié)點(diǎn)到達(dá)終點(diǎn)時(shí)，再開(kāi)始數(shù)據(jù)搬移，即數(shù)據(jù)往前移動(dòng) head 的位置。

來(lái)看一下實(shí)現(xiàn)方式：

class DynamicArrayQueue<T> {
    T[] items;
    int head;
    int tail;
    int count;

    DynamicArrayQueue(int capacity) {
        items = (T[]) new Object[capacity];
        count = capacity;
    }

    boolean enqueue(T t) {
        if (tail == count) {
            if (head == 0) return false;
            for (int i = head; i < tail; i++) {
                items[i - head] = items[i];
            }
            tail -= head;
            head = 0;
        }
        items[tail] = t;
        tail ++;
        print("enqueue");
        return true;
    }

    T dequeue() {
        if (head == tail) return null;
        T t = items[head];
        items[head] = null;
        head ++;
        print("new dequeue");
        return t;
    }

    void print(String mode) {
        System.out.println("mode:\t" + mode + " head:\t" + head + " tail:\t" + tail);
        for (int i = head; i < tail; i++) {
            System.out.print(items[i] + "");
        }
        System.out.println();
        System.out.println(Arrays.toString(items));
    }

    public static void main(String[] args) {
        DynamicArrayQueue<String> queue = new DynamicArrayQueue<String>(4);
        queue.enqueue("1");
        queue.enqueue("2");
        queue.enqueue("3");
        queue.enqueue("4");
        queue.dequeue();
        queue.dequeue();
        queue.enqueue("5");
        queue.enqueue("6");
    }
}

結(jié)果：

mode:   enqueue head:   0 tail: 1
1
[1, null, null, null]
mode:   enqueue head:   0 tail: 2
12
[1, 2, null, null]
mode:   enqueue head:   0 tail: 3
123
[1, 2, 3, null]
mode:   enqueue head:   0 tail: 4
1234
[1, 2, 3, 4]
mode:   new dequeue head:   1 tail: 4
234
[null, 2, 3, 4]
mode:   new dequeue head:   2 tail: 4
34
[null, null, 3, 4]
mode:   enqueue head:   0 tail: 3
345
[3, 4, 5, 4]
mode:   enqueue head:   0 tail: 4
3456
[3, 4, 5, 6]
mode:   new dequeue head:   1 tail: 4
456
[null, 4, 5, 6]
mode:   enqueue head:   0 tail: 4
4567
[4, 5, 6, 7]

想比較之前的實(shí)現(xiàn)，出隊(duì)的邏輯并沒(méi)有任何的改變，在入隊(duì)是，需要判斷 tail == 0，如果達(dá)到這個(gè)條件則可能需要進(jìn)行數(shù)據(jù)搬移。

鏈?zhǔn)疥?duì)列

思路其實(shí)類似于順序隊(duì)列的實(shí)現(xiàn)邏輯。

class LinkedQueue<T> {
    Node<T> head = null;
    Node<T> tail = null;

    void enqueue(T t) {
        if (tail == null) {
            Node<T> node = new Node<T>(t, null);
            head = node;
            tail = node;
        } else {
            tail.next = new Node<T>(t, null);
            tail = tail.next;
        }
        System.out.println(head.toString());
    }

    T dequeue() {
        if (head == null) return null;
        T t = head.value;
        head = head.next;
        if (head == null) {
            tail = null;
        }
        System.out.println(head == null ? "null" : head.toString());
        return t;
    }

    public static void main(String[] args) {
        LinkedQueue<String> queue = new LinkedQueue<String>();
        queue.enqueue("1");
        queue.enqueue("2");
        queue.enqueue("3");
        queue.dequeue();
        queue.dequeue();
        queue.enqueue("6");
    }
}

運(yùn)行結(jié)果：

1 
1 2 
1 2 3 
2 3 
3 
3 6

需要注意的是：

  1. 入隊(duì)的時(shí)候，需要考慮隊(duì)列無(wú)數(shù)據(jù)的情況
  2. 出隊(duì)的時(shí)候，需要考慮出隊(duì)到最后尾節(jié)點(diǎn)的處理

循環(huán)隊(duì)列

之前在用數(shù)組實(shí)現(xiàn)隊(duì)列時(shí)，在 tail == n 時(shí)會(huì)有數(shù)據(jù)搬移的操作，這樣入隊(duì)操作性能就會(huì)收到影響，我們可以使用循環(huán)隊(duì)列來(lái)解決這個(gè)問(wèn)題。

循環(huán)隊(duì)列其實(shí)長(zhǎng)得像一個(gè)環(huán)，現(xiàn)在需要將首尾相連變成一個(gè)環(huán)。

放三張圖感受一下，圖片來(lái)自于極客時(shí)間的課程。

image
image
image

從圖中可以發(fā)現(xiàn)規(guī)律，當(dāng) (tail + 1) % n = head 時(shí)，說(shuō)明隊(duì)列已滿。

來(lái)看一下代碼的具體實(shí)現(xiàn)方式：

class CircularQueue {
    // 數(shù)組：items，數(shù)組大?。簄
    private String[] items;
    private int n = 0;
    // head表示隊(duì)頭下標(biāo)，tail表示隊(duì)尾下標(biāo)
    private int head = 0;
    private int tail = 0;

    // 申請(qǐng)一個(gè)大小為capacity的數(shù)組
    public CircularQueue(int capacity) {
        items = new String[capacity + 1];
        n = capacity + 1;
    }

    // 入隊(duì)
    public boolean enqueue(String item) {
        // 隊(duì)列滿了
        if ((tail + 1) % n == head) return false;
        items[tail] = item;
        tail = (tail + 1) % n;
        return true;
    }

    // 出隊(duì)
    public String dequeue() {
        // 如果head == tail 表示隊(duì)列為空
        if (head == tail) return null;
        String ret = items[head];
        head = (head + 1) % n;
        return ret;
    }

    public void printAll() {
        if (0 == n) return;
        for (int i = head; i % n != tail; ++i) {
            System.out.print(items[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        CircularQueue queue = new CircularQueue(5);
        queue.enqueue("1");
        queue.enqueue("2");
        queue.enqueue("3");
        queue.enqueue("4");
        queue.printAll();
        queue.dequeue();
        queue.printAll();
        queue.enqueue("5");
        queue.enqueue("6");
        queue.printAll();
    }
}

運(yùn)行結(jié)果：

1 2 3 4 
2 3 4 
2 3 4 5 6

參考自極客時(shí)間

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容