iOS 数据结构之队列

关键时刻，第一时间送达！

作者：大兵布莱恩特

链接：https://www.jianshu.com/p/d979f70c9ed1

程序员共读整理发布，转载请联系作者获得授权

队列是iOS 中常见的一种数据结构,比如 NSOpeartionQueue 和 GCD 的 各种队列 ,其特点是先进先出(First In First out), 在多线程执行执行多个任务时候 ,放进同一队列的任务是顺次从队列里取出任务并执行的.

gith 代码仓库 : https://github.com/ZhaoBingDong/iOS-DataStructures.git

队列在我们生活中也很常见,比如排队购票 去银行办理业务排队办理业务,都是队首的办理完业务后,离开柜台 下一个人接着办理业务

本文我们将介绍两种队列实现方式, 数组队列和循环队列.

数组队列是利用我们已经写好的数据结构 ArrayList 来存放元素,每次入队时候 往数组后边添加一个元素,每次出队时候从数组第0个元素位置出队一个元素,但是用数组队列其缺点是 在出队时候 数组里所有元素都要整体往前移动1个位置

数组和循环队列所有方法如下

循环队列当出队一个元素后,不需要队列里所有元素往前移动,只需要移动队列 _front 和 _tail 指向的位置 , 可以复用已经出队元素留下的内存空间 ,类似与一个环形 , 其内部实现也是一个数组用来存放入队的元素, 当入队元素个数小于数组元素时 就会将元素放到一个空的内存空间位置,只需要维护下_front 和 _tail 指向位置 用来区分队首和队尾

测试用例 由于数组队列需要出队和入队时候需要频繁的移动数组里元素索引位置 ,这个操作时耗时的 ,而循环队列只需要把新入队的元素 存放在一个空的位置即可 ,减少了对数组内部元素的移动的操作.因此循环队列比数组队列时间耗时更少 性能更好

测试用例对比如下