栈

栈（Stack）是所有数据结构中最简单但却是最重要的一种，栈出现的情况在对内含反转数据的应用非常适合。栈是属于 后进先出 - Last In, First Out（LIFO） ，最后压入栈中的项总是最先从栈中弹出的项，生活中举个例子说明下，装薯片的时候按顺序装入罐子中，但是吃薯片的时候就要从开口处把最后一个装入的薯片先吃掉。

栈是一种形式的表，属于表类型中的受限表，即插入和删除只发生在一端（表的末端）。在栈当中我们把这端成为栈顶（top）。当我们对栈顶进行插入操作时，即向栈中增加一项时，称之为入栈（push）；对栈进行删除操作时，即从栈中删除一项时，称之为出栈（pop）。

核心方法

对于栈来说，主要的核心方法就是入栈和出栈两个方法，向栈顶入栈一个”i”的字符串：

1	stack.push("i")

目前栈中间的元素为[“i”]，从栈里面出栈当前的元素：

1	stack.pop()

这样返回了元素”i”，并且当前栈为空。继续出栈会导致返回nil，通常在实际应用中这里会做错误处理，“栈下溢（stack underflow）”。

源代码

//
//  Stack.swift
//  
//
//  Created by 叶帆 on 2017/9/6.
//

public struct Stack<T> {

    fileprivate var array = [T]()

    /**
     获取当前栈的长度
     - returns: 返回栈的长度，如果Stack为空，则值为0
     */
    public var count: Int {
        return array.count
    }

    /**
     判断是否为空
     - returns: 如果Stack为空，则值为true，否则值为false
     */
    public var isEmpty: Bool {
        return array.isEmpty
    }

    /**
     获取栈顶元素的值
     - returns: 栈顶元素的值，如果为空返回nil
     */
    public var top: T? {
        return array.last
    }

    /**
     向栈顶插入一个元素
     - parameter element: 需要插入的值
     - 时间复杂度: O(1)
     */
    public mutating func push(_ element: T) {
        array.append(element)
    }

    /**
     删除栈顶元素
     - returns: 返回删除栈顶元素的值，如果为空返回nil
     - 时间复杂度: O(1)
     */
    public mutating func pop() -> T? {
        return array.popLast()
    }
}

extension Stack: Sequence {
    public func makeIterator() -> AnyIterator<Element> {
        var curr = self
        return AnyIterator {
            _ -> Element? in
            return curr.pop()
        }
    }
}

应用场景

栈的强项是处理反转的能力，所以实际的应用场景都是和此相关的。

回文字符串

所谓的回文字符串就是指那些正读和反读均相同的字符系列，如“席主席”，“aha”均是回文，通过栈这种数据结构可以很容易判断一个字符串是否为回文。

大概的思路就是找到中间的值，把中间值以前的放入栈中，然后一个个出栈，并且在出栈的同时和中间值以后的值进行比对。如果top为空的时候就说明符合回文的规则。

逆波兰计算器

所谓的逆波兰计算器指的就是在这样的计算器中，操作数（通常是数字）在操作被指定前输入，操作数放入栈中。当操作执行时，操作数从栈中弹出并且把操作结果入栈。

括号的匹配

在程序中，通常会对{}、[]、()、<>来进行括号的匹配。

**版权声明**

Ivan’s Blog by Ivan Ye is licensed under a Creative Commons BY-NC-ND 4.0 International License.
由叶帆创作并维护的叶帆的博客博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证。

本文首发于Ivan’s Blog | 叶帆的博客博客（ http://yeziahehe.com ），版权所有，侵权必究。

本文链接：http://yeziahehe.com/2017/09/07/Structure_stack/