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

分享到:  QQ好友和群QQ好友和群 QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友 微信微信
查看查看201 回复回复1 收藏收藏 分享淘帖 转播转播 分享分享 微信
查看: 201|回复: 1
收起左侧

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

[复制链接]
大秘小蜜 发表于 2016-6-21 17:18:38 | 显示全部楼层 |阅读模式
快来登录
获取最新的苹果动态资讯
收藏热门的iOS等技术干货
拷贝下载Swift Demo源代码
本帖最后由 大秘小蜜 于 2016-6-21 17:25 编辑

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

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


当然要想了解更多Swift知识点或面试题,可以多访问全球最大的Swift开发者社区——敏捷大拇指http://www.Swifthumb.com

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

Swift 算法实战之路:栈和队列 - 敏捷大拇指 - Swift 算法实战之路:栈和队列





1、实现

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

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


[Swift] 纯文本查看 复制代码
class Stack {
  var stack: [AnyObject]

  init() {
    stack = [AnyObject]()
  }

  func push(object: AnyObject) {
    stack.append(object)
  }

  func pop() -> AnyObject? {
    if !isEmpty() {
      return stack.removeLast()
    } else {
      return nil
    }
  }

  func isEmpty() -> Bool {
    return stack.isEmpty
  }

  func peek() -> AnyObject? {
    return stack.last
  }

  func size() -> Int {
    return stack.count
  }
}


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

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


[Swift] 纯文本查看 复制代码
class Queue {
  var queue: [AnyObject]

  init() {
    queue = [AnyObject]()
  }

  func enqueue(object: AnyObject) {
    queue.append(object)
  }

  func dequeue() -> AnyObject? {
    if !isEmpty() {
      return queue.removeFirst()
    } else {
      return nil
    }
  }

  func isEmpty() -> Bool {
    return queue.isEmpty
  }

  func peek() -> AnyObject? {
    return queue.first
  }

  func size() -> Int {
    return queue.count
  }
}





2、实战

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

Given an absolute path for a file (Unix-style), simplify it.
For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"

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

Swift 算法实战之路:栈和队列 linux-current-working-directory

Swift 算法实战之路:栈和队列 - 敏捷大拇指 - Swift 算法实战之路:栈和队列 linux-current-working-directory


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

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


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

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


思路有了,代码也就有了:

[Swift] 纯文本查看 复制代码
func simplifyPath(path: String) -> String {
  var res = ""
  // 用数组来实现栈的功能
  var stack = [String]()
  // 拆分原路径
  let paths = path.characters.split {$0 == "/"}.map(String.init)

  for path in paths {
    // 注意要trim处理头尾空格的情况,Swift 3.0语法在trim上会更简洁
    var path = path.stringByTrimmingCharactersInSet(NSCharacterSet.whitespaceCharacterSet())
    // 对于 "." 我们直接跳过        
    guard path != "." else {
      continue
    }
    // 对于 ".." 我们使用pop操作        
    if path == ".."  {
      if (stack.count > 0) {
        stack.removeLast()
      }
    // 对于太注意空数组的特殊情况
    } else if path.characters.count > 0 {
      stack.append(path)
    }
  }
  // 将栈中的内容转化为优化后的新路径      
  for str in stack {
    res += "/"
    res += str
  }

  // 注意空路径的结果是 "/"      
  return res.isEmpty ? "/" : res
}


上面代码除了完成了基本思路,还考虑了大量的特殊情况、异常情况。这也是硅谷面试考察的一个方面:面试者思路的严谨和代码的风格规范。

队列会在以后讲树遍历和图的广度优先遍历时大放异彩,所以本期队列先按下不表。




3、转化

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

用栈来实现队列

[Swift] 纯文本查看 复制代码
class MyQueue {
  var stackA: Stack
  var stackB: Stack

  init() {
    stackA = Stack()
    stackB = Stack()
  }

  func enqueue(object: AnyObject) {
    stackA.push(object);
  }

  func dequeue() -> AnyObject? {
    _shift()
    return stackB.pop();
  }

  func peek() -> AnyObject? {
    _shift();
    return stackB.peek();
  }

  func isEmpty() -> Bool {
    return stackA.isEmpty() && stackB.isEmpty();
  }

  func size() -> Int {
    return stackA.size() + stackB.size()
  }

  private func _shift() {
    if stackB.isEmpty() {
      while !stackA.isEmpty() {
        stackB.push(stackA.pop()!);
      }
    }
  }
}


用队列实现栈

[Swift] 纯文本查看 复制代码
class MyStack {
  var queueA: Queue
  var queueB: Queue

  init() {
    queueA = Queue()
    queueB = Queue()
  }

  func push(object: AnyObject) {
    queueA.enqueue(object)
  }

  func pop() -> AnyObject? {
    _shift()
    let popObject = queueA.dequeue()
    _swap()
    return popObject
  }

  func isEmpty() -> Bool {
    return queueA.isEmpty()
  }

  func peek() -> AnyObject? {
    _shift()
    let peekObject = queueA.peek()
    queueB.enqueue(queueA.dequeue()!)
    _swap()

    return peekObject
  }

  func size() -> Int {
    return queueA.size()
  }

  private func _shift() {
    while queueA.size() != 1 {
      queueB.enqueue(queueA.dequeue()!)
    }
  }

  private func _swap() {
    let temp = queueB
    queueB = queueA
    queueA = temp
  }
}


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




4、总结

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




相关内容

Swift 算法实战之路:基本语法与技巧
Swift 算法实战之路:数组,字符串,集合,与字典
Swift 算法实战之路:链表
Swift 算法实战之路:栈和队列




作者:故胤道长


都看到这里了,就把这篇资料推荐给您的好朋友吧,让他们也感受一下。

回帖是一种美德,也是对楼主发帖的尊重和支持。

*声明:敏捷大拇指是全球最大的Swift开发者社区、苹果粉丝家园、智能移动门户,所载内容仅限于传递更多最新信息,并不意味赞同其观点或证实其描述;内容仅供参考,并非绝对正确的建议。本站不对上述信息的真实性、合法性、完整性做出保证;转载请注明来源并加上本站链接,敏捷大拇指将保留所有法律权益。如有疑问或建议,邮件至marketing@swifthumb.com

*联系:微信公众平台:“swifthumb” / 腾讯微博:@swifthumb / 新浪微博:@swifthumb / 官方QQ一群:343549891(满) / 官方QQ二群:245285613 ,需要报上用户名才会被同意进群,请先注册敏捷大拇指

嗯,不错!期待更多好内容,支持一把:
支持敏捷大拇指,用支付宝支付10.24元 支持敏捷大拇指,用微信支付10.24元

评分

参与人数 1金钱 +10 贡献 +10 专家分 +10 收起 理由
Anewczs + 10 + 10 + 10 32个赞!专家给力!

查看全部评分

cocoaswift 发表于 2016-6-21 19:30:21 | 显示全部楼层
系列呀,不错!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

做任务,领红包。
我要发帖

分享扩散

都看到这里了,就把这资料推荐给您的好朋友吧,让他们也感受一下。
您的每一位朋友访问此永久链接后,您都将获得相应的金钱积分奖励
热门推荐

合作伙伴

Swift小苹果

  • 北京治世天下科技有限公司
  • ©2014-2016 敏捷大拇指
  • 京ICP备14029482号
  • Powered by Discuz! X3.1 Licensed
  • swifthumb Wechat Code
  •   
快速回复 返回顶部 返回列表