一年前，我在 git 上發布了一個用 Swift 實現的棧，一共有兩個版本。因為 Swift 自身並沒有實現這個東西——儘管官方的教程中泛型的部分就是用這個棧舉的例子。
也許是人家覺得這個太簡單了吧
總之，這次我又來玩這個東西了，因為 HMM 的 Viterbi 算法需要做修剪，不然路徑太多無謂地增加計算量——畢竟，我們都關心第一名，誰會去注意第二名呢？
所以，這個棧也是基於原生 Array 的。幾本思路與普通的棧相同，不過這次我們使用結構體來做。
在 Swift 後台，實際上對於結構體和類區分的不是特別嚴謹，只有真正需要區分的時候才會有不同的行為。這裡 Swift 後台都做了優化。
首先我們還是先擺一個普通的棧：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
struct PriorityStack<Element> { fileprivate var items:[Element] = [] let maxLength:Int init(Length length:Int) {//长度固定，这样栈才能把小的元素自动丢弃 maxLength = length } mutating func push(_ newElement:Element) { } mutating func pop()->Element? { guard count > 0 else {return nil} return items.removeFirst() } func empty() -> Bool { return items.isEmpty } func peek() ->Element? { return items.last } var count:Int { return items.count } } |
這裡沒有什麼區別，對吧？首先，我們要讓元素可以比較，畢竟，你想要給它們排序：
|
1 |
struct PriorityStack<Element:Comparable> { |
所以我們讓泛型限定為遵循 可比 的類型。
接下來就是處理入棧了，這裡我們藉鑑了快速排序和插入排序算法（實際上是我自己設計的排序算法，我是後來才知道的原來有專門的排序算法，而且似乎是各種開發麵試的必考內容……?♂️）
總之，我重新發明了一遍輪子，也不好意思說我自己設計了算法，只好說借鑒了……
大致的流程
1、就是我們先判斷棧是不是滿了，如果滿了且新元素比最小的還小，那麼就丟棄：
|
1 2 3 |
if maxLength == count && newElement < items.last! { return } |
2、如果棧還是空的，那麼直接添加：
|
1 |
if items.isEmpty {items.append(newElement);return} |
3、這下有意思了，我們利用折半思想（其實就是快排的分塊），從數組現有數據數量的中間開始比較如果比中間的值大那麼就往上走，如果小就往下走，直到找到那個合適自己的位置然後插入：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
var middleIndex = Int(count/2) if newElement > items[middleIndex] { while middleIndex >= 0 { if newElement > items[middleIndex] { if middleIndex == 0 {items.insert(newElement, at: 0)} middleIndex -= 1 continue } items.insert(newElement, at: middleIndex + 1) break } } else { while middleIndex < count { if newElement < items[middleIndex] { if middleIndex == count - 1 {items.append(newElement)} middleIndex += 1 continue } items.insert(newElement, at: middleIndex) break } } |
4、最後，如果棧的長度（這裡也許應該說是高度），總之，如果長度等於我們設定的值，這時候又插入了一個有效的（就是比棧裡邊最小值還大的）值，那麼棧的長度就溢出了1，那麼就：
|
1 |
if count > maxLength {items.removeLast()} |
這樣，棧內部的 項目 就是自動排好序的啦！
然後，以防你已經讀懂，我再上個流程圖：
排序算法流程
當然，使用起來可能不是很方便，畢竟有時候我們要獲取這個棧的list，所以，讓它遵循 序列 就很有必要。
序列
這是 Swift 裡的一個協議，所有遵循它的類型就可以被 對於-在 遍歷了，當然，對應的還有比如 地圖 之類的方法也就自動有了，簡單來講就是你可以把它當作一個Array 來對待了！
那麼，怎麼辦呢？如果你點開 Sequence，你會發現聲明的方法太多了——實際上不需要全部去實現，因為 Swift 已經幫你實現好了，你需要做的僅僅是實現這兩個：
|
1 2 |
typealias Iterator func makeIterator() -> PriorityStack.Iterator |
就是這麼簡單！
不過，其實也很難，因為這裡可能有點繞，那就是由於我們並不是要遍歷自身，而是要遍歷棧內部的 Array，所以實現起來很簡單但思路和直接實現 Sequence 不一樣。
首先，你不需要去實現一個遵循 IteratorProtocol 的遍歷器，因為我們的基礎結構就是數組，它自己就有不是嗎？
其次，你也不需要實現 makeIterator() ，原因同上。
所以，我們點開數組的 makeIterator() ，可以看到它返回了一個 IndexingIterator<排列<元件>> ，再點進去看到這是一個結構體——總之，不用管它，我們只要也返回這個類型就好了，然後 makeIterator() 返回基礎數組自身的 makeIterator() 即可，所以，實際上代碼是這樣的：
|
1 2 3 4 5 6 |
extension PriorityStack:Sequence { typealias Iterator = IndexingIterator<Array<Element>> func makeIterator() -> PriorityStack.Iterator { return items.makeIterator() } } |
這下，當你對 PriorityStack 做任何遍歷操作，都相當於是對其內部的數組做了——不需要額外地寫一個getter來取出數組再操作。
那麼，舉個栗子：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
var pStack:PriorityStack<Int> = PriorityStack(Length: 5) pStack.push(1) pStack.push(5) pStack.push(2) pStack.push(8) pStack.push(100) pStack.push(999999) pStack.push(0) print(pStack.maxLength) print("---") for item in pStack { print(item) } let list:[Int] = pStack.map{return $0} print(list) |
然後呢？
好了，這篇總結就到這裡，我已經把我的堆棧在斯威夫特更新了，裡邊加入了這個自動排序棧，你可以去下載然後看一看它的完整代碼。
另外，如果你想了解快排，那麼可以看這裡：http://bubkoo.com/2014/01/12/sort-algorithm/quick-sort/
還有插入排序：https://zh.wikipedia.org/zh-hans/插入排序
本文由 落格博客 原創撰寫：落格博客 » 一個自動排序的 Swift 棧
轉載請保留出處和原文鏈接：https://www.logcg.com/archives/2530.html
