Deque(双向队列)-Swift实现

  • 特性

可以像普通队列一样,拥有从队首出队、从队尾入队的特性外,双向队列,也可以从队首入队,从队尾出队。

  • Swift实现(一般)

struct Deque<T> {
    private var array = [T]()
    //判空
    var isEmpty: Bool {
        return array.isEmpty
    }
    var count: Int {
        return array.count
    }
    //从队尾入队
    mutating func enqueue(_ element: T) {
        array.append(element)
    }
    //从队首入队
    mutating func enqueueFront(_ element: T) {
        array.insert(element, at: 0)
    }
    //从队首出队
    mutating func dequeue() -> T? {
        if isEmpty {
            return nil
        } else {
            return array.removeFirst()
        }
    }
    //从队尾出队
    mutating func dequeueBack() -> T? {
        if isEmpty {
            return nil
        } else {
            return array.removeLast()
        }
    }
    //查看队首元素
    func peekFront() -> T? {
        return array.first
    }
    //查看队尾元素
    func peekBack() -> T? {
        return array.last
    }
}

上面就是对双向队列的简单实现,但是存在如下问题:

  • 1 ,dequeue(队首出队)操作时,由于删除数组中第一个元素,需要将数组中剩余的所有元素,在内存中的位置,统一向前移动一个位置,来填补空白,这个操作的时间复杂度为O(n).
  • 2 ,enqueueFront(队首入队)操作时,由于是在数组的最前面插入一个新的元素,所以需要将数组中原有的所有元素,在内存中的位置,统一向后移动一个位置,这个操作的时间复杂度为O(n).
    上面两种情况,导致上面的双向队列实现的方法,效率有点低,我们需要优化这个问题。

同时我们会疑问,为什么在数组的尾部进行插入和删除操作时,不错在上面的问题呢,这就和Swift中数组的实现机制有关了,在Swift中,在数组初始化后,在数组的最后面面,会预留出一些空的位置,来以备将来在末尾增加新的元素。

//初始化数组
var arr = ["a", "b", "c"]
//实际在数组中情况为
["a", "b", "c", **,  **, **]
//** 就是预留出来的内存,以备将来插入新的元素
arr.append("d")后
// 实际情况为
["a", "b", "c", "d",  **, **]

借鉴上面的思路,我们也可以在双向队列的实现中,自己实现这种类似的机制,来解决问题1,2.

  • Swift实现(稍高效)

struct Deque<T> {
    private var array: [T?]
    
    ///在数组前面预留的空间
    private var spaceCount = 10
    //标记数组中的头部位置
    private var head = 0

    init(_ spaceCount: Int = 10) {
        self.spaceCount = spaceCount
        array = [T?].init(repeating: nil, count: spaceCount)
        head = spaceCount
    }
    
    //判空
    var isEmpty: Bool {
        return count == 0
    }
    
    var count: Int {
        return array.count - head
    }
    
    //从队尾入队
    mutating func enqueue(_ element: T) {
        array.append(element)
    }
    
    //从队首入队
    mutating func enqueueFront(_ element: T) {
        //需要向队首插入新的空位
        if head == 0{
            spaceCount *= 2
            let space = [T?].init(repeating: nil, count: spaceCount)
            array.insert(contentsOf: space, at: 0)
            head = spaceCount
        }
        head -= 1
        array.insert(element, at: head)
    }
    
    //从队首出队
    mutating func dequeue() -> T? {
        //取出队首元素
        guard !isEmpty, let element = array[head] else { return nil }
        array[head] = nil
        //标记数组头部增加1
        head += 1
        
        //定期去除多余的空间
        if head >= spaceCount*2 {
            let amountToRemove = spaceCount + spaceCount/2
            array.removeFirst(amountToRemove)
            head -= amountToRemove
            spaceCount /= 2
        }
        return element
    }
    
    //从队尾出队
    mutating func dequeueBack() -> T? {
        if isEmpty {
            return nil
        } else {
            return array.removeLast()
        }
    }
    //查看队首元素
    func peekFront() -> T? {
        return array.first ?? nil
    }
    //查看队尾元素
    func peekBack() -> T? {
        return array.last ?? nil
    }
}

新的实现方法,主要有以下的几处改变:

  • 1, 数组中的元素由 T 变成了 T?, 这是为了在数组的前面预留空位时,将空位中的元素设置为nil
  • 2,初始化时,在数组的前面预留出一定的空间,来实现我们队首插入操作时,不需要数组中的元素整体后移的思路
  • 3,enqueueFront() 队首入队时,用head标签,来标记当前实际的头部位置,同时当数组前面没有空位的时候,统一的在数组的前面增加空位,增量成倍数增长,这样当插入操作多是,效率更高
  • 4,dequeue() 队首出队的时候,只需要向后移动head标签的位置即可,这样防止每次数组中队首删除元素后,元素统一向前移动,但是防止数组中前面的空位过多浪费空间,我们定期的删除空位。
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 发现 关注 消息 iOS 第三方库、插件、知名博客总结 作者大灰狼的小绵羊哥哥关注 2017.06.26 09:4...
    肇东周阅读 12,259评论 4 61
  • 三乐事 1.第一次拜访客户,虽然情况比较…相当尴尬==咳咳 2.看了电影《猩球崛起》 3.跟发小老妈打电话 4.点...
    李晨睿Charles阅读 126评论 0 0
  • 当你感赏你所拥有的事物,无论他有多小,你都能得到更多同样的事物。 1.感赏两天的充分休息,脑子思路更清晰了,谢谢。...
    吸引力_阿福阅读 173评论 0 1
  • 改变沟通技能是个长期过程,技巧也非常多,但为了能让你在日常中更轻松的学会应用这些技巧,可以利用这个月最后的8天时间...
    筝小钱阅读 3,976评论 1 49
  • 路上永远少不了风景。 无意中看到了上面这个画面,很有感觉,所以就拍了下来。 妹妹在那边专注的玩水,旁边的小朋友恶作...
    zacchen阅读 439评论 0 0