資料結構：隊列

隊列的定義
隊列的資料存儲結構
- 順序存儲結構
- 鍊式存儲結構
java中的對列
總結

隊列的定義

隊列是隻允許在隊尾進行插入操作，在隊頭進行删除操作、先進先出的線性表。

如圖：

資料結構：隊列隊列的定義隊列的資料存儲結構java中的對列總結

其中A1為隊頭元素，A7為隊尾元素。

隊列的資料存儲結構

順序存儲結構

隊列的順序存儲結構，需要建立數組來實作：

public class ArrayQueue<T> {
    private int defalut_size = 10;//預設大小
    private Object[] mObjects;//目前存放資料的數組
    private int front;//隊頭下标
    private int rear;//隊尾下标

    public ArrayQueue() {
        //初始化對列數組
        mObjects = new Object[defalut_size];
    }

    //入隊
    public void enQueue(T t) {
        //隊尾下标不大于預設長度
        if (rear < defalut_size) {
            mObjects[rear] = t;
            rear++;
        }
    }
    //出隊
    public T deQueue() {
        //隊頭下标不超過隊尾下标
        if (front < rear) {
            T t = (T) mObjects[front];
            mObjects[front] = null;
            front++;
            return t;
        }
        return null;
    }
    //列印隊列狀态
    public void getQueuqData() {
        for (int i = 0; i < mObjects.length; i++) {
            System.out.println("數組下标: " + i + " data: " + mObjects[i]);
        }
    }
}

當調用出隊方法後，會把原來數組front的位置空出來，但假如此時隊尾的下标已到達最大值，再往後入隊的時候，就會導緻數組越界，但隊頭明明還存在一個空位置，這就是“假溢出”現象。如下圖：

資料結構：隊列隊列的定義隊列的資料存儲結構java中的對列總結

要解決假溢出，就用到循環對列。隻要對列尾指針rear達到數組最大時，把隊尾指針指向隊頭，達到頭尾循環。

//入隊
    public void enQueue(T t) {
        //是否對列已滿
        if ((rear + 1) % defalut_size == front) {
            rear = (rear + 1) % defalut_size;
            mObjects[rear] = t;
        }else {
            try {
                throw new Exception("對列已滿");
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
    }

鍊式存儲結構

對列的鍊式存儲結構，其實是線性表的單連結清單，隻不過是限制了隻能尾進頭出。隊頭指針叫做頭結點，隊尾指針叫做尾節點。

資料結構：隊列隊列的定義隊列的資料存儲結構java中的對列總結

java代碼實作如下：

public class LinkQueue<T> {
    private int size;//對列大小
    private Node front;//頭結點
    private Node rear;//尾節點

    private class Node<T> {
        private Node next;
        private T data;

        public Node(T data) {
            this.data = data;
        }
    }

    public LinkQueue() {
    }

    //初始化頭結點等于尾節點
    public LinkQueue(T t) {
        this.front = this.rear = new Node(t);
        size++;
        System.out.println("入隊資料：" + t);
    }

    //入隊
    public void enQueue(T t) {
        //初始化節點
        Node<T> node = new Node<>(t);
        //表示對列為空，則插入的頭結點與尾節點一直
        if (front == null) {
            rear = front = node;
        } else {
            //将尾節點的next指針指向新節點，并把新節點作為新節點。
            rear = rear.next = node;
        }
        System.out.println("入隊資料：" + t);
        size++;
    }

    //出隊
    public Object deQueue() {
        //表示隊列中大于一個節點
        if (front != rear) {
            //将頭結點指派給next；
            Node oldFront = front;
            //把原頭結點的next作為新的頭結點。
            front = oldFront.next;
            //對列大小減一
            size--;
            System.out.println("出隊資料：" + oldFront.data);
            return oldFront.data;//傳回出隊資料
        } else {
            Object data = front.data;
            //如果對列隻有一個節點,直接出隊，把頭結點尾節點賦為空，傳回出隊資料。
            front = rear = null;
            size = 0;
            System.out.println("出隊資料：" + data);
            return data;
        }
    }

    public int getSize() {
        System.out.println("隊列大小：" + size);
        return size;
    }

    public void printQueue() {
        Node<T> mFront = front;
        if (mFront != null) {
            System.out.println("剩下節點：" + mFront.data);
            while (mFront.next != null) {
                mFront = mFront.next;
                System.out.println("剩下節點：" + mFront.data);
            }
        }

    }
}

java中的對列

java中的對列是一個接口Queue

package java.util;

public interface Queue<E> extends Collection<E> {
    boolean add(E var1);

    boolean offer(E var1);

    E remove();

    E poll();

    E element();

    E peek();
}

其中

public abstract class AbstractQueue<E>
    extends AbstractCollection<E>
    implements Queue<E> {

public class PriorityQueue<E> extends AbstractQueue<E>
    implements java.io.Serializable {
    }

具體分析一下PriorityQueue這個類。

入隊

//實作add方法最終也是調用了offer方法
 public boolean add(E e) {
        return offer(e);
    }

//入隊方法
public boolean offer(E e) {
		//如果入隊資料為空，抛空指針異常
        if (e == null)
            throw new NullPointerException();
        //計數器加一
        modCount++;
        int i = size;//擷取目前已經存在的元素數量
        if (i >= queue.length)//當存在的數量大于或者等于存儲的數組長度時，擴容
            grow(i + 1);
        size = i + 1;//實際長度加一
        if (i == 0)//如果列為空，直接放入隊頭位置，否則入隊
            queue[0] = e;
        else
            siftUp(i, e);//這個隊列是一個優先級對列，會通過比較器，把新加入的元素放到合适位置，實作隊列元素的優先級。
        return true;
    }

先看擴容方法grow

private void grow(int minCapacity) {
        int oldCapacity = queue.length;//擷取舊數組長度
        // 如果目前數組長度小于64，則長度擴大為2*oldCapacity +2，
        //否則oldCapacity +oldCapacity/2的長度
        int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                         (oldCapacity + 2) :
                                         (oldCapacity >> 1));
        // 如果新長度大于Integer.MAX_VALUE - 8; 則為Integer.MAX_VALUE 否則為
        //Integer.MAX_VALUE - 8
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
            //擴容copy新數組
        queue = Arrays.copyOf(queue, newCapacity);
    }

出隊

public E poll() {
        if (size == 0)
            return null;
        int s = --size;//大小減一
        modCount++;//計數器加一
        E result = (E) queue[0];//拿隊頭元素
        E x = (E) queue[s];//擷取最後元素
        queue[s] = null;//最後元素賦空
        if (s != 0)
            siftDown(0, x);//利用二叉樹重新移動元素。
        return result;
    }

預設調用siftDownComparable方法利用二叉樹移動元素：

private void siftDownComparable(int k, E x) {
        Comparable<? super E> key = (Comparable<? super E>)x;
       // 擷取數組中間坐标
        int half = n >>> 1;           // loop while a non-leaf
        // k其實是half的父節點下标，若k >= half，則表明k在數組中已經沒有子節點
        while (k < half) {
            // k的左子節點下标
            int child = (k << 1) + 1; // assume left child is least
            // 擷取左子節點的值
            Object c = array[child];
            // 擷取右子節點下标
            int right = child + 1;
            // 選取左右子節點的最小值
            if (right < n &&
                ((Comparable<? super T>) c).compareTo((T) array[right]) > 0)
                c = array[child = right];
            // key <= c說明已經按照升序排序，跳出循環
            if (key.compareTo((T) c) <= 0)
                break;
            // 否則，将子節點的值放在父節點上
            array[k] = c;
            // 将child當作下次比較的k
            k = child;
        }
        queue[k] = key;
    }

可以看到 PriorityBlockingQueue底層使用線性表的順序存儲結構來實作。

總結

對列的操作時間複雜度為常數時間，順序存儲結構要提前申請空間，必要時還需要擴容來防止溢出，同時還要防止假溢出現象。而鍊式存儲結構，每次釋放和申請節點都需要時間開銷，如果在長度固定的情況下，建議用順序存儲結構，如果無法預知對列長度，則需要使用鍊式存儲結構。

下一節資料結構：樹

資料結構：隊列隊列的定義隊列的資料存儲結構java中的對列總結

資料結構：隊列

隊列的定義

隊列的資料存儲結構

順序存儲結構

鍊式存儲結構

java中的對列

總結

繼續閱讀

樹的基本概念(定義、基本術語、性質)

GSL--GNU Scientific Library

D5|哈希表，善用資料結構

如何成為一名.net 工程師?

BMP檔案結構及圖像每行位元組計算方法

D. Ehab the Xorcist(構造+思維)

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器