Swift 里的 Stack 实现

今天在练习设计模式的时候忽然发现 Swift 里是没有栈的——就是 Stack 类。由于我是照着 Java 版的设计模式来学习的,所以我只好自己看着实现一个了。

不过说起来,在苹果官方手册的“泛型”一章中还真有个栈的栗子,它是用结构体实现的。这也倒是符合了 Swift 一贯的风格——毕竟, Stack 也没必要去用类实现——对 Swift 里的结构体来说。

来自维基百科
来自维基百科

这里我们简单回顾一下什么是栈——其实它在不同的层面可能有不同的定义,这里我们参考维基百科的定义:

堆栈英语stack),也可直接称台湾作堆叠,在计算机科学中,是一种特殊的串列形式的数据结构,它的特殊之处在于只能允许在链接串列或阵列的一端(称为堆叠顶端指标,英语top)进行加入资料(英语push)和输出资料(英语pop)的运算。另外堆叠也可以用一维阵列连结串列的形式来完成。堆叠的另外一个相对的操作方式称为伫列

由于堆叠数据结构只允许在一端进行操作,因而按照后进先出(LIFO, Last In First Out)的原理运作。

堆叠数据结构使用两种基本操作:推入(push)和弹出(pop):

  • 推入:将数据放入堆叠的顶端(阵列形式或串列形式),堆叠顶端top指标加一。
  • 弹出:将顶端数据资料输出(回传),堆叠顶端资料减一。

泛型版本

这里我们用一个泛型的数组来作为栈的储存,然后就是简单的 push 和 pop,另外,我还添加了两个用来检测堆栈是否为空以及只查看顶端不移除的方法,这样的话,就和 Java 里的 Stack 类差不多了。

使用的话要按照泛型的方式去声明: var GVersionStack = StackG<SomeClass>()

这里由于我们使用的是结构体,所以要声明为变量而不是常量。另外也是因此,我们的部分对结构体内数据有修改的方法都标记了 mutating  关键字。

这里我们看个使用的栗子:

我随手写了一个类,一会儿我们用堆栈来存放这个类的实例(的引用)。

我声明了三个不同的实例,给它们不同的序号以追踪,然后压入栈里。由于是泛型,所以以后入栈的数据必须是 SomeClass 的类型(或者子类),否则就不能进入。这也符合了 Swift 语言的类型安全风格。

Class 版本

不过,我还是想要让它实现像 Java 那样的 Stack 类,怎么办呢?我把这个栈改了改:

这一次我使用了类而不再是结构体实现,去掉了泛型所以声明的时候更方便,也可以声明成常量——因为它保存的是类的引用。

这里我们把数组的类型声明成了 Any ,这样它就可以指代任何类型了,包括类,也包括 Swift 里的基本类型。

注意

由于 Swift 里的基本类型都是经过结构体包装的,而且它们并不继承自 AnyObject ,如果像OC那样写,就不能放入基本类型啦!而且,Swift 不会有默认继承基类的习惯,所以我们使用 Any 而不是 AnyObject 。

不过,这样也就没有了类型,不论你放什么东西进去,Swift 都不能帮你检查,因为它们都变成了 Any ,这时我们就要手动检查类型。好了,栗子还是上边的那个 SomeClass ,这次我们用新的栈来试试:

这次我不仅压入了 SomeClass ,还压入了字符串以及整形数字,一切都是那么完美。

接下来,我依次弹出堆栈里的数据,但我在使用它们之前必须先对其进行转换格式,否则就不能使用——因为 Swift 已经不认识它们了。

延伸阅读

最后,我把这两个写好的堆栈臭不要脸地传到了自己的 Github 上,供你下载使用和参考;

关于泛型的内容,参考自这里

关于堆栈的维基百科

 

Published by R0uter

如非声明,本人所著文章均为原创手打,转载请注明本页面链接和我的名字。

Join the Conversation

1 Comment

电子邮件地址不会被公开。 必填项已用*标注