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

目錄

• 1、隊(duì)列的基本概念
• 2、Java模擬單向隊(duì)列實(shí)現(xiàn)
• 3、雙端隊(duì)列
• 4、優(yōu)先級(jí)隊(duì)列
• 5、總結(jié)

1、隊(duì)列的基本概念

隊(duì)列（queue）是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進(jìn)行刪除操作，而在表的后端（rear）進(jìn)行插入操作，和棧一樣，隊(duì)列是一種操作受限制的線性表。進(jìn)行插入操作的端稱為隊(duì)尾，進(jìn)行刪除操作的端稱為隊(duì)頭。隊(duì)列中沒有元素時(shí)，稱為空隊(duì)列。
隊(duì)列的數(shù)據(jù)元素又稱為隊(duì)列元素。在隊(duì)列中插入一個(gè)隊(duì)列元素稱為入隊(duì)，從隊(duì)列中刪除一個(gè)隊(duì)列元素稱為出隊(duì)。因?yàn)殛?duì)列只允許在一端插入，在另一端刪除，所以只有最早進(jìn)入隊(duì)列的元素才能最先從隊(duì)列中刪除，故隊(duì)列又稱為先進(jìn)先出（FIFO—first in first out）線性表。比如我們?nèi)ル娪霸号抨?duì)買票，第一個(gè)進(jìn)入排隊(duì)序列的都是第一個(gè)買到票離開隊(duì)列的人，而最后進(jìn)入排隊(duì)序列排隊(duì)的都是最后買到票的。在比如在計(jì)算機(jī)操作系統(tǒng)中，有各種隊(duì)列在安靜的工作著，比如打印機(jī)在打印列隊(duì)中等待打印。

隊(duì)列分為：

①、單向隊(duì)列（Queue）：只能在一端插入數(shù)據(jù)，另一端刪除數(shù)據(jù)。

②、雙向隊(duì)列（Deque）：每一端都可以進(jìn)行插入數(shù)據(jù)和刪除數(shù)據(jù)操作。

這里我們還會(huì)介紹一種隊(duì)列——優(yōu)先級(jí)隊(duì)列，優(yōu)先級(jí)隊(duì)列是比棧和隊(duì)列更專用的數(shù)據(jù)結(jié)構(gòu)，在優(yōu)先級(jí)隊(duì)列中，數(shù)據(jù)項(xiàng)按照關(guān)鍵字進(jìn)行排序，關(guān)鍵字最?。ɑ蛘咦畲螅┑臄?shù)據(jù)項(xiàng)往往在隊(duì)列的最前面，而數(shù)據(jù)項(xiàng)在插入的時(shí)候都會(huì)插入到合適的位置以確保隊(duì)列的有序。

2、Java模擬單向隊(duì)列實(shí)現(xiàn)

在實(shí)現(xiàn)之前，我們先看下面幾個(gè)問題：

①、與棧不同的是，隊(duì)列中的數(shù)據(jù)不總是從數(shù)組的0下標(biāo)開始的，移除一些隊(duì)頭front的數(shù)據(jù)后，隊(duì)頭指針會(huì)指向一個(gè)較高的下標(biāo)位置，如下圖：

②、我們?cè)僭O(shè)計(jì)時(shí)，隊(duì)列中新增一個(gè)數(shù)據(jù)時(shí)，隊(duì)尾的指針rear 會(huì)向上移動(dòng)，也就是向下標(biāo)大的方向。移除數(shù)據(jù)項(xiàng)時(shí)，隊(duì)頭指針 front 向上移動(dòng)。那么這樣設(shè)計(jì)好像和現(xiàn)實(shí)情況相反，比如排隊(duì)買電影票，隊(duì)頭的買完票就離開了，然后隊(duì)伍整體向前移動(dòng)。在計(jì)算機(jī)中也可以在隊(duì)列中刪除一個(gè)數(shù)之后，隊(duì)列整體向前移動(dòng)，但是這樣做效率很差。我們選擇的做法是移動(dòng)隊(duì)頭和隊(duì)尾的指針。

③、如果向第②步這樣移動(dòng)指針，相信隊(duì)尾指針很快就移動(dòng)到數(shù)據(jù)的最末端了，這時(shí)候可能移除過數(shù)據(jù)，那么隊(duì)頭會(huì)有空著的位置，然后新來了一個(gè)數(shù)據(jù)項(xiàng)，由于隊(duì)尾不能再向上移動(dòng)了，那該怎么辦呢？如下圖：

為了避免隊(duì)列不滿卻不能插入新的數(shù)據(jù)，我們可以讓隊(duì)尾指針繞回到數(shù)組開始的位置，這也稱為“循環(huán)隊(duì)列”。

弄懂原理之后，Java實(shí)現(xiàn)代碼如下：

package com.ys.datastructure;

public class MyQueue {
    private Object[] queArray;
    //隊(duì)列總大小
    private int maxSize;
    //前端
    private int front;
    //后端
    private int rear;
    //隊(duì)列中元素的實(shí)際數(shù)目
    private int nItems;

    public MyQueue(int s){
        maxSize = s;
        queArray = new Object[maxSize];
        front = 0;
        rear = -1;
        nItems = 0;
    }

    //隊(duì)列中新增數(shù)據(jù)
    public void insert(int value){
        if(isFull()){
            System.out.println("隊(duì)列已滿?。?！");
        }else{
            //如果隊(duì)列尾部指向頂了，那么循環(huán)回來，執(zhí)行隊(duì)列的第一個(gè)元素
            if(rear == maxSize -1){
                rear = -1;
            }
            //隊(duì)尾指針加1，然后在隊(duì)尾指針處插入新的數(shù)據(jù)
            queArray[++rear] = value;
            nItems++;
        }
    }

    //移除數(shù)據(jù)
    public Object remove(){
        Object removeValue = null ;
        if(!isEmpty()){
            removeValue = queArray[front];
            queArray[front] = null;
            front++;
            if(front == maxSize){
                front = 0;
            }
            nItems--;
            return removeValue;
        }
        return removeValue;
    }

    //查看對(duì)頭數(shù)據(jù)
    public Object peekFront(){
        return queArray[front];
    }

    //判斷隊(duì)列是否滿了
    public boolean isFull(){
        return (nItems == maxSize);
    }

    //判斷隊(duì)列是否為空
    public boolean isEmpty(){
        return (nItems ==0);
    }

    //返回隊(duì)列的大小
    public int getSize(){
        return nItems;
    }    
}

測(cè)試：

package com.ys.test;

import com.ys.datastructure.MyQueue;

public class MyQueueTest {
    public static void main(String[] args) {
        MyQueue queue = new MyQueue(3);
        queue.insert(1);
        queue.insert(2);
        queue.insert(3);//queArray數(shù)組數(shù)據(jù)為[1,2,3]

        System.out.println(queue.peekFront()); //1
        queue.remove();//queArray數(shù)組數(shù)據(jù)為[null,2,3]
        System.out.println(queue.peekFront()); //2

        queue.insert(4);//queArray數(shù)組數(shù)據(jù)為[4,2,3]
        queue.insert(5);//隊(duì)列已滿,queArray數(shù)組數(shù)據(jù)為[4,2,3]
    }
}

3、雙端隊(duì)列

雙端隊(duì)列就是一個(gè)兩端都是結(jié)尾或者開頭的隊(duì)列，?隊(duì)列的每一端都可以進(jìn)行插入數(shù)據(jù)項(xiàng)和移除數(shù)據(jù)項(xiàng)，這些方法可以叫做：

insertRight()、insertLeft()、removeLeft()、removeRight()

如果嚴(yán)格禁止調(diào)用insertLeft()和removeLeft()（或禁用右端操作），那么雙端隊(duì)列的功能就和前面講的棧功能一樣。如果嚴(yán)格禁止調(diào)用insertLeft()和removeRight(或相反的另一對(duì)方法)，那么雙端隊(duì)列的功能就和單向隊(duì)列一樣了。

4、優(yōu)先級(jí)隊(duì)列

優(yōu)先級(jí)隊(duì)列（priority queue）是比棧和隊(duì)列更專用的數(shù)據(jù)結(jié)構(gòu)，在優(yōu)先級(jí)隊(duì)列中，數(shù)據(jù)項(xiàng)按照關(guān)鍵字進(jìn)行排序，關(guān)鍵字最?。ɑ蛘咦畲螅┑臄?shù)據(jù)項(xiàng)往往在隊(duì)列的最前面，而數(shù)據(jù)項(xiàng)在插入的時(shí)候都會(huì)插入到合適的位置以確保隊(duì)列的有序。

優(yōu)先級(jí)隊(duì)列 是0個(gè)或多個(gè)元素的集合，每個(gè)元素都有一個(gè)優(yōu)先權(quán)，對(duì)優(yōu)先級(jí)隊(duì)列執(zhí)行的操作有：

（1）查找
（2）插入一個(gè)新元素
（3）刪除

一般情況下，查找操作用來搜索優(yōu)先權(quán)最大的元素，刪除操作用來刪除該元素 。對(duì)于優(yōu)先權(quán)相同的元素，可按先進(jìn)先出次序處理或按任意優(yōu)先權(quán)進(jìn)行。這里我們用數(shù)組實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列，這種方法插入比較慢，但是它比較簡(jiǎn)單，適用于數(shù)據(jù)量比較小并且不是特別注重插入速度的情況。后面我們會(huì)講解堆，用堆的數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列，可以相當(dāng)快的插入數(shù)據(jù)。數(shù)組實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列，聲明為int類型的數(shù)組，關(guān)鍵字是數(shù)組里面的元素，在插入的時(shí)候按照從大到小的順序排列，也就是越小的元素優(yōu)先級(jí)越高。

package com.ys.datastructure;

public class PriorityQue {
    private int maxSize;
    private int[] priQueArray;
    private int nItems;

    public PriorityQue(int s){
        maxSize = s;
        priQueArray = new int[maxSize];
        nItems = 0;
    }

    //插入數(shù)據(jù)
    public void insert(int value){
        int j;
        if(nItems == 0){
            priQueArray[nItems++] = value;
        }else{
            j = nItems -1;
            //選擇的排序方法是插入排序，按照從大到小的順序排列，越小的越在隊(duì)列的頂端
            while(j >=0 && value > priQueArray[j]){
                priQueArray[j+1] = priQueArray[j];
                j--;
            }
            priQueArray[j+1] = value;
            nItems++;
        }
    }

    //移除數(shù)據(jù),由于是按照大小排序的，所以移除數(shù)據(jù)我們指針向下移動(dòng)
    //被移除的地方由于是int類型的，不能設(shè)置為null，這里的做法是設(shè)置為 -1
    public int remove(){
        int k = nItems -1;
        int value = priQueArray[k];
        priQueArray[k] = -1;//-1表示這個(gè)位置的數(shù)據(jù)被移除了
        nItems--;
        return value;
    }

    //查看優(yōu)先級(jí)最高的元素
    public int peekMin(){
        return priQueArray[nItems-1];
    }

    //判斷是否為空
    public boolean isEmpty(){
        return (nItems == 0);
    }

    //判斷是否滿了
    public boolean isFull(){
        return (nItems == maxSize);
    }
}

insert() 方法，先檢查隊(duì)列中是否有數(shù)據(jù)項(xiàng)，如果沒有，則直接插入到下標(biāo)為0的單元里，否則，從數(shù)組頂部開始比較，找到比插入值小的位置進(jìn)行插入，并把 nItems 加1.

remove()?方法直接獲取頂部元素。

優(yōu)先級(jí)隊(duì)列的插入操作需要 O(N)的時(shí)間，而刪除操作則需要O(1) 的時(shí)間，后面會(huì)講解如何通過 堆 來改進(jìn)插入時(shí)間。

5、總結(jié)

本篇文章我們介紹了隊(duì)列的三種形式，分別是單向隊(duì)列、雙向隊(duì)列以及優(yōu)先級(jí)隊(duì)列。其實(shí)大家聽名字也可以聽得出來他們之間的區(qū)別，單向隊(duì)列遵循先進(jìn)先出的原則，而且一端只能插入，另一端只能刪除。雙向隊(duì)列則兩端都可插入和刪除，如果限制雙向隊(duì)列的某一段的方法，則可以達(dá)到和單向隊(duì)列同樣的功能。最后優(yōu)先級(jí)隊(duì)列，則是在插入元素的時(shí)候進(jìn)行了優(yōu)先級(jí)別排序，在實(shí)際應(yīng)用中單項(xiàng)隊(duì)列和優(yōu)先級(jí)隊(duì)列使用的比較多。后面講解了堆這種數(shù)據(jù)結(jié)構(gòu)，我們會(huì)用堆來實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列，改善優(yōu)先級(jí)隊(duì)列插入元素的時(shí)間。

通過前面講的棧以及本篇講的隊(duì)列這兩種數(shù)據(jù)結(jié)構(gòu)，我們稍微總結(jié)一下：

①、棧、隊(duì)列（單向隊(duì)列）、優(yōu)先級(jí)隊(duì)列通常是用來簡(jiǎn)化某些程序操作的數(shù)據(jù)結(jié)構(gòu)，而不是主要作為存儲(chǔ)數(shù)據(jù)的。

②、在這些數(shù)據(jù)結(jié)構(gòu)中，只有一個(gè)數(shù)據(jù)項(xiàng)可以被訪問。

③、棧允許在棧頂壓入（插入）數(shù)據(jù)，在棧頂彈出（移除）數(shù)據(jù)，但是只能訪問最后一個(gè)插入的數(shù)據(jù)項(xiàng)，也就是棧頂元素。

④、隊(duì)列（單向隊(duì)列）只能在隊(duì)尾插入數(shù)據(jù)，對(duì)頭刪除數(shù)據(jù)，并且只能訪問對(duì)頭的數(shù)據(jù)。而且隊(duì)列還可以實(shí)現(xiàn)循環(huán)隊(duì)列，它基于數(shù)組，數(shù)組下標(biāo)可以從數(shù)組末端繞回到數(shù)組的開始位置。

⑤、優(yōu)先級(jí)隊(duì)列是有序的插入數(shù)據(jù)，并且只能訪問當(dāng)前元素中優(yōu)先級(jí)別最大（或最?。┑脑?。

⑥、這些數(shù)據(jù)結(jié)構(gòu)都能由數(shù)組實(shí)現(xiàn)，但是可以用別的機(jī)制（后面講的鏈表、堆等數(shù)據(jù)結(jié)構(gòu)）實(shí)現(xiàn)。