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