java 數據結構_Java版-數據結構-隊列（數組隊列）

前言

看過筆者前兩篇介紹的 Java版數據結構 數組和 棧的盆友，都給予了筆者一致的好評，在這里筆者感謝大家的認可！！！

由于本章介紹的數據結構是 隊列，在隊列的實現上會基于前面寫的 動態數組來實現，而 隊列又和 棧不論是從特點上和操作上都有類似之處，所以在這里對這兩種數據結構不了解的朋友，可以去看一下筆者前兩篇文章介紹的數據結構 數組和 棧，這里筆者把鏈接貼出來（看過的盆友可以跳過此步驟...）

Java版-數據結構-數組
Java版-數據結構-棧

介紹

隊列是一種特殊的線性表，它只允許在表的前端（front）進行刪除操作，而在表的后端（rear）進行插入操作，和棧一樣，隊列是一種操作受限制的線性表。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。

隊列的操作方式和 棧類似，唯一的區別在于隊列只允許新數據在后端（rear）進行添加。

特點

隊列是一種線性結構
只能從一端（隊尾）添加元素，從另一端（隊首）取出元素
先進先出，First In First Out（FIFO）

之前在介紹棧的時候，通過示意圖來幫助大家了解什么是棧；這里，我仍采用示意圖形式向大家演示隊列常用的兩個操作： 入隊操作和 出隊操作。

隊列入隊操作

這里我們可以形象地想成我們到銀行辦理業務排隊的場景，現在A、B、C三個元素分別到銀行柜臺排成一條隊辦理業務（我們都是文明的孩紙，總不能插隊O(∩_∩)O哈！），依次排隊的元素是：A、B、C。

隊列出隊操作

當元素 A辦理完業務時，當前是元素 A先離開隊列，然后是元素 B，最后是元素 C

我們時刻要牢記隊列，入隊是從 隊尾一端進行入隊，出隊是從 隊首一端進行出隊，是一種：先進先出的數據結構。

本文會介紹隊列的兩張實現方式，一種是數組隊列，另外一種是循環隊列，考慮篇幅長度原因，本篇我們暫時只介紹數組隊列，循環隊列放在下一篇介紹。

數組隊列（底層基于數組實現）

底層原理分析

現在我們聲明一個數組的長度（capacity=3），元素個數為（size=0）的int類型數組的空隊列，在這里，假設對隊列的 隊首為數組的 左側， 隊尾為數組的 右側，示意圖如下:

現在如果我們有四個元素：A、B、C、D要入隊

元素 A入隊

元素 A已經入隊了，現在開始元素 B入隊

元素 A和元素 B已經入隊了，現在開始元素 C入隊

元素 A、 B和 C已經分別入隊了，現在如果我們要開始元素 D入隊，根據我們之前定義的動態數組的特性，如果元素 D進行入隊操作，會發現此時我們的數組已經滿了，這時候數組會自動地 擴容（擴容的原理：新建一個容量是原數組容量兩倍的數組，把原數組中的元素依次拷貝到新的數組中，最后引用指向新的數組）的原來的兩倍（具體擴容多少，盆友可以自行設置）示意圖如下：

到這里我們已經完成了元素:A、B、C、D的入隊操作了，現在我們來看一下，它們的出隊操作，根據隊列的特性，隊列是一種 先進先出的數據結構，之前入隊操作順序依次是： A->B->C->D，那么出隊操作順序仍然是： A->B->C->D

現在我們來看一下元素 A和元素 B出隊后的示意圖：

元素 C和 D的出隊原理和元素 A出隊的原理一樣，直至全部出隊完成，變成空隊列

在元素出隊的過程中，相應地也會進行縮容操作，之前筆者這邊定義，當數組中元素的個數（size）等于數組容量（capacity）的一半時，數組會進行縮容操作，這也正是動態數組的特點。

了解了數組隊列的底層原理之后，接下來我們用代碼來實現一下（建議盆友，在看之前，自己可以嘗試寫一下，然后在看，這樣印象可能會比較深刻O(∩_∩)O哈！）

隊列基本操作

向隊列中添加元素（入隊）

void enqueue(E e);

從隊列中取出元素（出隊）

E dequeue();

獲取隊首元素

E getFront();

獲取隊列中元素個數

int getSize();

判斷隊列是否為空

boolean isEmpty();

代碼實現

接口定義 ：Queue

public interface Queue<E> {/*** 入隊** @param e*/void enqueue(E e);/*** 出隊** @return*/E dequeue();/*** 獲取隊首元素** @return*/E getFront();/*** 獲取隊列中元素的個數** @return*/int getSize();/*** 判斷隊列是否為空** @return*/boolean isEmpty();
}

DynamicArrayQueue 類實現接口 Queue

public class DynamicArrayQueue<E> implements Queue<E> {/*** 用數組存放隊列中元素的個數*/private DynamicArray<E> dynamicArray;/*** 指定容量，初始化隊列** @param capacity*/public DynamicArrayQueue(int capacity) {dynamicArray = new DynamicArray<>(capacity);}/*** 默認容量，初始化隊列*/public DynamicArrayQueue() {dynamicArray = new DynamicArray<>();}@Overridepublic void enqueue(E e) {dynamicArray.addLast(e);}@Overridepublic E dequeue() {return dynamicArray.removeFirst();}@Overridepublic E getFront() {return dynamicArray.getFirst();}@Overridepublic int getSize() {return dynamicArray.getSize();}@Overridepublic boolean isEmpty() {return dynamicArray.isEmpty();}@Overridepublic String toString() {return "DynamicArrayQueue{" +"【隊首】dynamicArray=" + dynamicArray + "}【隊尾】";}
}

測試類： DynamicArrayQueueTest

public class DynamicArrayQueueTest {@Testpublic void testArrayQueue() {// 指定容量（capacity=6）初始化隊列DynamicArrayQueue<String> dynamicArrayQueue = new DynamicArrayQueue(3);System.out.println("初始隊列：" + dynamicArrayQueue);// 準備入隊元素List<String> enQueueElements = Arrays.asList("A", "B", "C");// 元素入隊enQueueElements.forEach(x -> dynamicArrayQueue.enqueue(x));System.out.println("元素A、B、C入隊：" + dynamicArrayQueue);// 此時如果又有一個元素D入隊，會發生擴容操作 （size == capacity）進行擴容dynamicArrayQueue.enqueue("D");System.out.println("元素D入隊，發生擴容：" + dynamicArrayQueue);// 元素A出隊，會發生縮容操作（size == capacity / 2）進行縮容dynamicArrayQueue.dequeue();System.out.println("元素A出隊，發生縮容：" + dynamicArrayQueue);// 元素B出隊dynamicArrayQueue.dequeue();System.out.println("元素B出隊：" + dynamicArrayQueue);}
}

運行結果

初始隊列：DynamicArrayQueue{【隊首】dynamicArray=DynamicArray{data=[null, null, null], size=0,capacity=3}}【隊尾】元素A、B、C入隊：DynamicArrayQueue{【隊首】dynamicArray=DynamicArray{data=[A, B, C], size=3,capacity=3}}【隊尾】元素D入隊，發生擴容：DynamicArrayQueue{【隊首】dynamicArray=DynamicArray{data=[A, B, C, D, null, null], size=4,capacity=6}}【隊尾】元素A出隊，發生縮容：DynamicArrayQueue{【隊首】dynamicArray=DynamicArray{data=[B, C, D], size=3,capacity=3}}【隊尾】元素B出隊：DynamicArrayQueue{【隊首】dynamicArray=DynamicArray{data=[C, D, null], size=2,capacity=3}}【隊尾】

細心的盆友，會發現，因為隊列的底層是數組來實現的，隊列的出隊操作實際上就是：刪除數組中的第一個元素，后面的所有元素都要往前面挪一位；其實這樣性能是比較低下的，時間復雜度是O(n)級別的。
我們想如果元素進行出隊操作后，能否不挪動后面的元素，還能維持隊列的特性，這樣問題不就解決了嗎？盆友可以自行思考一下。

完整版代碼GitHub倉庫地址：Java版數據結構-隊列（數組隊列）歡迎大家【關注】和【Star】

本篇完成的數組隊列是基于之前【Java版-數據結構-數組】動態數組來實現的，下一篇筆者會給大家介紹用循環隊列來解決數組隊列帶來的性能問題。接下來，筆者還會一一的實現其它常見的數組結構。