队列(Queue)是另一个类似Array但是相当内敛的闺秀,是栈(Stack)的妹妹,听说她最近当了王后(Queen)~

和栈的先来后走正相反,她崇尚的是先来先走。

只能在队列尾部进(enqueue)一个元素,在头部出(dequeue)一个元素,看(peek)也只能看头。

看例子:

[Swift] 纯文本查看 复制代码
queue.enqueue(10)   // 队列里来了第一个成员10, 队列成了[ 10 ]
queue.enqueue(3)    // 现在是[ 10, 3 ]
queue.enqueue(57)   // 现在是[ 10, 3, 57 ]

queue.dequeue()     // 最先来的那位走了,现在是[ 3, 57 ],这个函数返回走了的10
queue.dequeue()     // 返回3,现在是[ 57 ]


如果队列空了再dequeue,就会返回nil,有的实现会直接给个错误信息(“没了”)。

注:如果不是一定要先来先走,我更喜欢姐姐,栈,姐姐比妹妹更简单、高效。

我们可以像实现栈那样,对Array简单包装来实现队列:

[Swift] 纯文本查看 复制代码
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 func peek() -> T? {
        return array.first
    }
}


这个实现不错,但在效率上有些缺憾。

虽然入队是个常数级复杂度的操作,但是出队却是线性复杂度的。因为头部的元素出队后,其他所有剩余元素都需要往前移一步。

让我们尽量避免移动来修正一下:

[Swift] 纯文本查看 复制代码
public struct Queue<T> {
    fileprivate var array = [T?]()
    fileprivate var head = 0
    
    public var isEmpty: Bool {
        return count == 0
    }
    
    public var count: Int {
        return array.count - head
    }
    
    public mutating func enqueue(_ element: T) {
        array.append(element)
    }
    
    public mutating func dequeue() -> T? {
        guard head < array.count, let element = array[head] else { return nil }
        
        array[head] = nil
        head += 1
        
        let percentage = Double(head)/Double(array.count)
        if array.count > 50 && percentage > 0.25 {
            array.removeFirst(head)
            head = 0
        }
        
        return element
    }
    
    public func peek() -> T? {
        if isEmpty {
            return nil
        } else {
            return array[head]
        }
    }
}


现在array里的元素是T?而不是原来的T。这样我们就可以用nil来表示数组那个位置没有元素,再用head变量,保证永远代表第一个元素的索引,这样一来就避免了在出队时移动元素。

当然,如果永不真正移除数组里的那些nil,我们的王后就会像她姐栈会“爆栈”一样,“爆队”给我们看。

数据结构:Queue

数据结构:Queue - 敏捷大拇指 - 数据结构:Queue


所以我们要在适当的时候,真正移除元素,就像这段代码做的:

[Swift] 纯文本查看 复制代码
let percentage = Double(head)/Double(array.count)
if array.count > 50 && percentage > 0.25 {
    array.removeFirst(head)
    head = 0
}


算一下nil在整个array里的比例,如果大于四分之一且数组总长度大于50,就真的移除head及之前的元。

0.25啊50啊这些数字要因情况而定,具体定多少,看你。

测试一下改进后的队列:

[Swift] 纯文本查看 复制代码
var q = Queue<String>()
q.array                   // []

q.enqueue("Ada")
q.enqueue("Steve")
q.enqueue("Tim")
q.array             // [{Some "Ada"}, {Some "Steve"}, {Some "Tim"}]
q.count             // 3

q.dequeue()         // "Ada"
q.array             // [nil, {Some "Steve"}, {Some "Tim"}]
q.count             // 2

q.dequeue()         // "Steve"
q.array             // [nil, nil, {Some "Tim"}]
q.count             // 1

q.enqueue("Grace")
q.array             // [nil, nil, {Some "Tim"}, {Some "Grace"}]
q.count             // 2


改进后的队列很棒,出队操作也变成了平均情况下的常数级。

队列还有很多实现方式,比如可以基于链表(linked list)、环状缓存(circular buffer)或堆(heap)来做,或者双向链表,或者排序队列等。你能想到的,都可以燃烧一把。




原作者: Matthijs Hollemans