队列(下)

Wednesday, April 17, 2019

队列的Swift实现

声明队列协议

<code class="language-swift">public protocol Queue {
    associatedtype Element
    mutating func enqueue(_ element: Element) -> Bool
    mutating func dequeue() -> Element?
    var isEmpty: Bool {get}
    var peek: Element? {get}
}</code>

数组队列

<code class="language-swift">public struct QueueArray<T>: Queue {
    private var array:[T] = []
    public init() {}

    public isEmpty: Bool {
        return array.isEmpty
    }

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

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

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

循环队列

结构

<code class="language-swift">public struct Ring<T> {
    private var array:[T?]
    private var readIndex = 0
    private var writeIndex = 0

    public init(count: T) {
        array = Array<T?>(repeating: nil, count: count)
    }

    public var first: T? {
        return array[readIndex]
    }

    private var availableSpaceForReading: Int {
        return writeIndex - readIndex
    }

    public var isEmpty: Bool {
        return availableSpaceForReading == 0
    }

    private var availableSpaceForWriting: Int {
        return array.count - availableSpaceForReading
    }

    public var isFull: Bool {
        return availableSpaceForWriting == 0
    }

    public mutating func write(_ element: T) -> Bool {
        if !isFull {
            array[writeIndex % array.count] = element
            writeIndex += 1
            return true
        }else {
            return false
        }
    }

    public mutating func read() -> T? {
        if !isEmpty {
            let element = array[readIndex % array.count]
            readIndex += 1
            return element
        }else {
            return nil
        }
    }
}</code>

操作

<code class="language-swift">public struct QueueRingBuffer<T>: Queue {
    private var ringBuffer: RingBuffer<T>

    public init(count: Int) {
        ringBuffer = RingBuffer.init(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()
    }

}
</code>
数据结构-算法

排序(上)

队列(上)