資料結構中的棧與隊列還是經常使用的，棧與隊列其實就是線性表的一種應用。因為線性隊列分為順序存儲和鍊式存儲，是以棧可以分為鍊棧和順序棧，隊列也可分為順序隊列和鍊隊列。本篇部落格其實就是《資料結構之線性表的順序存儲于鍊式存儲（Swift面向對象版）》這篇部落格的應用。本篇部落格會分别給出隊列的順序和鍊式存儲，以及棧的順序和鍊式存儲。
說到棧和隊列這兩種資料結構，了解起來應該不難。隊列就是進行排隊的資料結構，一個隊列肯定是線性結構了，之是以稱之為隊列，是因為有着先入先出（FIFO ----first in first out）的特性。就像你去銀行辦業務排隊時，你先排的隊當然是你先辦理業務，那些後排隊的要在你後邊辦業務。而棧就與隊列相反了，棧具有先入後出（FILO -- first in last out）的特性。在現實生活中手槍的子彈夾就是棧的結構，最先進去的子彈會最後才射出。當然在我們做iOS開發時，會經常使用到導航棧，而導航棧中存儲的就是你之前Push進的頁面，也是先入後出的特性。關于棧和隊列，下方會給出詳細的介紹。
一、棧與隊列的綜述
棧與隊列毫無疑問都是線性結構的，分别适用于不同的場景。部落格的本部分會給出棧與隊列的總體介紹，然後分别給出其實作方案。當然下方在棧與隊列的實作中，我們依然采用“面向接口”程式設計的思想，會先定義棧與隊列的相關接口，然後給出棧與隊列的不同實作方案。
下方這個就是一個典型的隊列的結構。需要加入隊列中的元素是往隊尾添加的，而需要出隊的元素從隊頭出。這樣出隊列的順序與進入隊列的順序是一緻的。這也就是隊列的特性，先入先出。之前我們在聊GCD的中的隊列的時候也同樣适應這個特性。在GCD中無論是串行隊列還是并行隊列，其都遵循隊列“先入先出”的規則。
上面我們簡單的聊了一下隊列，接下來我們來簡單的聊一下棧。在部落格的開頭也提到了，彈構就是棧結構。彈夾中的子彈就是棧中的元素，遵循着先入後出的原則。下方這個示例圖就是一個典型的棧型結構。在棧中有一個指針Top，永遠指向棧頂元素，如果棧為空，那麼Top就為nil。在棧結構中無論是入棧還是出棧，都是操作棧頂元素。是以入棧順序與出棧順序是相反的。
二、線性隊列和鍊式隊列的實作
聊完原理，接下來我們就要來進行代碼實作了。下方将會給出具體的隊列的實作代碼，并給出相應的測試用例。當然我們依然是采用面向對象的思想來實作的隊列的。在看具體代碼之前，我們先來看一下我們本篇部落格所涉及Demo的具體目錄。最上面的框是兩個協定，StackProtocol中聲明了棧結構所涉及的操作，所有棧都要遵循該協定。QueueProtocol聲明了隊列中所涉及的所有操作，隊列的實作都要遵循該隊列協定。
這樣做的好處就是所有類型的棧可以共用棧的測試用例，而隊列也是如此。下方就是我們測試用例的調用方式，需要測棧時，就給棧的測試用例傳入相應棧的對象，隊列也是一樣。也就能明顯看出面向接口程式設計的好處。
1.隊列協定：QueueType
在具體實作隊列之前，我們先定義隊列的接口。此處我們要定義的就是QueueType協定，在QueueType中聲明的是隊列的全部操作。無論是棧隊列，還是順序隊列都必須要遵循該接口，而在外部聲明隊列類型時，我們一般會使用QueueType來聲明隊列類型。類型為QueueType的隊列可以被指派為遵循QueueType協定的類的任何對象。下方就是QueueType協定中的内容。
從下方的代碼段中，我們顯然可以看出QueueType協定就是指派為我們的隊列實作定制大綱的。有了這個大綱，具體隊列的實作要按照下方這個大綱來。至于隊列的具體實作細節，QueueType協定并不關心，QueueType關系的是隊列對外的使用方式。
2.順序隊列
接下來我們就依據上述的隊列的協定，給出順序隊列的具體實作代碼。順序隊列我們就以Swift中的數組類型來代替了。enQueue--入隊列所對應的操作就是往數組的尾部添加資料，而deQeueu--出隊列操作就是将數組第一個元素進行移除并傳回移除的值即可。下方就是入隊列和出隊列的操作，如下所示。隊列的其他操作在此就不做過多贅述了，請參考github上分享的代碼。
3.鍊式隊列
鍊式隊列其實就是連結清單的一種使用方式。鍊式隊列就是講隊列元素以連結清單的形式進行存儲，并且規定隻能從連結清單的尾部添加元素，從連結清單的頭部移除元素。關于連結清單的各種操作請參考上篇部落格《資料結構之線性表的順序存儲于鍊式存儲（Swift面向對象版）》中介紹的内容。該部分就是連結清單在隊列中的應用。與上面的内容類似，下方是鍊式隊列的核心操作，下方截圖中的代碼段是鍊式隊列中出隊列和入隊列的操作了。如下所示：
4.隊列的測試用例
上面我們分别實作了鍊式隊列和順序隊列，接下來我們将會對上面這兩種隊列進行測試。由于上面這兩種隊列有種統一的對外調用接口，也就是這兩種隊列都遵循QeueuType這個隊列協定。是以在測試隊列時我們可以使用同一個測試用例，這也就是“面向接口程式設計”的好處。當我們再引入其他隊列的具體實作方案時，隻需要将新引入的隊列解決方案遵循我們之前定義的QueueType接口即可，我們的測試用例仍然好用。從這一點我們就能看出“面向接口”程式設計的可維護性和高擴充性。
下方就是我們隊列的測試用例, 函數的參數是QueueType的類型。也就是隻要遵循QueueType協定的所有類的對象都可以作為該函數的參數。最下方的兩行代碼是該函數的調用方式。第一個傳入的是順序隊列的對象，所有測試的就是順序隊列相關代碼。而第二個傳入的是棧隊列的對象，那麼測試的就是棧隊列的相關代碼。
下方就是測試用例的運作結果，先将a, b出隊列，然後将x,y,x如隊列。
三、棧的順序存儲與鍊式存儲
上面已經聊完隊列的相關内容了，接下來我們在按照上面的方式來聊一下棧的内容。再重複一遍棧的規則：先入後出。先入後出是棧的特定，當然棧也屬于邏輯結構中線性結構，基于線性結構的特定，是以棧也是有這鍊式和順序存儲的結構的。下方将會給出棧的這兩種實作。在具體實作不同類型的棧時，我們還是依照“面向接口”程式設計的思想，先定義出棧的協定StackType。StackType協定中定義了棧的所有相關操作，棧的具體實作要遵循該協定。這樣做的好處就不做過多贅述了。
1.棧協定StackType的定義
首先我們還是來定義棧的接口StackType。下方截圖中的代碼段就是我們定義好的棧的接口，也就是Swift語言中的協定。從下方協定中我們不難看出，隻聲明了方法，而沒有具體實作。具體實作我們放在不同類型的棧中去做。因為具體實作的棧要對外統一調用接口，是以必須遵循StackType協定。
2.棧的順序存儲實作
定義完棧的協定後，我們就該遵循該協定給出具體的實作了，接下來我們要給出順序棧的實作方式。此處為了簡單期間，我們就使用Swift的數組（Array）變量來實作。當然入棧和出棧操作都是借助Array自帶的操作來實作的。下方截圖中就是順序棧中入棧（push）和出棧（pop）的操作。因為我們借助了Array本身的操作，也就是Array為我們做了許多事情，是以實作起來就比較簡單了。
下方就是順數棧的主要操作，push()方法就是将該函數的參數進行入棧操作。其實就是調用的Array的append()方法，将該參數存入到數組的最後一個位置。而pop()方法負責移除并傳回棧頂元素，此處我們借用了Swift語言中的Array的removeLast()方法，來移除數組的最後一個元素，然後将這個元素進行傳回。從上述操作步驟來看，棧的特點就是對棧頂元素進行操作。
3. 棧的鍊式存儲實作
上面的順序存儲，我們使用的是順序存儲，借助了Array來實作的，是以操作起來比較簡單。棧的鍊式存儲操作起來會相對麻煩一些，不過這些操作在上篇部落格中已經進行了詳細的介紹，是以對本篇部落格來說并非難事。
下方這段代碼就是鍊式存儲的棧的核心操作。push()方法指派的就是往棧中添加新的元素，首先會建立一個新的結點，然後添加到棧頂元素中。棧頂元素我們用top指針來進行标記。入棧後我們還要将棧的長度進行加一操作。然後就是pop()出棧操作了，首先會判斷棧是否為空，如果不為空就傳回棧頂元素，并将棧頂元素進行移除。移除棧頂元素後需要将top指針指向新的棧頂并将棧中的元素進行減一操作。具體代碼如下所示。
4.棧的測試用例
因為上述我們棧的實作都遵循了我們事先定義好的StackType協定，是以上述兩種類型的棧可以使用一個測試用例。這一點與上述隊列的測試用例是一緻的，接下來我們将要來測試我們的棧。下方testStack()函數就是我們棧的測試函數，函數的參數類型是StackType。所有遵循StackType協定的棧的對象都可以作為該函數的參數。最後兩行是函數的調用方式，第一個傳入的是順序棧的對象，第二個傳入的參數是鍊棧的對象。
由上面這段代碼可看出，該測試用例是适用于StackType系列的棧。下方就是測試用例的輸出結果，輸出結果還算是直覺形象，是以在此就不做過多的贅述了。
至此呢，我們的棧與隊列的順序存儲和鍊式存儲就聊完了。當然，本篇部落格隻是拿出了Demo的一部分來講的，更完整的示例還是看github上分享的Demo吧。
github分享位址：https://github.com/lizelu/DataStruct-Swift/tree/master/StackAndQueue
作者：青玉伏案
出處：http://www.cnblogs.com/ludashi/
本文版權歸作者和共部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接，否則保留追究法律責任的權利。
如果文中有什麼錯誤，歡迎指出。以免更多的人被誤導。
收履歷：某網際網路公司，招聘iOS/Android靠譜工程師，入職後，可内部聯系樓主，有小禮品贈送，有意者可郵箱投遞履歷：[email protected]