面試官讓手寫隊(duì)列，差點(diǎn)沒寫出來(lái)

前言

棧和隊(duì)列是一對(duì)好兄弟，前面我們介紹過(guò)一篇棧的文章(棧，不就后進(jìn)先出)，棧的機(jī)制相對(duì)簡(jiǎn)單，后入先出，就像進(jìn)入一個(gè)狹小的山洞，山洞只有一個(gè)出入口，只能后進(jìn)先出(在外面的先出去，堵在里面先進(jìn)去的就有點(diǎn)倒霉)。而隊(duì)列就好比是一個(gè)隧道，后面的人跟著前面走，前面人先出去(先入先出)。日常的排隊(duì)就是隊(duì)列運(yùn)轉(zhuǎn)形式的一個(gè)描述！

棧是一種喜新厭舊的數(shù)據(jù)結(jié)構(gòu)，來(lái)了新的就會(huì)處理新的把老的先停滯在這(我們找人、約人辦事最討厭這種人)，隊(duì)列就是大公無(wú)私的一種數(shù)據(jù)結(jié)構(gòu)，排隊(duì)先來(lái)先得，講究順序性，所以這種數(shù)據(jù)結(jié)構(gòu)在程序設(shè)計(jì)、中間件等都非常廣泛的應(yīng)用，例如消息隊(duì)列、FIFO磁盤調(diào)度、二叉樹層序遍歷、BFS寬度優(yōu)先搜索等等。

隊(duì)列的核心理念就是：先進(jìn)先出！

隊(duì)列的概念：隊(duì)列是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進(jìn)行刪除操作，而在表的后端（rear）進(jìn)行插入操作，和棧一樣，隊(duì)列是一種操作受限制的線性表。進(jìn)行插入操作的端稱為隊(duì)尾，進(jìn)行刪除操作的端稱為隊(duì)頭。

同時(shí)，閱讀本篇文章最好先弄懂順序表的基本操作和棧的數(shù)據(jù)結(jié)構(gòu)！學(xué)習(xí)效果更佳！

隊(duì)列介紹

我們?cè)O(shè)計(jì)隊(duì)列時(shí)候可以選擇一個(gè)標(biāo)準(zhǔn)，這里就拿力扣622設(shè)計(jì)循環(huán)隊(duì)列作為隊(duì)列設(shè)計(jì)的標(biāo)準(zhǔn)。

隊(duì)頭front： 刪除數(shù)據(jù)的一端。

隊(duì)尾rear： 插入數(shù)據(jù)的一端。

對(duì)于數(shù)組，從數(shù)組后面插入更容易，數(shù)組前面插入較困難，所以一般用數(shù)組實(shí)現(xiàn)的隊(duì)列隊(duì)頭在數(shù)組前面，隊(duì)尾在數(shù)組后面；而對(duì)于鏈表，插入刪除在兩頭分別進(jìn)行那么頭部(前面)刪除尾部插入最方便的選擇。

實(shí)現(xiàn)方法：

MyCircularQueue(k): 構(gòu)造器，設(shè)置隊(duì)列長(zhǎng)度為 k 。

Front: 從隊(duì)首獲取元素。如果隊(duì)列為空，返回 -1 。

Rear: 獲取隊(duì)尾元素。如果隊(duì)列為空，返回 -1 。

enQueue(value): 向循環(huán)隊(duì)列插入一個(gè)元素。如果成功插入則返回真。

deQueue(): 從循環(huán)隊(duì)列中刪除一個(gè)元素。如果成功刪除則返回真。

isEmpty(): 檢查循環(huán)隊(duì)列是否為空。

isFull(): 檢查循環(huán)隊(duì)列是否已滿。

普通隊(duì)列

按照上述的介紹，我們很容易知道數(shù)組實(shí)現(xiàn)的方式。用數(shù)組模擬表示隊(duì)列。要考慮初始化，插入，問(wèn)題。

在這個(gè)普通隊(duì)列一些操作需要注意的有：

初始化：數(shù)組的front和rear都指向0. (front和rear下標(biāo)相等的時(shí)候說(shuō)明隊(duì)列為空)

入隊(duì)：隊(duì)不滿，數(shù)組不越界，先隊(duì)尾位置傳值，再隊(duì)尾下標(biāo)+1(隊(duì)尾rear實(shí)際上超前一位，為了區(qū)分空隊(duì)列情況)

出隊(duì)：隊(duì)不空，先取隊(duì)頭位置元素，在隊(duì)頭+1。

但是很容易發(fā)現(xiàn)問(wèn)題，每個(gè)空間域只能利用一次，造成空間極度浪費(fèi)，非常容易越界！

循環(huán)隊(duì)列(數(shù)組實(shí)現(xiàn))

針對(duì)上述的問(wèn)題。有個(gè)較好的解決方法！就是對(duì)已經(jīng)申請(qǐng)的(數(shù)組)內(nèi)存重復(fù)利用。這就是我們所說(shuō)的循環(huán)隊(duì)列。循環(huán)隊(duì)列的一個(gè)好處是我們可以利用這個(gè)隊(duì)列之前用過(guò)的空間。在一個(gè)普通隊(duì)列里，一旦一個(gè)隊(duì)列滿了，我們就不能插入下一個(gè)元素，即使在隊(duì)列前面仍有空間。但是使用循環(huán)隊(duì)列，我們能使用這些空間去存儲(chǔ)新的值。

數(shù)組實(shí)現(xiàn)的循環(huán)隊(duì)列就是在邏輯上作修改。因?yàn)槲覀冴?duì)列中只需要front和rear兩個(gè)指針。rear在邏輯上在后面，front在邏輯上是在前面的，但實(shí)際上它們不一定誰(shuí)在前誰(shuí)在后，在計(jì)算距離的時(shí)候需要給rear先補(bǔ)上數(shù)組長(zhǎng)度減去front，然后求余即可。

初始化：數(shù)組的front和rear都指向0. 這里需要注意的是：front和rear位于同一個(gè)位置時(shí)候，證明隊(duì)列里面是空的。還有在這里我具體實(shí)現(xiàn)時(shí)候?qū)?shù)組申請(qǐng)大了一個(gè)位置空出來(lái)，防止隊(duì)列滿的情況又造成front和rear在同一個(gè)位置。

入隊(duì)：隊(duì)不滿，先隊(duì)尾位置傳值，再rear=(rear + 1) % maxsize;

出隊(duì)：隊(duì)不空，先取隊(duì)頭位置元素，front=(front + 1)% maxsize;

這里出隊(duì)入隊(duì)指標(biāo)相加如果遇到最后需要轉(zhuǎn)到頭位置，這里直接+1求余找到位置(相比判斷是否在最后更加簡(jiǎn)潔)，其中maxsize是數(shù)組實(shí)際大小。

是否為空：return rear == front;

大?。簉eturn (rear+maxsize-front)%maxsize; 這里很容易理解，一張圖就能解釋清楚，無(wú)論是front實(shí)際在前在后都能滿足要求。

這里面有幾個(gè)大家需要注意的，就是指標(biāo)相加如果遇到最后需要轉(zhuǎn)到頭的話。可以判斷是否到數(shù)組末尾位置。也可以直接+1求余。其中maxsize是數(shù)組實(shí)際大小。

具體實(shí)現(xiàn)：

public class MyCircularQueue { private int data[];// 數(shù)組容器 private int front;// 頭 private int rear;// 尾 private int maxsize;// 最大長(zhǎng)度 public MyCircularQueue(int k) { data = new int[k+1]; front = 0; rear = 0; maxsize = k+1; } public boolean enQueue(int value) { if (isFull()) return false; else { data[rear] = value; rear=(rear + 1) % maxsize; } return true; } public boolean deQueue() { if (isEmpty()) return false; else { front=(front+1)%maxsize; } return true; } public int Front() { if(isEmpty()) return -1; return data[front]; } public int Rear() { if(isEmpty()) return -1; return data[(rear-1+maxsize)%maxsize]; } public boolean isEmpty() { return rear == front; } public boolean isFull() { return (rear + 1) % maxsize == front; } }

循環(huán)隊(duì)列(鏈表實(shí)現(xiàn))

對(duì)于鏈表實(shí)現(xiàn)的隊(duì)列，要根據(jù)先進(jìn)先出的規(guī)則考慮頭和尾的位置

我們知道隊(duì)列是先進(jìn)先出的，對(duì)于鏈表，我們能采用單鏈表盡量采用單鏈表，能方便盡量方便，同時(shí)還要兼顧效率。使用鏈表大概有兩個(gè)實(shí)現(xiàn)方案：

方案一 如果隊(duì)列頭設(shè)在鏈表尾，隊(duì)列尾設(shè)在鏈表頭。那么隊(duì)尾進(jìn)隊(duì)插入在鏈表頭部插入沒問(wèn)題，容易實(shí)現(xiàn)，但是如果隊(duì)頭刪除在鏈表尾部進(jìn)行，如果不設(shè)置尾指針要遍歷到隊(duì)尾，但是設(shè)置尾指針刪除需要將它前驅(qū)節(jié)點(diǎn)需要雙向鏈表，都挺麻煩的。

方案二如果隊(duì)列頭設(shè)在鏈表頭，隊(duì)列尾設(shè)在鏈表尾，那么隊(duì)尾進(jìn)隊(duì)插入在鏈表尾部插入沒問(wèn)題(用尾指針可以直接指向next)，容易實(shí)現(xiàn)，如果隊(duì)頭刪除在鏈表頭部進(jìn)行也很容易，就是我們前面常說(shuō)的頭節(jié)點(diǎn)刪除節(jié)點(diǎn)。

所以我們最終采取的是方案2的帶頭節(jié)點(diǎn)、帶尾指針的單鏈表!

主要操作為：

初始化：設(shè)立一個(gè)頭結(jié)點(diǎn)，是front和rear都先指向它。

入隊(duì)：rear.next=va;rear=va;（va為被插入節(jié)點(diǎn)）

出隊(duì)：隊(duì)不空，front.next=front.next.next;經(jīng)典帶頭節(jié)點(diǎn)刪除，但是如果僅有一個(gè)節(jié)點(diǎn)刪除時(shí)候，需要多加一個(gè)rear=front，不然rear就失聯(lián)啦。

是否為空：return rear == front; 或者自定義維護(hù)len判斷return len==0

大?。汗?jié)點(diǎn)front遍歷到rear的個(gè)數(shù)，或者自定義維護(hù)len直接返回(這里并沒實(shí)現(xiàn))。

實(shí)現(xiàn)代碼：

public class MyCircularQueue{ class node { int data;// 節(jié)點(diǎn)的結(jié)果 node next;// 下一個(gè)連接的節(jié)點(diǎn) public node() {} public node(int data) { this.data = data; } } node front;//相當(dāng)于head 帶頭節(jié)點(diǎn)的 node rear;//相當(dāng)于tail/end int maxsize;//最大長(zhǎng)度 int len=0; public MyCircularQueue(int k) { front=new node(0); rear=front; maxsize=k; len=0; } public boolean enQueue(int value) { if (isFull()) return false; else { node va=new node(value); rear.next=va; rear=va; len++; } return true; } public boolean deQueue() { if (isEmpty()) return false; else { front.next=front.next.next; len--; //注意 如果被刪完 需要將rear指向front if(len==0) rear=front; } return true; } public int Front() { if(isEmpty()) return -1; return front.next.data; } public int Rear() { if(isEmpty()) return -1; return rear.data; } public boolean isEmpty() { return len==0; //return rear == front; } public boolean isFull() { return len==maxsize; } }

雙向隊(duì)列(加餐)

設(shè)計(jì)實(shí)現(xiàn)雙端隊(duì)列，其實(shí)你經(jīng)常使用的ArrayDeque就是一個(gè)經(jīng)典的雙向隊(duì)列，其基于數(shù)組實(shí)現(xiàn)，效率非常高。我們這里實(shí)現(xiàn)的雙向隊(duì)列模板基于力扣641 設(shè)計(jì)循環(huán)雙端隊(duì)列 。

你的實(shí)現(xiàn)需要支持以下操作：

MyCircularDeque(k)：構(gòu)造函數(shù),雙端隊(duì)列的大小為k。

insertFront()：將一個(gè)元素添加到雙端隊(duì)列頭部。 如果操作成功返回 true。

insertLast()：將一個(gè)元素添加到雙端隊(duì)列尾部。如果操作成功返回 true。

deleteFront()：從雙端隊(duì)列頭部刪除一個(gè)元素。 如果操作成功返回 true。

deleteLast()：從雙端隊(duì)列尾部刪除一個(gè)元素。如果操作成功返回 true。

getFront()：從雙端隊(duì)列頭部獲得一個(gè)元素。如果雙端隊(duì)列為空，返回 -1。

getRear()：獲得雙端隊(duì)列的最后一個(gè)元素。 如果雙端隊(duì)列為空，返回 -1。

isEmpty()：檢查雙端隊(duì)列是否為空。

isFull()：檢查雙端隊(duì)列是否滿了。

其實(shí)有了上面的基礎(chǔ)，實(shí)現(xiàn)一個(gè)雙端隊(duì)列非常容易，有很多操作和單端的循環(huán)隊(duì)列是一致的，只有多了一個(gè)隊(duì)頭插入和隊(duì)尾刪除的操作，兩個(gè)操作分別簡(jiǎn)單的分析一下：

隊(duì)頭插入：隊(duì)友front下標(biāo)位置本身是有值的，所以要將front退后一位然后再賦值，不過(guò)要考慮是否為滿或者數(shù)組越界情況。

隊(duì)尾刪除：只需要rear位置減1，同時(shí)也要考慮是否為空和越界情況。

具體實(shí)現(xiàn)代碼：

public class MyCircularDeque { private int data[];// 數(shù)組容器 private int front;// 頭 private int rear;// 尾 private int maxsize;// 最大長(zhǎng)度 /*初始化 最大大小為k */ public MyCircularDeque(int k) { data = new int[k+1]; front = 0; rear = 0; maxsize = k+1; } /** 頭部插入 */ public boolean insertFront(int value) { if(isFull()) return false; else { front=(front+maxsize-1)%maxsize; data[front]=value; } return true; } /** 尾部插入 */ public boolean insertLast(int value) { if(isFull()) return false; else{ data[rear]=value; rear=(rear+1)%maxsize; } return true; } /** 正常頭部刪除 */ public boolean deleteFront() { if (isEmpty()) return false; else { front=(front+1)%maxsize; } return true; } /** 尾部刪除 */ public boolean deleteLast() { if(isEmpty()) return false; else { rear=(rear+maxsize-1)%maxsize; } return true; } /** Get the front item */ public int getFront() { if(isEmpty()) return -1; return data[front]; } /** Get the last item from the deque. */ public int getRear() { if(isEmpty()) return -1; return data[(rear-1+maxsize)%maxsize]; } /** Checks whether the circular deque is empty or not. */ public boolean isEmpty() { return front==rear; } /** Checks whether the circular deque is full or not. */ public boolean isFull() { return (rear+1)%maxsize==front; } }

總結(jié)

對(duì)于隊(duì)列來(lái)說(shuō)數(shù)據(jù)結(jié)構(gòu)相比棧復(fù)雜一些，但是也不是很難，搞懂先進(jìn)先出然后用數(shù)組或者鏈表實(shí)現(xiàn)即可。

對(duì)于數(shù)組，隊(duì)尾tail指向的位置是空的，而鏈表的front（head一樣）為頭指針為空的，所以在不同結(jié)構(gòu)實(shí)現(xiàn)相同效果的方法需要注意一下。

數(shù)組實(shí)現(xiàn)的循環(huán)隊(duì)列能夠很大程度利用數(shù)組空間，而雙向隊(duì)列則是既能當(dāng)隊(duì)列又能當(dāng)棧的一種高效數(shù)據(jù)結(jié)構(gòu)，掌握還是很有必要的。

最后，筆者水平有限，如果有紕漏和不足之處還請(qǐng)指出。另外，如果感覺不錯(cuò)可以點(diǎn)個(gè)贊，關(guān)注個(gè)人公眾號(hào)：bigsai 更多經(jīng)常與你分享，關(guān)注回復(fù)bigsai獲取精心準(zhǔn)備的學(xué)習(xí)資料一份！

Java 數(shù)據(jù)結(jié)構(gòu)

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請(qǐng)聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。