Java數(shù)據(jù)結(jié)構(gòu)——隊(duì)列

2.4 隊(duì)列

概述

計(jì)算機(jī)科學(xué)中，queue 是以順序的方式維護(hù)的一組數(shù)據(jù)集合，在一端添加數(shù)據(jù)，從另一端移除數(shù)據(jù)。習(xí)慣來說，添加的一端稱為尾，移除的一端稱為頭，就如同生活中的排隊(duì)買商品

In computer science, a queue is a collection of entities that are maintained in a sequence and can be modified by the addition of entities at one end of the sequence and the removal of entities from the other end of the sequence

先定義一個(gè)簡化的隊(duì)列接口

public interface Queue<E> {

    /**
     * 向隊(duì)列尾插入值
     * @param value 待插入值
     * @return 插入成功返回 true, 插入失敗返回 false
     */
    boolean offer(E value);

    /**
     * 從對(duì)列頭獲取值, 并移除
     * @return 如果隊(duì)列非空返回對(duì)頭值, 否則返回 null
     */
    E poll();

    /**
     * 從對(duì)列頭獲取值, 不移除
     * @return 如果隊(duì)列非空返回對(duì)頭值, 否則返回 null
     */
    E peek();

    /**
     * 檢查隊(duì)列是否為空
     * @return 空返回 true, 否則返回 false
     */
    boolean isEmpty();

    /**
     * 檢查隊(duì)列是否已滿
     * @return 滿返回 true, 否則返回 false
     */
    boolean isFull();
}

鏈表實(shí)現(xiàn)

下面以單向環(huán)形帶哨兵鏈表方式來實(shí)現(xiàn)隊(duì)列

image.png
image.png
image.png

代碼

public class LinkedListQueue<E>
        implements Queue<E>, Iterable<E> {

    private static class Node<E> {
        E value;
        Node<E> next;

        public Node(E value, Node<E> next) {
            this.value = value;
            this.next = next;
        }
    }

    private Node<E> head = new Node<>(null, null);
    private Node<E> tail = head;
    private int size = 0;
    private int capacity = Integer.MAX_VALUE;

    {
        tail.next = head;
    }

    public LinkedListQueue() {
    }

    public LinkedListQueue(int capacity) {
        this.capacity = capacity;
    }

    @Override
    public boolean offer(E value) {
        if (isFull()) {
            return false;
        }
        Node<E> added = new Node<>(value, head);
        tail.next = added;
        tail = added;
        size++;
        return true;
    }

    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        Node<E> first = head.next;
        head.next = first.next;
        if (first == tail) {
            tail = head;
        }
        size--;
        return first.value;
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return head.next.value;
    }

    @Override
    public boolean isEmpty() {
        return head == tail;
    }

    @Override
    public boolean isFull() {
        return size == capacity;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            Node<E> p = head.next;
            @Override
            public boolean hasNext() {
                return p != head;
            }
            @Override
            public E next() {
                E value = p.value;
                p = p.next;
                return value;
            }
        };
    }
}

環(huán)形數(shù)組實(shí)現(xiàn)

好處

  1. 對(duì)比普通數(shù)組，起點(diǎn)和終點(diǎn)更為自由，不用考慮數(shù)據(jù)移動(dòng)
  2. “環(huán)”意味著不會(huì)存在【越界】問題
  3. 數(shù)組性能更佳
  4. 環(huán)形數(shù)組比較適合實(shí)現(xiàn)有界隊(duì)列、RingBuffer 等
image.png

下標(biāo)計(jì)算

例如，數(shù)組長度是 5，當(dāng)前位置是 3 ，向前走 2 步，此時(shí)下標(biāo)為 (3 + 2)\%5 = 0

image.png

(cur + step) \% length

  • cur 當(dāng)前指針位置
  • step 前進(jìn)步數(shù)
  • length 數(shù)組長度

注意：

  • 如果 step = 1，也就是一次走一步，可以在 >= length 時(shí)重置為 0 即可

判斷空

image.png

判斷滿

image.png

滿之后的策略可以根據(jù)業(yè)務(wù)需求決定

  • 例如我們要實(shí)現(xiàn)的環(huán)形隊(duì)列，滿之后就拒絕入隊(duì)

代碼

public class ArrayQueue<E> implements Queue<E>, Iterable<E>{

    private int head = 0;
    private int tail = 0;
    private final E[] array;
    private final int length;

    @SuppressWarnings("all")
    public ArrayQueue(int capacity) {
        length = capacity + 1;
        array = (E[]) new Object[length];
    }

    @Override
    public boolean offer(E value) {
        if (isFull()) {
            return false;
        }
        array[tail] = value;
        tail = (tail + 1) % length;
        return true;
    }

    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        E value = array[head];
        head = (head + 1) % length;
        return value;
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return array[head];
    }

    @Override
    public boolean isEmpty() {
        return tail == head;
    }

    @Override
    public boolean isFull() {
        return (tail + 1) % length == head;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            int p = head;
            @Override
            public boolean hasNext() {
                return p != tail;
            }

            @Override
            public E next() {
                E value = array[p];
                p = (p + 1) % array.length;
                return value;
            }
        };
    }
}

判斷空、滿方法2

引入 size

public class ArrayQueue2<E> implements Queue<E>, Iterable<E> {

    private int head = 0;
    private int tail = 0;
    private final E[] array;
    private final int capacity;
    private int size = 0;

    @SuppressWarnings("all")
    public ArrayQueue2(int capacity) {
        this.capacity = capacity;
        array = (E[]) new Object[capacity];
    }

    @Override
    public boolean offer(E value) {
        if (isFull()) {
            return false;
        }
        array[tail] = value;
        tail = (tail + 1) % capacity;
        size++;
        return true;
    }

    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        E value = array[head];
        head = (head + 1) % capacity;
        size--;
        return value;
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return array[head];
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return size == capacity;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            int p = head;

            @Override
            public boolean hasNext() {
                return p != tail;
            }

            @Override
            public E next() {
                E value = array[p];
                p = (p + 1) % capacity;
                return value;
            }
        };
    }
}

判斷空、滿方法3

  • head 和 tail 不斷遞增，用到索引時(shí)，再用它們進(jìn)行計(jì)算，兩個(gè)問題

    • 如何保證 head 和 tail 自增超過正整數(shù)最大值的正確性

    • 如何讓取模運(yùn)算性能更高

  • 答案：讓 capacity 為 2 的冪

public class ArrayQueue3<E> implements Queue<E>, Iterable<E> {

    private int head = 0;
    private int tail = 0;
    private final E[] array;
    private final int capacity;

    @SuppressWarnings("all")
    public ArrayQueue3(int capacity) {
        if ((capacity & capacity - 1) != 0) {
            throw new IllegalArgumentException("capacity 必須為 2 的冪");
        }
        this.capacity = capacity;
        array = (E[]) new Object[this.capacity];
    }

    @Override
    public boolean offer(E value) {
        if (isFull()) {
            return false;
        }
        array[tail & capacity - 1] = value;
        tail++;
        return true;
    }

    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        E value = array[head & capacity - 1];
        head++;
        return value;
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return array[head & capacity - 1];
    }

    @Override
    public boolean isEmpty() {
        return tail - head == 0;
    }

    @Override
    public boolean isFull() {
        return tail - head == capacity;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            int p = head;

            @Override
            public boolean hasNext() {
                return p != tail;
            }

            @Override
            public E next() {
                E value = array[p & capacity - 1];
                p++;
                return value;
            }
        };
    }
}
?著作權(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)，簡書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

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

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