Swift 算法实战之路:栈和队列

212

这期的内容有点剑走偏锋,我们来讨论一下栈和队列。Swift语言中没有内设的栈和队列,很多扩展库中使用Generic Type来实现栈或是队列。笔者觉得最实用的实现方法是使用数组,本期主要内容有:

  • 栈和队列的基本Swift实现,以及在iOS开发中应用的实例
  • Facebook栈相关面试题一道
  • 栈和队列的互相实现及其思想

实现

对于栈来说,我们需要了解以下几点:

  • 栈是后进先出的结构。你可以理解成有好几个盘子要垒成一叠,哪个盘子最后叠上去,下次使用的时候它就最先被抽出去。
  • 在iOS开发中,如果你要在你的App中添加撤销操作(比如删除图片,恢复删除图片),那么栈是首选数据结构
  • 无论在面试还是写App中,只关注栈的这几个基本操作:push, pop, isEmpty, peek, size。

    对于队列来说,我们需要了解以下几点:
  • 队列是先进先出的结构。这个正好就像现实生活中排队买票,谁先来排队,谁先买到票。
  • iOS开发中多线程的GCD和NSOperationQueue就是基于队列实现的。
  • 关于队列我们只关注这几个操作:enqueue, dequeue, isEmpty, peek, size。

实战

下面是Facebook一道真实的面试题。

这道题目一看,这不就是我们平常在terminal里面敲的cd啊pwd之类的吗,好熟悉啊。

根据常识,我们知道以下规则:

  • . 代表当前路径。比如 /a/. 实际上就是 /a,无论输入多少个 . 都返回当前目录
  • ..代表上一级目录。比如 /a/b/.. 实际上就是 /a,也就是说先进入a目录,再进入其下的b目录,再返回b目录的上一层,也就是a目录。

然后针对以上信息,我们可以得出以下思路:

  1. 首先输入是个 String,代表路径。输出要求也是 String, 同样代表路径。
  2. 我们可以把 input 根据 “/” 符号去拆分,比如 “/a/b/./../d/” 就拆成了一个String数组[“a”, “b”, “.”, “..”, “d”]
  3. 创立一个栈然后遍历拆分后的 String 数组,对于一般 String ,直接加入到栈中,对于 “..” 那我们就对栈做pop操作,其他情况不错处理

思路有了,代码也就有了

上面代码除了完成了基本思路,还考虑了大量的特殊情况、异常情况。这也是硅谷面试考察的一个方面:面试者思路的严谨和代码的风格规范。
队列会在以后讲树遍历和图的广度优先遍历时大放异彩,所以本期队列先按下不表。

转化

处理栈和队列问题,最经典的一个思路就是使用两个栈/队列来解决问题。也就是说在原栈/队列的基础上,我们用一个协助栈/队列来帮助我们简化算法,这是一种空间换时间的思路。比如

用栈来实现队列

用队列实现栈

上面两种实现方法都是使用两个相同的数据结构,然后将元素由其中一个转向另一个,从而形成一种完全不同的数据。

总结

Swift中栈和队列是比较特殊的数据结构,个人认为最实用的实现方法是利用数组。虽然它们本身比较抽象,却是很多复杂数据结构和iOS开发中的功能模块的基础。这也是一个工程师进阶之路理应熟练掌握的两种数据结构。

1 收藏 评论

相关文章

可能感兴趣的话题



直接登录
跳到底部
返回顶部