数据结构:Stack

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

数据结构:Stack

[复制链接]
Ding 发表于 2016-11-3 15:12:46 | 显示全部楼层 |阅读模式
快来登录
获取优质的苹果资讯内容
收藏热门的iOS等技术干货
拷贝下载Swift Demo源代码
订阅梳理好了的知识点专辑
栈(Stack)类似数组,但是个相当内敛的闺秀。一个新元素,只可以在栈顶压(push)进来;要移除元素,也只能弹出(pop)栈顶的那个;访问元素也是一样,只可对顶部的那个元素惊鸿一瞥(peek)。

数据结构:Stack

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


为什么这样?在许多场合,你需要把东西放在一个临时容器里,稍后又需要一一取出,无论添加还是移除,你非常关心顺序。

栈提供了先进后出的机制保证了一种特别的顺序,类似的,队列( queue)提供了先进先出的机制。

比如,我们想给一个空栈里加个数字:

[Swift] 纯文本查看 复制代码
stack.push(10)


现在的栈是 [ 10 ]。再加一个:

[Swift] 纯文本查看 复制代码
stack.push(3)


现在成了 [ 10, 3 ]。再一个:

[Swift] 纯文本查看 复制代码
stack.push(57)


现在是 [ 10, 3, 57 ]。

数据结构:Stack 2

数据结构:Stack - 敏捷大拇指 - 数据结构:Stack 2


移除一个元素:

[Swift] 纯文本查看 复制代码
stack.pop()


这个方法返回被移除的元素57,只因它是最后被放进栈的。现在栈重新成了 [ 10, 3 ] 。我们继续:

[Swift] 纯文本查看 复制代码
stack.pop()


不出所料,返回了3。

如果栈已经空了,再pop人就会返回nil,也有的实现是直接给你个错误信息(“栈干了”)。

数据结构:Stack 0

数据结构:Stack - 敏捷大拇指 - 数据结构:Stack 0


用Swift实现栈太简单了,只需要简单地包装下Array,只支持上面说的push、pop和peek等方法就好:

[Swift] 纯文本查看 复制代码
public struct Stack<T> {
    fileprivate var array = [T]()
    
    public var isEmpty: Bool {
        return array.isEmpty
    }
    
    public var count: Int {
        return array.count
    }
    
    public mutating func push(_ element: T) {
        array.append(element)
    }
    
    public mutating func pop() -> T? {
        return array.popLast()
    }
    
    public func peek() -> T? {
        return array.last
    }
}


[Swift] 纯文本查看 复制代码
extension Stack: Sequence {
    public func makeIterator() -> AnyIterator<T> {
        var curr = self
        return AnyIterator {
            _ -> T? in
            return curr.pop()
        }
    }
}


注意到push方法是在array的最后追加元素而不是在最前插入。在最前插入有点低效,是个O(n)复杂度的操作,因为那需要内存中数组原来的元素都改变位置。在最后追加则只是常数级O(1)操作,不管数组原来有多少个元素,追加要用的时间几乎一样。

顺便一提的是函数调用栈:每次你调用一个函数或方法,CPU都会在一个栈上保存该函数的地址,函数执行完就可以根据这个地址准确地返回调用的地方。这也就是为什么一个函数如果多次调用自己——极端情况下是无限递归——我们的程序总是崩给我们看,只因为“栈爆了”,CPU用光了自己的空间。

数据结构:Stack 1

数据结构:Stack - 敏捷大拇指 - 数据结构:Stack 1


另外,猿媛们都该知道一个很好的网站:爆栈网(StackOverFlow),除了GitHub,那里是我们的另外一个乐园啊。




原作者: Matthijs Hollemans

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

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

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

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

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

评分

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

查看全部评分

本帖被以下淘专辑推荐:

 楼主| Ding 发表于 2016-11-3 16:55:44 | 显示全部楼层
jswift 发表于 2016-11-3 15:42
期待 Queue、各种链表、图算法、

Queue来了:
数据结构:Queue
jswift 发表于 2016-11-3 15:42:27 | 显示全部楼层
期待 Queue、各种链表、图算法、
攻城狮 发表于 2016-11-3 15:51:15 | 显示全部楼层
jswift 发表于 2016-11-3 15:42
期待 Queue、各种链表、图算法、

图,很难的啊
 楼主| Ding 发表于 2016-11-4 08:12:27 | 显示全部楼层

开始自学编程的时候,很喜欢数据结构和算法那部分。到了树略感吃力,到了图就眉头紧锁了。还有个字符串匹配的KMP,虽然意思理解了,但是具体实现还是一愣一愣的。

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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

分享扩散

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

相关标签

热门推荐

合作伙伴

Swift小苹果

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