您好,登錄后才能下訂單哦!
隊列寫法有哪些,很多新手對此不是很清楚,為了幫助大家解決這個難題,下面小編將為大家詳細(xì)講解,有這方面需求的人可以來學(xué)習(xí)下,希望你能有所收獲。
棧和隊列是一對好兄弟,前面我們介紹過一篇棧的文章(棧,不就后進先出),棧的機制相對簡單,后入先出,就像進入一個狹小的山洞,山洞只有一個出入口,只能后進先出(在外面的先出去,堵在里面先進去的就有點倒霉)。而隊列就好比是一個隧道,后面的人跟著前面走,前面人先出去(先入先出)。日常的排隊就是隊列運轉(zhuǎn)形式的一個描述!
棧是一種喜新厭舊的數(shù)據(jù)結(jié)構(gòu),來了新的就會處理新的把老的先停滯在這(我們找人、約人辦事最討厭這種人),隊列就是大公無私的一種數(shù)據(jù)結(jié)構(gòu),排隊先來先得,講究順序性,所以這種數(shù)據(jù)結(jié)構(gòu)在程序設(shè)計、中間件等都非常廣泛的應(yīng)用,例如消息隊列、FIFO磁盤調(diào)度、二叉樹層序遍歷、BFS寬度優(yōu)先搜索等等。
隊列的核心理念就是:先進先出! 這種非?;A(chǔ)和重要的數(shù)據(jù)結(jié)構(gòu)一定要掌握并手寫一個!雖然隊列就是先進先出核心規(guī)則,但手寫還需要考慮不少細(xì)節(jié)!
隊列的概念:隊列是一種特殊的線性表,特殊之處在于它只允許在表的前端(front)進行刪除操作,而在表的后端(rear)進行插入操作,和棧一樣,隊列是一種操作受限制的線性表。進行插入操作的端稱為隊尾,進行刪除操作的端稱為隊頭。
同時,閱讀本篇文章最好先弄懂順序表的基本操作和棧的數(shù)據(jù)結(jié)構(gòu)!學(xué)習(xí)效果更佳!
我們設(shè)計隊列時候可以選擇一個標(biāo)準(zhǔn),這里就拿力扣622設(shè)計循環(huán)隊列作為隊列設(shè)計的標(biāo)準(zhǔn)。
隊頭front:刪除數(shù)據(jù)的一端。
隊尾rear: 插入數(shù)據(jù)的一端。
對于數(shù)組,從數(shù)組后面插入更容易,數(shù)組前面插入較困難,所以一般用數(shù)組實現(xiàn)的隊列隊頭在數(shù)組前面,隊尾在數(shù)組后面;而對于鏈表,插入刪除在兩頭分別進行那么頭部(前面)刪除尾部插入最方便的選擇。
實現(xiàn)方法:
MyCircularQueue(k): 構(gòu)造器,設(shè)置隊列長度為 k 。
Front: 從隊首獲取元素。如果隊列為空,返回 -1 。
Rear: 獲取隊尾元素。如果隊列為空,返回 -1 。
enQueue(value): 向循環(huán)隊列插入一個元素。如果成功插入則返回真。
deQueue(): 從循環(huán)隊列中刪除一個元素。如果成功刪除則返回真。
isEmpty(): 檢查循環(huán)隊列是否為空。
isFull(): 檢查循環(huán)隊列是否已滿。
按照上述的介紹,我們很容易知道數(shù)組實現(xiàn)的方式。用數(shù)組模擬表示隊列。要考慮初始化,插入,問題。
在這個普通隊列一些操作需要注意的有:
初始化:數(shù)組的front和rear都指向0. (front和rear下標(biāo)相等的時候說明隊列為空)
入隊:隊不滿,數(shù)組不越界,先隊尾位置傳值,再隊尾下標(biāo)+1(隊尾rear實際上超前一位,為了區(qū)分空隊列情況)
出隊:隊不空,先取隊頭位置元素,在隊頭+1。
但是很容易發(fā)現(xiàn)問題,每個空間域只能利用一次,造成空間極度浪費,非常容易越界!
針對上述的問題。有個較好的解決方法!就是對已經(jīng)申請的(數(shù)組)內(nèi)存重復(fù)利用。這就是我們所說的循環(huán)隊列。循環(huán)隊列的一個好處是我們可以利用這個隊列之前用過的空間。在一個普通隊列里,一旦一個隊列滿了,我們就不能插入下一個元素,即使在隊列前面仍有空間。但是使用循環(huán)隊列,我們能使用這些空間去存儲新的值。
數(shù)組實現(xiàn)的循環(huán)隊列就是在邏輯上作修改。因為我們隊列中只需要front和rear兩個指針。rear在邏輯上在后面,front在邏輯上是在前面的,但實際上它們不一定誰在前誰在后,在計算距離的時候需要給rear先補上數(shù)組長度減去front,然后求余即可。
初始化:數(shù)組的front和rear都指向0. 這里需要注意的是:front和rear位于同一個位置時候,證明隊列里面是空的。還有在這里我具體實現(xiàn)時候?qū)?shù)組申請大了一個位置空出來,防止隊列滿的情況又造成front和rear在同一個位置。
入隊:隊不滿,先隊尾位置傳值,再rear=(rear+1) % maxsize;
出隊:隊不空,先取隊頭位置元素,front=(front+1)% maxsize;
這里出隊入隊指標(biāo)相加如果遇到最后需要轉(zhuǎn)到頭位置,這里直接+1求余找到位置(相比判斷是否在最后更加簡潔),其中maxsize是數(shù)組實際大小。
是否為空:return rear == front;
大小:return (rear+maxsize-front)%maxsize; 這里很容易理解,一張圖就能解釋清楚,無論是front實際在前在后都能滿足要求。
這里面有幾個大家需要注意的,就是指標(biāo)相加如果遇到最后需要轉(zhuǎn)到頭的話??梢耘袛嗍欠竦綌?shù)組末尾位置。也可以直接+1求余。其中maxsize是數(shù)組實際大小。
具體實現(xiàn):
public class MyCircularQueue { private int data[];// 數(shù)組容器 private int front;// 頭 private int rear;// 尾 private int maxsize;// 最大長度 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; } }
對于鏈表實現(xiàn)的隊列,要根據(jù)先進先出的規(guī)則考慮頭和尾的位置
我們知道隊列是先進先出的,對于鏈表,我們能采用單鏈表盡量采用單鏈表,能方便盡量方便,同時還要兼顧效率。使用鏈表大概有兩個實現(xiàn)方案:
方案一 如果隊列頭設(shè)在鏈表尾,隊列尾設(shè)在鏈表頭。那么隊尾進隊插入在鏈表頭部插入沒問題,容易實現(xiàn),但是如果隊頭刪除在鏈表尾部進行,如果不設(shè)置尾指針要遍歷到隊尾,但是設(shè)置尾指針刪除需要將它前驅(qū)節(jié)點需要雙向鏈表,都挺麻煩的。
方案二如果隊列頭設(shè)在鏈表頭,隊列尾設(shè)在鏈表尾,那么隊尾進隊插入在鏈表尾部插入沒問題(用尾指針可以直接指向next),容易實現(xiàn),如果隊頭刪除在鏈表頭部進行也很容易,就是我們前面常說的頭節(jié)點刪除節(jié)點。
所以我們最終采取的是方案2的帶頭節(jié)點、帶尾指針的單鏈表!
主要操作為:
初始化:設(shè)立一個頭結(jié)點,是front和rear都先指向它。
入隊:rear.next=va;rear=va;(va為被插入節(jié)點)
、
出隊:隊不空,front.next=front.next.next;經(jīng)典帶頭節(jié)點刪除,但是如果僅有一個節(jié)點刪除時候,需要多加一個rear=front,不然rear就失聯(lián)啦。
是否為空:return rear == front; 或者自定義維護len判斷return len==0
大?。汗?jié)點front遍歷到rear的個數(shù),或者自定義維護len直接返回(這里并沒實現(xiàn))。
實現(xiàn)代碼:
public class MyCircularQueue{ class node { int data;// 節(jié)點的結(jié)果 node next;// 下一個連接的節(jié)點 public node() {} public node(int data) { this.data = data; } } node front;//相當(dāng)于head 帶頭節(jié)點的 node rear;//相當(dāng)于tail/end int maxsize;//最大長度 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; } }
設(shè)計實現(xiàn)雙端隊列,其實你經(jīng)常使用的ArrayDeque就是一個經(jīng)典的雙向隊列,其基于數(shù)組實現(xiàn),效率非常高。我們這里實現(xiàn)的雙向隊列模板基于力扣641 設(shè)計循環(huán)雙端隊列 。
你的實現(xiàn)需要支持以下操作:
MyCircularDeque(k):構(gòu)造函數(shù),雙端隊列的大小為k。
insertFront():將一個元素添加到雙端隊列頭部。如果操作成功返回 true。
insertLast():將一個元素添加到雙端隊列尾部。如果操作成功返回 true。
deleteFront():從雙端隊列頭部刪除一個元素。如果操作成功返回 true。
deleteLast():從雙端隊列尾部刪除一個元素。如果操作成功返回 true。
getFront():從雙端隊列頭部獲得一個元素。如果雙端隊列為空,返回 -1。
getRear():獲得雙端隊列的最后一個元素。如果雙端隊列為空,返回 -1。
isEmpty():檢查雙端隊列是否為空。
isFull():檢查雙端隊列是否滿了。
其實有了上面的基礎(chǔ),實現(xiàn)一個雙端隊列非常容易,有很多操作和單端的循環(huán)隊列是一致的,只有多了一個隊頭插入和隊尾刪除的操作,兩個操作分別簡單的分析一下:
隊頭插入:隊友front下標(biāo)位置本身是有值的,所以要將front退后一位然后再賦值,不過要考慮是否為滿或者數(shù)組越界情況。
隊尾刪除:只需要rear位置減1,同時也要考慮是否為空和越界情況。
具體實現(xiàn)代碼:
public class MyCircularDeque { private int data[];// 數(shù)組容器 private int front;// 頭 private int rear;// 尾 private int maxsize;// 最大長度 /*初始化 最大大小為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; } }
對于隊列來說數(shù)據(jù)結(jié)構(gòu)相比棧復(fù)雜一些,但是也不是很難,搞懂先進先出然后用數(shù)組或者鏈表實現(xiàn)即可。
對于數(shù)組,隊尾tail指向的位置是空的,而鏈表的front(head一樣)為頭指針為空的,所以在不同結(jié)構(gòu)實現(xiàn)相同效果的方法需要注意一下。
數(shù)組實現(xiàn)的循環(huán)隊列能夠很大程度利用數(shù)組空間,而雙向隊列則是既能當(dāng)隊列又能當(dāng)棧的一種高效數(shù)據(jù)結(jié)構(gòu),掌握還是很有必要的。
看完上述內(nèi)容是否對您有幫助呢?如果還想對相關(guān)知識有進一步的了解或閱讀更多相關(guān)文章,請關(guān)注億速云行業(yè)資訊頻道,感謝您對億速云的支持。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。