數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)之——隊(duì)列與循環(huán)隊(duì)列

• 什么是隊(duì)列(Queue)
• 隊(duì)列基于動(dòng)態(tài)數(shù)組的實(shí)現(xiàn)及時(shí)間復(fù)雜度分析
• 優(yōu)化隊(duì)列
• 循環(huán)隊(duì)列(LoopQueue)

什么是隊(duì)列(Queue)

隊(duì)列(Queue)同棧(stack)一樣也是一種運(yùn)算收限的線(xiàn)性數(shù)據(jù)結(jié)構(gòu)，參考：數(shù)據(jù)結(jié)構(gòu)之——棧。棧即：LIFO(Last In First Out),隊(duì)列則是FIFO(First In First Out)，也就是說(shuō)隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)僅允許在一端(隊(duì)尾)添加元素，在另一端(隊(duì)首)刪除元素，所以說(shuō)隊(duì)列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)。可以將隊(duì)列想象成銀行柜臺(tái)的排隊(duì)機(jī)制一樣，在前面排隊(duì)的人可以先辦理業(yè)務(wù)，在最后排隊(duì)的人等到前面所有的人辦理完畢后，才可以進(jìn)行業(yè)務(wù)的處理，如圖：

隊(duì)列基于動(dòng)態(tài)數(shù)組的實(shí)現(xiàn)及時(shí)間復(fù)雜度分析

隊(duì)列同ArrayStack的實(shí)現(xiàn)一樣，都需要基于動(dòng)態(tài)數(shù)組作為底層實(shí)現(xiàn)。
動(dòng)態(tài)數(shù)組實(shí)現(xiàn)代碼,動(dòng)態(tài)數(shù)組實(shí)現(xiàn)原理
在設(shè)計(jì)模式上，同ArrayStack一樣，設(shè)計(jì)的是Queue這樣一個(gè)接口，并創(chuàng)建ArrayQueue這樣一個(gè)類(lèi)implements這個(gè)接口，Queue接口的方法與Stack棧的方法大體相同，只不過(guò)我們將入棧push設(shè)計(jì)成enqueue(入隊(duì))，出棧pop設(shè)計(jì)為dequeue(出隊(duì))。接口代碼如下：

public interface Queue<E>{void enqueue(E e);E dequeue();E getFront();int getSize();boolean is Empty(); } 復(fù)制代碼

ArrayQueue代碼如下：

public class ArrayQueue<E> implements Queue<E>{private Array<E> array;public ArrayQueue(int capacity){array = new Array<>(capacity);}public ArrayQueue(){array = new Array<>();}@Overridepublic int getSize(){return array.getSize();}@Overridepublic boolean isEmpty(){return array.isEmpty();}public int getCapacity(){return array.getCapacity();}@Overridepublic void enqueue(E e){array.addLast(e);}@Overridepublic E dequeue(){return array.removeFirst();}@Overridepublic E getFront(){if(array.isEmpty)throw new IllegalArgumentException("ArrayQueue is Empty");return array.get(0)}@Overridepublic String toString(){StringBuilder sb = new StringBuilder();sb.append("Queue:\n");sb.append("front:[");for(int i=0;i<getSize();i++){sb.append(array.get(i));if(i!=getSize()-1){sb.append(",");}else{sb.append("]tail");}}return sb.toString();} } 復(fù)制代碼

時(shí)間復(fù)雜度分析如下：

E getFront();int getSize();boolean is Empty(); 復(fù)制代碼

以上方法，時(shí)間復(fù)雜度為：O(1)。

void enqueue(E e); 復(fù)制代碼

因?yàn)槿腙?duì)操作相當(dāng)于在動(dòng)態(tài)數(shù)組的尾部添加元素，雖然有resize()這樣一個(gè)O(n)級(jí)別的算法，但是以均攤時(shí)間復(fù)雜度分析，enqueue操作仍然是一個(gè)O(1)級(jí)別的算法。

E dequeue(); 復(fù)制代碼

dequeue()操作相當(dāng)于動(dòng)態(tài)數(shù)組的removeFirst()操作，在數(shù)組的頭部刪除一個(gè)元素，array[0] 后面的所有元素都需要向前挪動(dòng)一個(gè)位置，所以dequeue出隊(duì)是一個(gè)O(n)級(jí)別的算法。
綜上分析，ArrayQueue還是有些不完美的地方，ArrayStack所有的操作均為O(1)級(jí)別的算法，但是基于動(dòng)態(tài)數(shù)組實(shí)現(xiàn)的隊(duì)列ArrayQueue 在出隊(duì)操作dequeue上性能還是略顯不足，LoopQueue(循環(huán)隊(duì)列)就優(yōu)化了ArrayQueue出隊(duì)這樣一個(gè)問(wèn)題。

優(yōu)化ArrayQueue

我們已經(jīng)知道了，ArrayQueue美中不足的地方就在于dequeue這樣一個(gè)操作是O(n)級(jí)別的算法。出現(xiàn)這個(gè)問(wèn)題的原因?qū)嶋H上是因?yàn)槊看芜M(jìn)行出隊(duì)操作時(shí)，動(dòng)態(tài)數(shù)組都需要將array[0]后面所有的元素向前挪動(dòng)一個(gè)單位，但實(shí)際上想一想這個(gè)過(guò)程并不“劃算”，因?yàn)?#xff0c;隊(duì)列元素的數(shù)量達(dá)到萬(wàn)以上的級(jí)別時(shí)，僅僅刪除一個(gè)元素，我們就需要將所有的元素進(jìn)行一次大換血。和銀行柜臺(tái)業(yè)務(wù)辦理的排隊(duì)不同，銀行柜臺(tái)的一號(hào)辦理人辦理完畢，后面所有的人只需要上前一小步就可以了，但是對(duì)于計(jì)算機(jī)來(lái)講，每一個(gè)數(shù)據(jù)的調(diào)整都需要計(jì)算機(jī)親歷躬行。有什么辦法可以避免這種大規(guī)模的動(dòng)輒呢？我們可以使用兩個(gè)變量去維護(hù)隊(duì)列的隊(duì)首和隊(duì)尾。

假設(shè)變量為front和tail。front維護(hù)隊(duì)首，變量tail維護(hù)隊(duì)尾，當(dāng)front==tail時(shí)，隊(duì)列為空，每增加一個(gè)元素，tail就像后移動(dòng)一個(gè)單位，所以我們需要多使用一個(gè)空間去維護(hù) tail這樣一個(gè)變量，這樣我們?cè)谠O(shè)計(jì)模式上就需要開(kāi)辟用戶(hù)指定的capacity加1的數(shù)組空間。對(duì)于用戶(hù)來(lái)講，capacity==n,但實(shí)際上真正的capacity也就是data.length==n+1,因?yàn)槲覀冃枰嗬速M(fèi)一個(gè)空間去維護(hù)tail這個(gè)變量，但是浪費(fèi)這樣一個(gè)空間相比于dequeue的大換血O(n)操作也是值得的。
示例：enqueue元素“D”

示例：dequeue

上述思路優(yōu)化后的隊(duì)列MyQueue代碼如下：

public class MyQueue<E> implements Queue<E> {private int front;private int tail;private E[]data;public MyQueue(int capacity){data = (E[])new Object[capacity+1];}public MyQueue(){this(10);}@Overridepublic int getSize(){return tail-front;}@Overridepublic boolean isEmpty(){return front==tail;}@Overridepublic E getFront(){return data[front];}private void resize(int newCapacity){E[]newData = (E[])new Object[newCapacity+1];for(int i=0;i<(tail-front);i++){newData[i] = data[front+i];}data = newData;tail = tail - front;front = 0;}@Overridepublic void enqueue(E e){if(tail == data.length-1)resize((tail-front)*2);data[tail] = e;tail++;}@Overridepublic E dequeue(){E ret = data[front];// Loitering Objectdata[front] = null;front++;if(((tail-front)==(data.length-1)/4) && (data.length-1)/2!=0)resize((data.length-1)/2);return ret;}@Overridepublic String toString(){StringBuilder stringBuilder = new StringBuilder();stringBuilder.append(String.format("MyQueue size=%d,capacity=%d\n",tail-front,data.length-1));stringBuilder.append("front:[");for(int i=front;i<tail;i++){stringBuilder.append(data[i]);if((i+1)!=tail){stringBuilder.append(",");}}stringBuilder.append("]tail");return stringBuilder.toString();} }復(fù)制代碼

MyQueue對(duì)ArrayQueue進(jìn)行了優(yōu)化操作，原本dequeue需要O(n)的時(shí)間復(fù)雜度，進(jìn)行優(yōu)化后，dequeue由O(n)的時(shí)間復(fù)雜度變?yōu)榱司鶖侽(1)的時(shí)間復(fù)雜度。這里面需要注意的是：MyQueue的enqueue入隊(duì)操作規(guī)定了tail == data.length-1時(shí)進(jìn)行“擴(kuò)容”操作，這里面擴(kuò)容二字我使用了雙引號(hào)，因?yàn)橛锌赡苓@個(gè)“擴(kuò)容”實(shí)際上是縮容。

我們規(guī)定了enqueue操作中，

if(tail == data.length-1)resize((tail-front)*2); 復(fù)制代碼

在上圖的示例中，如果reisze，我們實(shí)際上就相當(dāng)于進(jìn)行了縮容的操作。我們這樣的設(shè)計(jì)看起來(lái)解決了問(wèn)題，但仍然不靈活，我們希望在入隊(duì)時(shí)的resize只涉及到擴(kuò)容，出隊(duì)時(shí)的resize只涉及縮容，我們是否能對(duì)這樣的需求進(jìn)行優(yōu)化呢？

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

循環(huán)隊(duì)列的思想和ArrayQueue優(yōu)化后的MyQueue大體相同，只不過(guò)循環(huán)隊(duì)列里面加入了更加巧妙的循環(huán)機(jī)制。

上例中,我們規(guī)定tail == data.length-1隊(duì)列為滿(mǎn)進(jìn)行resize,但是這一次我們換一種思路。當(dāng)繼續(xù)向當(dāng)前隊(duì)列添加元素時(shí)，我們這樣做：

變量tail重新回到了起點(diǎn)，這也就是循環(huán)隊(duì)列稱(chēng)之為“循環(huán)”的意義所在。那么什么時(shí)候表示當(dāng)前隊(duì)列已滿(mǎn)需要進(jìn)行resize呢？

當(dāng)front == (tail+1)%data.length，當(dāng)這個(gè)條件成立時(shí)，也就說(shuō)明了隊(duì)列為滿(mǎn)，需要進(jìn)行擴(kuò)容操作了。循環(huán)隊(duì)列實(shí)現(xiàn)代碼如下：

public class LoopQueue<E> implements Queue<E> {private E[]data;private int front;private int tail;public LoopQueue(int capacity){data = (E[])new Object[capacity+1];}public LoopQueue(){this(10);}@Overridepublic int getSize(){if(tail<front)return data.length-(front-tail);else{return tail-front;}}public int getCapacity(){return data.length-1;}@Overridepublic boolean isEmpty(){return getSize()==0;}private void resize(int newCapacity){E[]newData = (E[])new Object[newCapacity+1];for(int i=0;i<getSize();i++){newData[i] = data[(i+front)%data.length];}data = newData;tail = getSize();front = 0;}@Overridepublic void enqueue(E e){if(front==(tail+1)%data.length)resize(2*getSize());data[tail] = e;tail = (tail+1)%data.length;}@Overridepublic E dequeue(){E ret = data[front];// Loitering Objectdata[front] = null;front = (front+1)%data.length;if(getSize() == getCapacity()/4 && getCapacity()/2!=0){resize(getCapacity()/2);}return ret;}@Overridepublic E getFront(){if(getSize()==0)throw new IllegalArgumentException("LoopQueue is empty");return data[front];}@Overridepublic String toString(){StringBuilder stringBuilder = new StringBuilder();stringBuilder.append(String.format("LoopQueue size:%d,capacity:%d\n",getSize(),getCapacity()));stringBuilder.append("front:[");for(int i=front;i!=tail;i=(i+1)%data.length){stringBuilder.append(data[i]);if((i+1)%data.length!=tail)stringBuilder.append(",");}stringBuilder.append("]tail");return stringBuilder.toString();} }復(fù)制代碼

現(xiàn)在我們對(duì)ArrayQueue,LoopQueue進(jìn)行性能上的測(cè)試，

import java.util.Random;public class Main {private static double testQueue(Queue<Integer>q,int testCount){long startTime = System.nanoTime();Random random = new Random();for(int i=0;i<testCount;i++)q.enqueue(random.nextInt(Integer.MAX_VALUE));for(int i=0;i<testCount;i++)q.dequeue();long endTime = System.nanoTime();return (endTime-startTime)/1000000000.0;}public static void main(String[]args){int testCount = 100000;ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();LoopQueue<Integer> loopQueue = new LoopQueue<>();double loopQueueTime = testQueue(loopQueue,testCount);double arrayQueueTime = testQueue(arrayQueue,testCount);System.out.println("LoopQueue:"+loopQueueTime);System.out.println("ArrayQueue"+arrayQueueTime);} }復(fù)制代碼

在jdk1.8的環(huán)境下測(cè)試結(jié)果為：

導(dǎo)致兩者之間造成巨大差異的結(jié)果就是dequeue操作，ArrayQueue的dequeue操作為O(n)級(jí)別的算法，而LoopQueue的dequeue操作 在均攤的時(shí)間復(fù)雜度上為O(1)。

總結(jié)

以上是生活随笔為你收集整理的数据结构之——队列与循环队列的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。