Swift 數(shù)據(jù)結(jié)構(gòu) - 棧和隊(duì)列

棧（Stack）

棧（stack）是限制對(duì)元素的插入（push）和刪除（pop）只能在一個(gè)位置上進(jìn)行的表，該位置是表的末端，叫做棧的棧頂（top)。

進(jìn)棧和出棧

基于棧結(jié)構(gòu)的特點(diǎn)，在實(shí)際應(yīng)用中，通常只會(huì)對(duì)棧執(zhí)行以下兩種操作：

  • 向棧中添加元素，此過(guò)程被稱為"進(jìn)棧"（入?；驂簵＃?；
  • 從棧中提取出指定元素，此過(guò)程被稱為"出棧"（或彈棧）；

棧的實(shí)現(xiàn)

棧是一種 "特殊" 的線性存儲(chǔ)結(jié)構(gòu)，因此棧的具體實(shí)現(xiàn)有以下兩種方式：

  1. 順序棧：采用順序存儲(chǔ)結(jié)構(gòu)可以模擬棧存儲(chǔ)數(shù)據(jù)的特點(diǎn)，從而實(shí)現(xiàn)棧存儲(chǔ)結(jié)構(gòu)；
  2. 鏈棧：采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)棧結(jié)構(gòu)；

1. 數(shù)組實(shí)現(xiàn)

public struct Stack<T> {
  fileprivate var array = [T]()

  public var isEmpty: Bool {
    return array.isEmpty
  }

  public var count: Int {
    return array.count
  }

  public mutating func push(_ element: T) {
    array.append(element)
  }

  public mutating func pop() -> T? {
    return array.popLast()
  }

  public var top: T? {
    return array.last
  }
}

注意到，壓棧操作是將新元素壓入數(shù)組的尾部，而不是頭部。在數(shù)組的頭部插入元素是一個(gè)很耗時(shí)的操作，它的時(shí)間復(fù)雜度為 O(n)，因?yàn)樾枰獙F(xiàn)有元素往后移位為新元素騰出空間。而在尾部插入元素的時(shí)間復(fù)雜度為 O(1)；無(wú)論數(shù)組有多少元素，這個(gè)操作所消耗的時(shí)間都是一個(gè)常量。

2. 鏈表實(shí)現(xiàn)
這里我們使用單鏈表來(lái)實(shí)現(xiàn)，定義一個(gè)first指針指向棧頂，棧的鏈表實(shí)現(xiàn)實(shí)際上是簡(jiǎn)化了單鏈表實(shí)現(xiàn)，具體實(shí)現(xiàn)看以下代碼。

/// 鏈表節(jié)點(diǎn)類
public class ListNode<T> {
    var value: T  // 值
    var next: ListNode<T>? = nil // 下一個(gè)節(jié)點(diǎn)
    weak var previous: ListNode<T>? = nil
    init(value: T) {
        self.value = value
    }
}

public class StackList<T> {
    public var count: Int = 0
    public var first: ListNode<T>?
    
    public var isEmpty: Bool {
      return count == 0
    }
    
    public func push(_ element: T) {
        let oldNode = first
        first = ListNode(value: element)
        first?.next = oldNode
        count += 1
    }
    
    public func pop() -> T? {
        let value = first?.value
        first = first?.next
        count -= 1
        return value
    }
}

隊(duì)列（queue）

wiki: 隊(duì)列，又稱為佇列（queue），是先進(jìn)先出（FIFO, First-In-First-Out）的線性表。在具體應(yīng)用中通常用鏈表或者數(shù)組來(lái)實(shí)現(xiàn)。隊(duì)列只允許在后端（稱為rear）進(jìn)行插入操作，在前端（稱為front）進(jìn)行刪除操作。隊(duì)列的操作方式和堆棧類似，唯一的區(qū)別在于隊(duì)列只允許新數(shù)據(jù)在后端進(jìn)行添加。

多種隊(duì)列

隊(duì)列一般分為普通的數(shù)組隊(duì)列，鏈表隊(duì)列和循環(huán)隊(duì)列。

鏈表隊(duì)列：長(zhǎng)度一般是無(wú)限的，一般不存在溢出的可能性，用完就銷毀，不會(huì)浪費(fèi)內(nèi)存空間。

普通的數(shù)組隊(duì)列：長(zhǎng)度一般是有限的，即數(shù)組長(zhǎng)度。由于元素出隊(duì)后其位置的內(nèi)存空間并不會(huì)釋放，因此會(huì)浪費(fèi)大量的內(nèi)存空間。


image.png

循環(huán)隊(duì)列：特殊的數(shù)組隊(duì)列，由于普通的數(shù)組的隊(duì)列會(huì)浪費(fèi)大量的內(nèi)存空間，因此出現(xiàn)了循環(huán)隊(duì)列。當(dāng)循環(huán)隊(duì)列的隊(duì)尾指針到達(dá)數(shù)組末尾后，會(huì)重新回到數(shù)組起始位置，實(shí)現(xiàn)了對(duì)內(nèi)存的重復(fù)利用。


image.png

隊(duì)列的實(shí)現(xiàn)

1. 數(shù)組隊(duì)列

public struct Queue<T> {
  fileprivate var array = [T]()

  public var isEmpty: Bool {
    return array.isEmpty
  }
  
  public var count: Int {
    return array.count
  }

  public mutating func enqueue(_ element: T) {
    array.append(element)
  }
  
  public mutating func dequeue() -> T? {
    if isEmpty {
      return nil
    } else {
      return array.removeFirst()
    }
  }
  
  public var front: T? {
    return array.first
  }
}

2. 鏈表隊(duì)列

/// 鏈表節(jié)點(diǎn)類
public class ListNode<T> {
    var value: T? // 值
    var next: ListNode<T>? = nil // 下一個(gè)節(jié)點(diǎn)
    weak var previous: ListNode<T>? = nil
    init(value: T?) {
        self.value = value
    }
}

public class QueueByLinkList<T> {
    public var count: Int = 0
    public var first: ListNode<T>?
    public var last: ListNode<T>?
    
    public var isEmpty: Bool {
      return count == 0
    }
    
    //初始化隊(duì)列
    init() {
        first = ListNode(value: nil)
        last = first
        count = 0
    }
    
    //入隊(duì)
    public func enqueue(_ element: T) {
        if isEmpty {
            last?.value = element
            count += 1
            return
        }
        let oldNode = last
        last = ListNode(value: element)
        oldNode?.next = last
        count += 1
    }
    
    //出隊(duì)
    public func dequeue(_ element: T) -> T? {
        if isEmpty {
            print("***隊(duì)列為空***")
            return nil
        }
        let value = first?.value
        first = first?.next
        count -= 1
        return value
    }
}

3. 循環(huán)隊(duì)列

public struct CycleQueue<T> {
    fileprivate var queue = [T]()
    fileprivate var queue_Capacity: Int = 0
    
    var count: Int {
        return queue.count
    }
    
    // 構(gòu)造函數(shù)創(chuàng)建出一個(gè)隊(duì)列數(shù)據(jù)模型來(lái)
    init(queue_Capacity: Int) {
        self.queue_Capacity = queue_Capacity
        self.clearQueue()
    }
    
    /// 清空隊(duì)列
    public mutating func clearQueue() {
        queue.removeAll()
    }
    
    /// 判斷隊(duì)列是否已經(jīng)滿了
    public func queueFull() -> Bool {
        return queue_Capacity == count
    }
    
    var isEmpty: Bool {
        return queue.isEmpty
    }

    /// 往隊(duì)列中添加一個(gè)元素
    public mutating func enQueue(_ element : T) -> Bool {
        if queueFull() {
            print("隊(duì)列已滿")
            return false
        } else {
            queue.append(element)
            return true
        }
    }
  
    /// 從隊(duì)列中取出來(lái)一個(gè)元素 如果隊(duì)列為空 那么 取出來(lái)的為 nil
    public mutating func deQueue() -> T? {
         if isEmpty {
            return nil
        } else {
            let element = queue.removeFirst()
            return element
        }
    }
     /// 遍歷隊(duì)列
    public func queueTraverse() {
        if isEmpty {
            print("隊(duì)列為空")
        } else {
            queue.forEach { (element) in
                print("element: \(element)")
            }
        }
    }
}

參考文章
淺談棧和隊(duì)列

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容