栈(Stack)是一种后入先出(Last in First out，简称LIFO)的数据结构。你可以把它想象成一个羽毛球的收纳筒，最先放进去的那个羽毛球一定是最后拿出来，而最后放进去的那个羽毛球一定是最先拿出来。栈结构和数组非常类似，不过相比而言，栈的访问方式受到了一定的限制。下面是栈数据结构的示意图：
栈结构示意图.png
数组里面的元素是可以随机访问的，而栈结构在数据元素访问接口这一块有着严格的限制。从上图中可以看出，栈结构里面的元素在访问时，只能从一端进行。栈数据结构中主要实现了下面这三种方法：
- push()：将一个元素压入到栈底；
- pop()：从栈顶移除并返回一个元素；
- peek()：从栈顶返回一个元素，但是这个元素不会从栈中删除。
当然，除了上面这三种主要的方法之外，栈中还实现了一些用于辅助操作的方法和属性，主要有下面这几种：
- cout：用于返回栈中元素的个数；
- isEmpty()：如果栈为空，就返回true，否则就返回false；
- isFull()：如果栈存储空间已满，则返回true，否则返回false。
栈的定义由一系列的接口组成，而这些接口又定义了栈可以执行哪些操作。在实现一个栈时，你并不需要定义底层的数据结构。一般而言，通用的数据结构是由数组或者链表组成，具体采用哪种实现方式，取决项目需求的性能特征。
1、栈的应用
栈常见的应用场景有：表达式评估和语法解析。具体表现为，将整数转换为二进制、回溯算法，以及使用命令设计模式支持撤消和重做功能。
2、栈的实现
接下来的内容里，我们将会利用泛型(Generics)语法来定义我们的栈结构。因为泛型语法在存储数据类型时，可以展现出极大的灵活性。
在Stack类型的数据结构中，我们将会实现以下几个方法和属性：push()、 pop()、peek()、isEmpty()，以及count属性。因为数组中有很多现成的方法，这对我们Stack类型的实现有极大的帮助， 所以我们会采用数组作为Stack类型的辅助存储器：
// 定义一个Stack类型的栈
public struct Stack<T> {
// 数组作为辅助存储器，主要是用来存储Stack里面的元素
fileprivate var elements = [T]()
// 构造器
public init() {}
// 出栈操作：从Stack中删除一个元素，并且将其返回
public mutating func pop() -> T? {
return self.elements.popLast()
}
// 压栈操作：将数据元素压入栈底(类似于数组中的添加元素)
public mutating func push(element: T){
self.elements.append(element)
}
// 出栈操作：从Stack中返回一个数据元素，但是不会将其从Stack中删除
public func peek() -> T? {
return self.elements.last
}
// 判断Stack里面的元素是否为空
public func isEmpty() -> Bool {
return self.elements.isEmpty
}
// 用于获取Stack里面的元素个数
public var count: Int {
return self.elements.count
}
}
在上面的代码中，我们使用了泛型，因为它可以在编译时才确定存储在Stack中的数据究竟是什么类型，这为我们对Stack数据类型的设计提供了很大的灵活性。除此之外，我们还在Stack中使用了数组，用它来存储Stack中的元素。不光如此，数组中还提供了一个popLast()方法，它为我们实现从栈顶删除一个元素提供了很大的帮助。下面我们就来用一下这个Stack数据类型：
// 声明一个Stack类型的变量
var myStack = Stack<Int>()
// 调用压栈方法，将数据存入栈底
myStack.push(element: 5) // [5]
myStack.push(element: 44) // [5, 44]
myStack.push(element: 23) // [5, 44, 23]
// 调用出栈方法，将栈顶的数据删除
var x = myStack.pop() // x = 23
x = myStack.pop() // x = 44
x = myStack.pop() // x = 5
// 如果栈中的元素已经被清空了，再次调用出栈方法会返回nil
x = myStack.pop() // x = nil
3、通过协议扩展栈
我们只是初步定义了一个Stack类型的栈，距离实际应用还差得很远，接下来我们要用extension对其进行相应的扩展。在上一篇文章中，我们介绍过迭代器(iterators)和序列(sequences)，下面我们就要把它们用在我们的Stack类型里。
我们会添加几个便利协议。首先要添加的就是CustomStringConvertible协议和CustomDebugStringConvertible协议。这两个协议允许你在打印Stack类型及其元素值时，返回比较友好的名称：
// 打印Stack类型及其元素的值
extension Stack: CustomStringConvertible, CustomDebugStringConvertible {
// 栈及其元素的文本表示
public var description: String {
return self.elements.description
}
// 栈及其元素的文本表示，主要用于调试
public var debugDescription: String {
return self.elements.debugDescription
}
}
接下来，我们肯定希望Stack在定义的时候，用起来像Array一样的方便，为此我们需要让它遵守ExpressibleByArrayLiteral协议。它可以让我们在声明一个Stack类型时，可以使用快速声明的语法：
// 让Stack能够使用快速声明的语法
extension Stack: ExpressibleByArrayLiteral {
public init(arrayLiteral elements: T...) {
self.init(elements)
}
}
// 使用快速声明的语法来初始化一个Stack类型的变量
var stringStack : Stack = ["LeBron James", "Carmelo Anthony", "Dwyane Wade", "Chris Paul"]
使用快速声明语法时一定要注意，必须明确指明它是Stack类型，否则编译器会把它当做普通的Array类型进行处理。接下来我们继续扩展Stack，让它遵守IteratorProtocol协议，从而可以像Array那样使用迭代器：
// 给Stack扩展迭代器
public struct ArrayIterator<T> : 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
}
}
在上面的代码中我们引入了关键字mutating。有时候，我们需要修改一个方法实例的属性，比如说修改一个结构体的值类型，为了允许对结构体中的数据进行修改，就需要用关键字mutating对方法名进行修饰。
因为Stack类型在实现时使用了数组作为其内部存储结构，我们定义了一个类型为[T]的变量currentElement，在泛型T定义的位置，当结构体ArrayIterator被使用时，它会将数组存储起来然后传递给构造器。除此之外，我们还实现了负责返回序列中下一个元素的next()方法，如果我们遍历到数组的末尾，它就会返回一个nil，然后通知Swift的运行时，数组中已经没有可遍历的元素了，不必再执行for...in循环了。
接下来，我们希望通过实现makeIterator()方法来继续扩展Stack类型，让Stack类型可以支持for...in循环。为此我们应该遵守Sequence协议。 在这个实现中，需要连接上面定义的ArrayIterator类型：
// 给Stack添加for...in支持
extension Stack: Sequence {
public func makeIterator() -> ArrayIterator<T> {
return ArrayIterator<T>(elements: self.elements)
}
}
Swift运行时会调用makeIterator()方法来初始化for ... in循环。 我们将返回ArrayIterator的一个新实例，当我们的栈实例使用了后备数组时，该实例被初始化
Swift运行时会调用makeIterator()方法来初始化for…in循环。当Stack实例使用支持数组时，它将会返回一个新的已经被初始化了的ArrayIterator实例。
最后一个需要扩展的功能是添加另外一个构造器，它将允许我们从一个已经存在的栈中初始化一个新的Stack实例。需要注意的是，当我们创建一个副本时，需要调用数组的reversed()方法。这是因为Sequence.makeIterator()方法是由数组的构造器调用，并且从我们的栈中pop出一个元素。如果我们不对数组进行转置，最终我们将会从原始栈中创建出一个与存储序列相反的栈，而这并不是我们想要的。给Stack再添加一个构造器：
extension Stack: Sequence {
public func makeIterator() -> ArrayIterator<T> {
return ArrayIterator<T>(elements: self.elements)
}
// 再添加一个构造器，用于从一个已经存在的Stack实例中初始化出一个新的Stack实例
public init<S : Sequence>(_ s: S) where S.Iterator.Element == T {
self.elements = Array(s.reversed())
}
}
// 快速声明
var aStack : Stack = [3, 5, 7, 9]
// 从已经存在的Stack实例中再初始化出一个新的实例
var bStack = Stack<Int>(aStack)
// 将元素44压入aStack中
aStack.push(element: 44)
// 将元素20压入bStack中
bStack.push(element: 20)
需要注意的是，当我们创建bStack实例变量时，它会从aStack中创建一个副本，并且当我们向bStack中添加元素时，aStack中的元素不会受影响。
关于Stack类型，我们仍然有改进的余地。我们可以利用Swift标准库现有的功能对迭代器和序列部分的代码进行优化。下面我们将会介绍三种新的类型，它们都是支持懒惰计算(lazy evaluation)的：
- AnyIterator<Element>：它是一个抽象的IteratorProtocol基类型，与IteratorProtocol 类型有关，通常是当做序列类型来用；
- AnySequence<Base>：创建一个与基类型具有相同元素的序列，当你调用.lazy时，会返回一个LazySequence类型；
- IndexingIterator<Elements>：它是任意集合的迭代器，也是任意没有明确声明集合默认的迭代器。
接下来，我们就用上面这三种类型来改进与Sequence有关的扩展：
// 给Stack添加for...in支持
extension Stack: Sequence {
// 改进Sequence协议的代码
public func makeIterator() -> AnyIterator<T> {
return AnyIterator(IndexingIterator(_elements:
self.elements.lazy.reversed()))
}
// 再添加一个构造器
public init<S : Sequence>(_ s: S) where S.Iterator.Element == T {
self.elements = Array(s.reversed())
}
}
上面的代码比较分散，看起来有些乱，为了方便阅读和查看，现在我们整理一下，把它们放在一起：
// 实现一个基本的Stack类型
public struct ArrayStack<T> {
// 声明一个数组，用于存储栈里面的元素
fileprivate var elements = [T]()
// 构造器
public init() {}
// 构造器
public init<S : Sequence>(_ s: S) where S.Iterator.Element == T {
self.elements = Array(s.reversed())
}
// 出栈操作，并且将该元素从栈顶删除
mutating public func pop() -> T? {
/**
* 在栈的实现过程中，我们是采用数组来存储元素的，而数组中有一个popLast()方法，
* 这个方法在我们设计pop()方法，实现从栈顶删除元素时，可以提供有效的帮助
*/
return self.elements.popLast()
}
// 入栈操作，将该元素添加到栈底
mutating public func push(element: T){
self.elements.append(element)
}
// 单纯的出栈操作，不会将元素从栈里删除
public func peek() -> T? {
return self.elements.last
}
// 判断栈是否为空
public func isEmpty() -> Bool {
return self.elements.isEmpty
}
// 返回栈中元素的个数
public var count: Int {
return self.elements.count
}
}
// 用来实现数组字面意思声明语法
extension ArrayStack: ExpressibleByArrayLiteral {
/**
* 这个方法可以让你像下面这样定义一个栈：
* var myStack: ArrayStack<Int> = [4, 5, 6, 7]
*/
public init(arrayLiteral elements: T...) {
self.init(elements)
}
}
// 当你打印类型时，可以输出好看的名称
extension ArrayStack: CustomStringConvertible, CustomDebugStringConvertible {
/**
* 在打印栈及其元素时，输出简介漂亮的格式。
* 如果不实现这些代码，打印栈的结果为：ArrayStack<Int>(elements: [5, 44, 23])
* 实现下面这些代码之后，打印栈的结果为：[5, 44, 23]
*/
public var description: String {
return self.elements.description
}
// 打印时输出简介的格式，主要用于调试
public var debugDescription: String {
return self.elements.debugDescription
}
}
// 声明一个栈
var myStack = ArrayStack<Int>()
// 入栈操作
myStack.push(element: 5)
myStack.push(element: 44)
myStack.push(element: 23)
// 打印栈及其元素
print(myStack)
// 出栈操作(会从栈顶删除元素)
var x = myStack.pop()
x = myStack.pop()
x = myStack.pop()
// 前面的操作已经将栈里面的元素删除完了，所以这一步操作会返回nil
x = myStack.pop()
// 得到一个空的栈
x = myStack.pop()
// 打印栈
print(myStack)
// 继续进行入栈操作
myStack.push(element: 87)
myStack.push(element: 2)
myStack.push(element: 9)
// 打印栈
print(myStack)
print("**************")
// 使用新的元素覆盖原来栈里面的元素
myStack = [4,5,6,7]
print(myStack)
// 查看栈的类型
type(of: myStack)
print("**************")
/**
* 给我们的栈添加for..in语法支持，并且实现从一个现有的栈中初始化出一个新
* 的栈
*/
extension ArrayStack: Sequence {
// 再添加一个构造器，用于从一个已经存在的Stack实例中初始化出一个新的Stack实例
public func makeIterator() -> AnyIterator<T> {
return AnyIterator(IndexingIterator(_elements: self.elements.lazy.reversed()))
}
}
// 从现有的栈中初始化出一个新的栈
var stackFrommyStack = ArrayStack<Int>(myStack)
// 给新创建出来的栈添加元素
stackFrommyStack.push(element: 55)
// 继续给原来的栈添加元素
myStack.push(element: 70)
myStack.push(element: 10)
// 遍历原来栈中的元素
for el in myStack {
print(el)
}
栈数据结构的基础知识，我们暂时先整理到这里，后面将会开始学习Swift队列(Queue)的相关知识。
网友评论