java中棧和隊(duì)列的分析

　　《p》棧《/p》《p》棧的英文單詞是Stack，它代表一種特殊的線性表，這種線性表只能在固定一端（通常認(rèn)為是線性表的尾端）進(jìn)行插入，刪除操作?！?p》《p》棧的基本定義《/p》《p》棧是一種數(shù)據(jù)結(jié)構(gòu)，它代表只能在某一端進(jìn)行插入，刪除操作的特殊線性表，通常就是在線性表的尾端進(jìn)行插入，刪除操作。《/p》《p》對(duì)于棧而言，允許進(jìn)行插入，刪除操作的一端被稱為棧頂（top），另一端咋被稱為棧底（bottom）。《/p》《p》對(duì)于一個(gè)棧不包含任何元素，那么這個(gè)棧就被稱為空棧。 《br》 從棧頂插入一個(gè)元素被稱為進(jìn)棧，將一個(gè)元素從棧頂刪除被稱為“彈出棧”，對(duì)應(yīng)的英文說法為pop，如下圖：《/p》《p》stack.PNG 《br》 對(duì)于元素為a0，a1，a2，…，an-1的棧，假設(shè)棧中元素被a0，a1，a2，…，an-1的次序進(jìn)棧，那么a0未棧底元素，an-1為棧頂元素。出棧時(shí)第一個(gè)彈出的元素應(yīng)為棧頂元素，也就是an-1.也就是說，棧中元素的修改是按后進(jìn)先出（LIFO）的原則進(jìn)行的?！?p》《p》歸納起來，可以再對(duì)棧下一個(gè)定義：棧就是一種后進(jìn)先出（LIFO）的線性表。《/p》《p》棧的常用操作《/p》《p》棧是一種被限制過的線性表，通常不應(yīng)該提供線性表中的如下方法：《/p》《p》獲取指定索引處的元素 《br》 按值查找數(shù)據(jù)元素的位置 《br》 向指定索引處插入數(shù)據(jù)元素 《br》 刪除指定元素索引處的數(shù)據(jù)元素 《br》 從上面這個(gè)方法可以看出，棧不應(yīng)該提供從中間任意位置 《br》 訪問元素的方法。也就是說，棧只允許在棧頂插入，刪除元素。 《br》 棧的常用操作如下： 《br》 初始化：通常是一個(gè)構(gòu)造器，用于創(chuàng)建一個(gè)空棧 《br》 返回棧的長(zhǎng)度：該方法用于返回棧中數(shù)據(jù)元素的個(gè)數(shù) 《br》 入棧：向棧的棧頂插入一個(gè)數(shù)據(jù)元素，棧的長(zhǎng)度+1 《br》 出棧：從棧的棧頂刪除一個(gè)數(shù)據(jù)元素，棧的長(zhǎng)度-1，該方法通常飯后被刪除的元素 《br》 訪問棧頂元素：返回棧頂?shù)臄?shù)據(jù)元素，但不刪除棧頂元素 《br》 判斷棧是否為空：改方法判斷棧是否為空，如果棧為空則返回true，否則返回false. 《br》 清空棧：將棧清空 《br》 類似于線性表即采用順序存儲(chǔ)的方式來實(shí)現(xiàn)，也可以用鏈?zhǔn)浇Y(jié)構(gòu)來實(shí)現(xiàn)，也可使用鏈?zhǔn)浇Y(jié)構(gòu)來實(shí)現(xiàn)，棧同樣即可采用順序結(jié)構(gòu)來存儲(chǔ)棧內(nèi)的元素，也可采用鏈?zhǔn)浇Y(jié)構(gòu)來存儲(chǔ)棧內(nèi)元素?！?p》《p》棧的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)《/p》《p》順序存儲(chǔ)結(jié)構(gòu)的棧簡(jiǎn)稱為順序棧，它利用一組地址連續(xù)的存儲(chǔ)單元依次存放從棧底到棧頂?shù)臄?shù)據(jù)元素。棧底位置固定不變，它的棧頂可以直接通過順序棧底層數(shù)組的數(shù)組元素arr［size-1］來訪問。順序棧的存儲(chǔ)示意圖如下圖：《/p》《p》stack_sort.PNG 《br》 順序棧中數(shù)據(jù)元素的物理關(guān)系和邏輯關(guān)系是一致的，先進(jìn)棧的元素位于棧底，棧底元素的存儲(chǔ)位置相對(duì)也比較小?！?p》《p》1.進(jìn)?！?p》《p》對(duì)于順序棧的進(jìn)棧操作而言，只需將新的數(shù)據(jù)元素存入棧內(nèi)，然后讓記錄棧內(nèi)元素個(gè)數(shù)的變量加1，程序即可再次通過arr［size-1］重新訪問新的棧頂元素。進(jìn)棧操作示意圖如下：《/p》《p》inti_stack.PNG 《br》 由于順序棧底層通常會(huì)采用數(shù)組來保存數(shù)據(jù)元素，因此可能出現(xiàn)的情況是：當(dāng)程序試圖讓一個(gè)數(shù)據(jù)元素進(jìn)棧時(shí)，底層數(shù)據(jù)已滿，那么就必須擴(kuò)充底層數(shù)組的長(zhǎng)度來容納新進(jìn)棧的數(shù)據(jù)元素。《/p》《p》1.出?！?p》《p》對(duì)于順序棧的出棧操作而言，需要將棧頂元素彈出棧，程序要做兩件事?！?p》《p》讓記錄棧內(nèi)元素個(gè)數(shù)的變量減1. 《br》 釋放數(shù)組對(duì)棧頂元素的引用。 《br》 出棧操作示意圖如下圖：《/p》《p》out_stack.PNG 《br》 對(duì)于刪除操作來說，只要讓記錄棧內(nèi)元素個(gè)數(shù)的size減1，程序即可通過arr［size-1］訪問到新的棧頂元素。但不要忘記釋放原來?xiàng)ｍ數(shù)臄?shù)組引用，否則會(huì)引起內(nèi)存泄漏?！?p》《p》棧比普通線性表的功能更弱，棧時(shí)一種被限制過的線性表，只能從棧頂插入，刪除數(shù)據(jù)元素?！?p》《p》棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及實(shí)現(xiàn)《/p》《p》程序可以采用單鏈表來保存棧中所有元素，這種鏈?zhǔn)浇Y(jié)構(gòu)的棧也被稱為棧鏈。對(duì)于棧鏈而言，棧頂元素不斷地改變，程序只要使用一個(gè)top引用來記錄當(dāng)前的棧頂元素即可。top引用變量永遠(yuǎn)引用棧頂元素，再使用一個(gè)size變量記錄當(dāng)前棧中包含多少個(gè)元素即可。如下圖：《/p》《p》linked_stack.PNG 《br》 1.進(jìn)?！?p》《p》對(duì)于棧鏈的進(jìn)棧操作，程序只需要做如下兩件事： 《br》 -讓top引用指向新元素添加的元素，新元素的next引用指向原來的棧頂元素?！?p》《p》讓記錄棧內(nèi)元素個(gè)數(shù)的size變量加1. 《br》 進(jìn)棧操作示意圖如下：《/p》《p》into_linked_stack.PNG 《br》 2.出?！?p》《p》對(duì)于鏈棧的出棧操作，需要將棧頂元素彈出棧，程序需要做兩件事情：《/p》《p》讓top引用指向原棧頂元素的下一個(gè)元素，并釋放原來的棧頂元素 《br》 讓記錄棧內(nèi)元素個(gè)數(shù)的size變量減1. 《br》 出棧操作示意圖如下：《/p》《p》out_linked_stack.PNG 《br》 對(duì)于順序棧來說，程序開始就需要在底層為他開辟一塊連續(xù)的內(nèi)存（數(shù)組），這個(gè)空間浪費(fèi)其實(shí)很大。從空間利用率的角度說，鏈棧的空間利用率比順序棧的空間利用率要高一些?！?p》《p》java集合中的?！?p》《p》Java集合實(shí)際上提供兩種棧供開發(fā)者使用：《/p》《p》java.util.Stack：它就是一個(gè)最普通的順序棧，底層數(shù)據(jù)實(shí)現(xiàn)。這個(gè)Stick類是線程安全的，在多線程環(huán)境下也可以放心使用 《br》 java.util.LinkedList:LinkedList是一個(gè)雙端鏈表：除此之外。LinkedList還可作為棧使用，查看該類api將會(huì)發(fā)現(xiàn)，他同樣提供了push（），pop（），peek（）等方法，這表明LinkedList其實(shí)還可以當(dāng)成棧使用。LinkedList代表?xiàng)５逆準(zhǔn)綄?shí)現(xiàn)，但它是線程不安全的，如果需要在多線程環(huán)境下使用，則應(yīng)該使用Collections類的工具發(fā)將其“改造”成線程安全的類。 《br》 隊(duì)列《/p》《p》隊(duì)列的基本定義《/p》《p》隊(duì)列是一種特殊的線性表，他只允許在表的前端（front）進(jìn)行刪除操作，只允許在表的后端（rear）進(jìn)行插入操作，進(jìn)行插入操作的端稱為隊(duì)尾，進(jìn)行刪除的端稱為對(duì)頭?！?p》《p》如果隊(duì)列中不包含任何元素，該隊(duì)列就被稱為空隊(duì)列。《/p》《p》對(duì)于一個(gè)隊(duì)列來說，每個(gè)元素總是從隊(duì)列的rear端進(jìn)入隊(duì)列，然后等待該與元素之前的所有元素出對(duì)之后，當(dāng)前元素才能出對(duì)。因此，把隊(duì)列簡(jiǎn)稱為先進(jìn)先出（FIFO）的線性表。如下圖：《/p》《p》queue.PNG 《br》 隊(duì)列的常用操作《/p》《p》隊(duì)列同時(shí)是一種被限制過的線性表，通常不應(yīng)該提供線性表中的如下方法：《/p》《p》獲取指定索引處的元素 《br》 按值查找數(shù)據(jù)元素的位置 《br》 向指定索引處插入數(shù)據(jù)元素 《br》 刪除指定索引處的數(shù)據(jù)元素 《br》 從上面這些方法可以看出，隊(duì)列不應(yīng)該提供從中間任意位置訪問元素的方法，也就是說，隊(duì)列只允許在隊(duì)列的前端（front）刪除元素，只允許在隊(duì)列的后端（rear）插入元素。 《br》 隊(duì)列的常用操作如下： 《br》 初始化：通常是一個(gè)構(gòu)造器，用于創(chuàng)建一個(gè)空隊(duì)列 《br》 返回隊(duì)列的長(zhǎng)度：該方法用十返回隊(duì)列中數(shù)據(jù)元素的個(gè)數(shù)。 《br》 加入元索：向隊(duì)列的rear端插入一個(gè)數(shù)據(jù)元素，隊(duì)列的長(zhǎng)度+1 《br》 刪除元素：從隊(duì)列的front端刪除一個(gè)數(shù)據(jù)元素，隊(duì)列的長(zhǎng)度-1，該方法通常返回被刪除的元素。 《br》 訪問隊(duì)列的前端元素：返回隊(duì)列的front端的數(shù)據(jù)元素，但不刪除該元素。 《br》 判斷隊(duì)列是否為空：該方法判斷隊(duì)列是否為空，如果隊(duì)列為空則返回true否則返回false 《br》 清空隊(duì)列：將隊(duì)列清空 《br》 類似于線性表既可采用順序存儲(chǔ)的方式來實(shí)現(xiàn)，也可采用鏈?zhǔn)浇Y(jié)構(gòu)來賣現(xiàn)，隊(duì)列同樣既可采用順序結(jié)構(gòu)來存儲(chǔ)隊(duì)列元素，也可采用鏈?zhǔn)浇Y(jié)構(gòu)來存儲(chǔ)隊(duì)列元素。《/p》《p》隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)《/p》《p》系統(tǒng)采用一組地址連續(xù)的存儲(chǔ)單元依次存放隊(duì)列從rear端到front端的所有數(shù)據(jù)元素，程序只需（front和rear兩個(gè)整型變量來記錄隊(duì)列front端的元素索引、rear端的元素索引。示意圖如下：《/p》《p》queue_sort.PNG 《br》 順序隊(duì)列可能會(huì)造成假滿的問題，程序有如下解決方：《/p》《p》每次將元素移除隊(duì)列時(shí)將隊(duì)列中的所有元素向front端移動(dòng)一位，這種方式front值永遠(yuǎn)為0，有元素插入隊(duì)列時(shí)rear值+1，有元素移除隊(duì)列時(shí)rear值-1，。但這種方式非常浪費(fèi)時(shí)間，因?yàn)槊看螌⒃貜年?duì)列移除都需要進(jìn)行“整體搬家”。 《br》 將數(shù)組存儲(chǔ)區(qū)看成一個(gè)首尾相接的環(huán)形區(qū)域，當(dāng)存放數(shù)組的最大地址之后，rear值再次變?yōu)?。采用這種技巧存儲(chǔ)的隊(duì)列稱為循環(huán)隊(duì)列。 《br》 循環(huán)隊(duì)列《/p》《p》為了重新利用循環(huán)順序隊(duì)列底層數(shù)組中已刪除元素所占用的空間，消除可能出現(xiàn)的“假滿”現(xiàn)象，可以將順序隊(duì)列改進(jìn)為循環(huán)隊(duì)列。《/p》《p》循環(huán)隊(duì)列是首尾相連的隊(duì)列：當(dāng)front，rear變量值達(dá)到底層數(shù)組的capacity-1之后，再前進(jìn)一位就自定變成0，。示意圖如下：《/p》《p》circulation.PNG 《br》 不管隊(duì)列是空還是滿，都會(huì)出現(xiàn)一個(gè)情況：front==rear.如果底層數(shù)據(jù)中elementData［front］==null，則表明此時(shí)隊(duì)列為空，否則表明該隊(duì)列已滿。《/p》《p》隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及實(shí)現(xiàn)《/p》《p》使用鏈?zhǔn)浇Y(jié)構(gòu)保存線性表，也可以采用鏈?zhǔn)浇Y(jié)構(gòu)來存儲(chǔ)隊(duì)列的各元素，采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的隊(duì)列也被稱為鏈隊(duì)列?！?p》《p》對(duì)于鏈隊(duì)列而言，由于程序需要從rear端添加元素，然后從front端移除元素，因此考慮對(duì)鏈隊(duì)列增加front，rear兩個(gè)引用變量，使他們分別執(zhí)行鏈隊(duì)列的頭，尾兩個(gè)節(jié)點(diǎn)。鏈隊(duì)列示意圖如下：《/p》《p》queue_llinked.PNG《/p》《p》由于鏈隊(duì)列采用鏈?zhǔn)浇Y(jié)構(gòu)類保存隊(duì)列中所有元素，該隊(duì)列允許添加無限多個(gè)數(shù)據(jù)元素，因此鏈隊(duì)列無隊(duì)列滿的問題?！?p》《p》1.插入隊(duì)列《/p》《p》對(duì)于鏈隊(duì)列而言，插入操作的實(shí)現(xiàn)非常簡(jiǎn)單，只要?jiǎng)?chuàng)建一個(gè)新節(jié)點(diǎn)，讓原rear節(jié)點(diǎn)的next引用指向新的節(jié)點(diǎn)，再讓rear引用指向該新節(jié)點(diǎn)即可?！?p》《p》queue_linked_insert.PNG 《br》 2.移除隊(duì)列《/p》《p》對(duì)于鏈隊(duì)列而言，移除操作的實(shí)現(xiàn)也非常簡(jiǎn)單，只要讓front引用指向原front所引用節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)即可。當(dāng)然，不要忘記釋放原front節(jié)點(diǎn)的引用。示意圖如下：《/p》《p》queue_linked_delete.PNG 《br》 Java集合中的隊(duì)列《/p》《p》從JDK1.5開始，java的集合框架中提供了一個(gè)queue接口，該接口代表了一個(gè)隊(duì)列，實(shí)現(xiàn)該接口的類可以當(dāng)成隊(duì)列使用。Queue里包含了6個(gè)方法，用于代表隊(duì)列包含的3個(gè)標(biāo)志性的方法，如下所示：《/p》《p》插入：在隊(duì)列的rear端插入元素 《br》 移除：在隊(duì)列的front端刪除元素 《br》 訪問：訪問隊(duì)列的front端元素 《br》 Java為上面的每個(gè)方法方法提供了兩個(gè)版本：具有特殊返回值的版本和拋出異常的版本，這樣就產(chǎn)生了6個(gè)方法?！?p》《p》版本 拋出異常的版本 具有特殊返回值的版本 《br》 插入 add（e） offer（e） 《br》 移除 remove（） poll（） 《br》 訪問 element（） peek（） 《br》 雙端隊(duì)列《/p》《p》雙端隊(duì)列代表一種特殊的隊(duì)列，它可以在兩端同時(shí)進(jìn)行插入，刪除操作，如下圖所示：《/p》《p》double_queue.PNG 《br》 對(duì)于雙端隊(duì)列，由于它可以從兩端分別進(jìn)入插入，刪除操作，如果程序?qū)⑺械牟迦?，刪除操作固定在一端進(jìn)行，這個(gè)雙端隊(duì)列就變成前面介紹的棧，由此可見，Deque和Queue，Stack之間的關(guān)系如圖：《/p》《p》double_queue_relation.PNG 《br》 雙端隊(duì)列（Deque）既可說是Queue的子接口，也可說Stack（JDK并未提供這個(gè)接口）的子接口。因此。Deque即可當(dāng)成隊(duì)列使用，也可當(dāng)成棧使用。《/p》《p》由此可見，Deque其實(shí)就是Queue和Stack混合而成的一種特殊的線性表，完全可以參考起前面的Queue，Stack的實(shí)現(xiàn)類實(shí)現(xiàn)Deque?！?p》《p》JDK為Deque提供了ArrayDeque和LinkedList兩個(gè)常見的實(shí)現(xiàn)類。其中，ArrayDeque代表順序存儲(chǔ)結(jié)構(gòu)的雙端隊(duì)列，LinkedList則代表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的雙端隊(duì)列。《/p》《p》LinkedList代表一種雙向，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的循環(huán)線性表，這里有提到LinkedList代表線程安全的，鏈?zhǔn)浇Y(jié)構(gòu)的雙端隊(duì)列，由此可見，LinkedList實(shí)在是一個(gè)功能非常強(qiáng)大的集合類。事實(shí)上，LinkedList幾乎是Java集合框架中方法最多的類。 《br》 LinkedList_relation.PNG 《br》 雖然LinkedList工具類的功能非常強(qiáng)大，它既可當(dāng)成線性表使用，也可當(dāng)成棧使用，還可當(dāng)成隊(duì)列使用，但對(duì)大部分程序而言，使用ArrayList，ArrayDeque的性能比LinkedList更好?！?p》《p》大家可以點(diǎn)擊加入群：478052716【JAVA高級(jí)程序員】里面有Java高級(jí)大牛直播講解知識(shí)點(diǎn)走的就是高端路線（如果你想跳槽換工作但是技術(shù)又不夠或者工作上遇到了瓶頸我這里有一個(gè)JAVA的免費(fèi)直播課程講的是高端的知識(shí)點(diǎn)基礎(chǔ)不好的誤入喲只要你有1-5年的開發(fā)經(jīng)驗(yàn)可以加群找我要課堂鏈接 注意：是免費(fèi)的 沒有開發(fā)經(jīng)驗(yàn)誤入哦）