Swift数据结构——栈的实现

2018-02-27 11:28:07来源:oschina作者:Enrica_Shi人点击

分享

  栈(Stack)是一种**后入先出(Last in First Out)**的数据结构,仅限定在栈顶进行插入或者删除操作。栈结构的实际应用主要有数制转换、括号匹配、表达式求值等等。栈数据结构示意图如下所示:


这里写图片描述


###一、背景知识
  从上面的示意图中,我们知道了栈是一种受限制的数据结构,它不像数组那样可以随机存取,只能在栈顶执行入栈和出栈操作,并且最先入栈的元素最后出栈,而最后入栈的元素最先出栈。那么问题来了,在Swift中,**我们该如何实现一个栈数据结构呢?**在回答这个问题之前,我们先来了解一点Swift的基础知识。


######1、值类型和引用类型


  值类型在被赋值给另外一个实例,或者是作为参数传递给函数时,总是被复制的。也就是说它赋值或者传递的是副本,而不是原件,你修改其中一个的值,不会对另外一个值造成影响。Swift中的结构体和枚举都是值类型。


  引用类型在被赋值给另外一个实例,或者是作为参数传递给函数时,不会产生副本,而是会对底层实例创建新的引用。也就是说,它们最终都指向同一个底层实例,只要是一个引用修改了实例的值,另一个引用也会受到影响。


  Swift中没有内建的栈类型数据结构,这就意味着,如果我们要实现一个栈数据结构,就必须自定义。在Swift中,结构体和类都可以用来定义自定义类型,那么我们究竟是该用结构体还是类呢?在回答这个问题之前,先来对结构体和类的基本特性做一个简单的了解。


  在Objective-C编程中,结构体和类的区别很大,该用结构体还是类,往往一眼就能做出决定。但是,在Swift中,结构体不再像之前那么单纯,它里面增添了很多面向对象的特性,从而使得结构体可以执行一些原本只有类才能执行的任务。这样一来,貌似让结构体和类之间的选择变得困难起来。不过,结构体终究还是结构体,它永远都无法变成类。因此,对于结构体和类之间的选择,官方还是有一定的指导原则的:



(1)、如果类型需要传值,那么就用结构体。这么做会确保赋值或者传递参数到函数中时,类型是被复制的;
(2)、如果类型不支持、或者没有必要支持子类继承,那么就用结构体。结构体不支持继承关系,也就不存在子类问题;
(3)、如果类型要表达的行为相对比较直观,并且里面只包含一些简单的值,那么最好是考虑用结构体。如有必要,随时可以将其转成类;
(4)、最后一点,结构体属于值类型,而类属于引用类型。如果需要保证数据独立,不受其它影响,最好是使用结构体;
(5)、除上面4点之外的其它所有情况,均建议使用类。



  看完上面的选择建议,相信你在实现栈结构时,是该选择结构体还是类,心中一定有了明确的答案。因为栈主要是用来存储数据,不涉及继承关系,而且主要的操作就是入栈和出栈,所以最好是使用结构体。


######2、认识Swift内建的数组类型


  在确定了栈使用结构体类型之后,接下来就应该为栈寻找后备存储器了。为此,先来复习一下栈数据结构的一些基本特点:①、栈可以存储多个数据元素,因此其后备存储器必须能一次存储多个独立的数据;②、另外,栈是一种后入先出的数据结构,换句话说,就是栈里面的元素在入栈和出栈时必须保持一定的顺序。Swift中已经存在的内建类型能满足上面两点的,基本上也就只有元组(Tuple)和数组(Array)了。但是,元组的操作不如数组灵活,更重要的是,数组中有很多内建的属性和方法,可以极大的帮助我们简化栈结构的实现过程。为此,使用数组(Array)作为栈的后备存储器显然是最佳选择。


  在栈数据结构的实现过程中,我们已经确定了总体的方向,即采用结构体类型,并且使用数组(Array)作为后备存储器。接下来,为了更好的理解栈数据结构的实现过程,可以先了解一下数组(Array)常用的一些内建属性和方法,相关内容可以参考上一篇笔记《Swift数据结构引言》,也可以参考《The Swift Programming Language》中Collection Types的内容。


######3、泛型、where和面向协议编程


  我们都知道,Swift中的常量、变量,以及函数都有自己的类型,在声明它们的时候,必须指明类型(或者通过字面量语法对其进行初始化,然后再有系统进行类型推断),而且类型一段确定,就只能存储同一类型的数据。但是很多时候,特别是函数,其具体实现过程是一模一样的,只不过处理的数据类型不同。这样一来就容易产生这样一个问题:为了尽可能多的处理各种数据类型,同一个函数要重复写很多遍,这显然不是一种聪明的做法。为了应对这个问题,Swift中引入了泛型的概念,就是在声明函数的时候,先不指明具体的数据类型,而是使用占位符,等到真正用到具体的数据时,再来确定其真实的数据类型。这样做的好处是,可以极大的增加代码的灵活性,最大限度的减少重复的代码。


  Swift中声明泛型的语法是,在类型名后面紧跟一对尖括号(<>),尖括号内部使用特定的符号作为类型占位符。占位符可以是任何字母,也可以是字符串,不过通常情况下,我们一般使用一个大写的字母T作为类型占位符:


/// 泛型结构体,其处理的数据类型是泛型T
struct Stack {
// 代码...
}
/// 泛型函数和方法(拥有两个泛型占位符)
///
/// - Parameter items: 参数items的类型是一个泛型数组[T]
/// - Parameter f: 参数f是一个闭包,其参数是一个泛型T,返回值是一个泛型U
/// - Returns: 整个函数的返回值是一个泛型数组[U]
func myMap(_ items: [T], _ f: (T) -> (U)) -> [U] { ... }

  除了泛型之外,还有另外一个很重要的概念我们后面会用到,就是类型约束(Type Constraint)。我们在上面谈到了泛型,其实类型约束是和泛型紧密相关的。因为泛型的真实类型要到实际应用的时候才知道,而在此之前,我们对即将要用到的数据的类型一无所知。这样一来,很容易引发一个问题,就是不管什么类型的数据都能传进去。但是有时并非所有类型的数据都适合。比如说,如果一个函数是用来比较两个参数值大小的,那么这两个参数值就必须遵守Equatable协议,否则编译的时候就不能通过。为了解决这个问题,Swift中引入了类型约束的概念。


  Swift中的类型约束,就是指在将参数传递给泛型函数时,对参数的具体类型进行一些必要的限制。类型约束有两种情况:第一种情况是,所传参数的类型必须是某个指定类的子类;另外一种情况是,所传参数必须遵守某种协议,或者协议组合。类型约束的语法是,在泛型类型后面紧跟冒号(:),然后再写上指定类的子类,或者协议(组合)。以比较两个参数值是否相等为例,来演示一下类型约束:


/// 比较两个值是否相等。所传参数的类型是一个泛型,并且参数必须遵守Equatable协议
///
/// - Parameter firstValue: 第一个参数,参数必须遵守Equatable协议
/// - Parameter secondValue: 第二个参数,参数必须遵守Equatable协议
/// - Returns: 如果所传两个参数相等,则返回true,否则返回false
func checkIfEqual(_ firstValue: T, _ secondValue: T) -> Bool {
return firstValue == secondValue
}

  还有一个非常重要的东西,就是关键字where。where既可以用来做条件筛选,也可以用来做类型约束,就以上面的类型约束来说,它和下面的写法等价:


func checkIfEqual(_ firstValue: T, _ secondValue: T) -> Bool where T: Equatable {
return firstValue == secondValue
}

  如果想了解where的更多用法,可以参考苹果的官方文档。最后一个知识点是面向协议编程,可以观看官方的Protocol-Oriented Programming in Swift,以及Swift Summit的What the 55 Swift Standard Library Protocols Taught Me。


###二、栈结构的基本实现


  我们先来实现一个最基本的栈数据结构。该结构必须拥有存储数据元素的能力,以及最关键的出栈和入栈的能力。为此,先声明一个数组,用来存储数据元素,然后再来实现若干基本的操作方法:


/// 实现一个基本的栈结构
struct Stack {/// 声明一个泛型数组,用于存储栈中的元素(栈结构的后备存储器)
private var elements = [T]()/// 返回栈结构中元素的个数
public var count: Int {

// 返回数组elements中的元素个数
return elements.count
}/// 获取或者设置栈的存储容量
public var capacity: Int {

// 获取栈的存储容量
get {

// 返回数组elements的容量
return elements.capacity
}

// 设置栈的最小容量
set {

// 设置数组elements的最小容量
elements.reserveCapacity(newValue)
}
}/// 初始化方法(创建栈实例)
public init() {}/// 使用push方法执行入栈操作
public mutating func push(element: T) {

// 判断栈是否已满
if count == capacity {
fatalError("栈已满,不能再执行入栈操作!")
}

// 使用数组的append()方法将元素添加到数组elements中
self.elements.append(element)
}/// 使用pop方法执行出栈操作
@discardableResult
public mutating func pop() -> T? {

// 判断栈是否已空
if count == 0 {
fatalError("栈已空,不能再执行出栈操作!")
}

// 移除数组elements的最后一个元素
return elements.popLast()
}/// 返回栈顶元素
public func peek() -> T? {

// 返回数组elements的最后一个元素(但是不移除该元素)
return elements.last
}/// 清空栈中所有的元素
public mutating func clear() {

// 清空数组elements中所有的元素
elements.removeAll()
}/// 判断栈是否为空
public func isEmpty() -> Bool {

// 判断数组elements是否为空
return elements.isEmpty
}/// 判断栈是否已满
public func isFull() -> Bool {

// 对数组的存储情况进行判断
if count == 0 {

// 如果数组为空,则表示栈还未存储数据元素
return false
} else {

// 如果数组不为空,则返回数组的存储容量
// 然后再根据实际存储情况判断栈是否已满
return count == elements.capacity
}
}
}

  关于上面的代码,注释都写得非常的清楚,如果复习过Swift中数组的相关知识,相信不难理解。简单的说一下关键字mutating,以及特性@discardableResult。我们在前面说过,结构体是值类型,值类型的方法是不能对自身(self)进行修改的,如果非要对自身(self)进行修改,就必须用关键字mutating进行标记。因为Stack类型中push(element: )方法和pop()方法需要修改栈中元素的个数,所以需要用mutating进行标记。@discardableResult是Swift中的一个特性,用于抑制函数或者方法返回值被调用而没有使用其结果时的警告,如果你对警告不是特别敏感,可以考虑不用这个特性。


  为了检验我们设计的这个栈是否能正常工作,可以把上面的代码拷贝到自己的项目中进行测试,也可以到我的代码仓库中下载项目进行测试。


###三、栈功能的扩展


  我们的栈结构只是具备了一些简单的功能,可以通过遵守相关协议来对其进行扩充。首先遵守CustomStringConvertible和CustomDebugStringConvertible协议,让打印Stack实例的效果更加简洁、漂亮:


// MARK: - 遵守CustomStringConvertible和CustomDebugStringConvertible协议
extension Stack: CustomStringConvertible, CustomDebugStringConvertible {
// 为Stack增加description属性,实现打印简洁漂亮的格式
// 未遵守协议之前打印效果:Stack(elements: ["刘备", "关羽", "张飞"])
// 遵守协议之后的打印效果:["刘备", "关羽", "张飞"]
public var description: String {
// 返回数组elements的文本表示
return elements.description
}// 为Stack增加description属性,实现打印简洁漂亮的格式,适配debug模式
// 未遵守协议之前打印效果:Stack(elements: ["刘备", "关羽", "张飞"])
// 遵守协议之后的打印效果:["刘备", "关羽", "张飞"]
public var debugDescription: String {

// 返回数组elements的文本表示,适配debug模式
return elements.debugDescription
}
}

  在创建Stack实例的时候,使用var stringStack: Stack = Stack()或者var intStack = Stack()语法可能显得太啰嗦,如果希望像数组一样使用var doubleStack: Stack = [1.0, 2.0, 3.0]字面量语法,就必须遵守ExpressibleByArrayLiteral协议,实现相应的方法:


// MARK: - 遵守ExpressibleByArrayLiteral协议
extension Stack: ExpressibleByArrayLiteral {// 为Stack增加类似于数组的字面量初始化方法
public init(arrayLiteral elements: T...) {
self.init()
}
}

  如果你希望Stack类型能够支持for...in和forEach(_ body: )语法,就应该遵守Sequence协议,然后实现相应的方法:


// MARK: - 遵守IteratorProtocol协议(手动实现迭代器功能)
public struct ArrayIterator : IteratorProtocol {
var currentElement: [T]
init(elements: [T]) {
self.currentElement = elements
}
mutating public func next() -> T? {
if (!self.currentElement.isEmpty) {
return self.currentElement.popLast()
}
return nil
}
}
// MARK: - 遵守Sequence协议(实现for...in循环)
extension Stack: Sequence {
public func makeIterator() -> ArrayIterator {
return ArrayIterator(elements: self.elements)
}
}
/****************** 或者直接实现下面这一个方法 ******************/
// MARK: - 遵守Sequence协议
extension Stack: Sequence {
// 实现for...in循环和forEach循环
public func makeIterator() -> AnyIterator {
return AnyIterator(IndexingIterator(_elements: self.elements.lazy.reversed()))
}
}

  最后再来增加一个新的构造函数,它可以让我们用一个已经存在的实例作为参数,然后创建另外一个全新的实例:


// MARK: - 增加新的构造函数
extension Stack {/// 实现用一个已经存在的栈作为参数,然后初始化一个新的栈
///
/// - Parameter stack: 一个已经存在的栈实例
public init(_ stack: S) where S.Iterator.Element == T {

// 将一个已经存在的栈实例转置,然后作为参数传入
self.elements = Array(stack.reversed())
}
}

  以上就是一个简单栈结构的实现过程,可以自己动手尝试一下,后面会继续学习其它类型的数据结构。完整的代码参见SwiftBooks。


###四、参考资料


[1] Matthew Mathias. John Gallagher. 《Swift Programming The Big Nerd Ranch Guide (2nd Edition)》
[2] 严蔚敏. 吴伟民. 《数据结构(C语言版)》
[3] Erik Azar. Mario Eguiluz Alebicto. 《Swift Data Structure and Algorithms》

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台