Chapter 8: Queues

前言

Queue是FIFO的資料結構，本章會介紹4種不同實作方式來實作queue，並分析其時間複雜度。

大綱

• Common operations

• Array-based implementation

• Doubly linked list implementation

• Ring buffer implementation

• Double-stack implementation

Common operations

• Queue常見的基本操作

  • Enqueue: 插入元素到queue的做末端，如果插入成功回傳true

  • Dequeue: 移除queue的最前端元素，並回傳此元素

  • isEmpty: 判斷queue是否為空

  • Peek: 回傳queue最前端元素，並沒有移除

public protocol Queue {
  associatedtype Element

  mutating func enqueue(_ element: Element) -> Bool
  mutating func dequeue() -> Element?
  var isEmpty: Bool { get }
  var peek: Element? { get }
}

Array-based implementation

• 利用Array來實作Queue

public struct QueueArray<T>: Queue {
    private var array: [T] = []
    public init() {}

    public var isEmpty: Bool {
        return array.isEmpty
    }

    public var peek: T? {
        return array.first
    }

    public mutating func enqueue(_ element: T) -> Bool {
        array.append(element)
        return true
    }

    public mutating func dequeue() -> T? {
        return isEmpty ? nil : array.removeFirst()
    }
}

• 優缺點

  • enqueue快速，但萬一遇到array滿了，就會有額外的工在進行resiz。

  • dequeue慢，每次搬移後都需要將array中的元素進行shift的動作。

Doubly linked list implementation

• Doubly linked list是利用有紀錄previos跟next的node進行實作。

public class QueueLinkedList<T>: Queue {

    private var list = DoublyLinkedList<T>()
    public init() {}

    public func enqueue(_ element: T) -> Bool {
        list.append(element)
        return true
    }

    public func dequeue() -> Element? {
        guard !list.isEmpty, let element = list.first else {
            return nil
        }

        return list.remove(element)
    }

    public var isEmpty: Bool {
        return list.isEmpty
    }

    public var peek: T? {
        return list.first?.value
    }

}

• 優缺點

  • Doubly linked list的dequeu只需要O(1)，Array-based需要O(n)。

  • list中每個元素都需要額外紀錄前一個跟後一個元素的reference。

    • Moreover, every time you create a new element, it requires a relatively expensive dynamic allocation. By contrast QueueArray does bulk allocation, which is faster.

Ring buffer implementation

• Ring buffer - circular buffer, is a fixed-size array, 用來優化Doubly linked list的空間複雜度。

  • The read pointer keeps track of the front of the queue.

  • The write pointer keeps track of the next available slot so that you can override existing elements that have already been read

  • 當read和write在相同的index時，表示queue是empty

public struct QueueRingBuffer<T>: Queue {
    private var ringBuffer: RingBuffer<T>

    public init(count: Int) {
        ringBuffer = RingBuffer<T>(count: count)
    }

    public var isEmpty: Bool {
        return ringBuffer.isEmpty
    }

    public var peek: T? {
        return ringBuffer.first
    }

    public mutating func enqueue(_ element: T) -> Bool {
        return ringBuffer.write(element)
    }

    public mutating func dequeue() -> T? {
        return isEmpty ? nil : ringBuffer.read()
    }
}

• 優缺點

  • 跟link list有相同的性能。

  • 唯一不同的是空間複雜度，ring buffer是固定size, 所以有可能出現euqueue失敗的情況。

Double-stack implementation

• 利用兩個stack實作queue

  • 當要enqueue，就在right stack放入元素。

  • 當要dequeue, 就把right stack中所有元素進行反轉，然後放入左邊stack, 就達成FIFO的目的。

public struct QueueStack<T>: Queue {
    private var leftStack: [T] = []
    private var rightStack: [T] = []

    public init() {}

    public var isEmpty: Bool {
        return leftStack.isEmpty && rightStack.isEmpty
    }

    public var peek: T? {
        return leftStack.isEmpty ? rightStack.first : leftStack.last
    }

    public mutating func enqueue(_ element: T) -> Bool {
        rightStack.append(element)
        return true
    }

    public mutating func dequeue() -> T? {
        // 表示之前沒有任何deqeue動作，或者已經deqeue多次了
        if leftStack.isEmpty {
            leftStack = rightStack.reversed()
            rightStack.removeAll()
        }

        return leftStack.popLast()
    }
}

• 優缺點

  • 跟array相比，利用兩個stack來優化dequeue效能。

  • two-stack implementation is fully dynamic and doesn’t have the fixed size restriction that your ring-buffer-based queue implementation has.

  • It beats the linked list in terms of spacial locality

    • A linked list wherein the elements aren’t in contiguous blocks of memory. This could lead to more cache misses, which will increase access time