数据结构：栈的介绍与实现（swift版）

什么是栈呢？

简单来说，栈是一种存储数据的格式，分配内存的一种方式。
类似于线性表(通过pNext指针的方式，指向下一个元素的地址)将数据串联起来。在这种内存分配模式下，只允许在一端（栈顶）进行插入和删除元素，因此，数据具备先进后出的状态。

如图

tu.001.jpeg

我们可以把栈看做一个杯子，在不断向被子里放入比如橘子（🍊）吧，想象一下，当我们把被子装满，我们想吃橘子的时候，是不是只能先拿最上面的，才能接着取下一个，这就是栈的先进后出，也只能在杯子口放橘子和拿橘子。

简单的栈实现思路。

我们可以把栈，看做一个简单的对象Stack（杯子），这个对象拥有2个指针，一个始终指向被子最上方的橘子（栈顶指针），一个永远指向杯底（栈底指针），并且有一些基本功能。比如：

• 初始化一个空栈 init
• 判断栈是否为空 empty
• 插入一份数据 push
• 删除一份数据 pop
• 遍历所有数据 enumerateObjects

以下我们采用swift语言简单实现这些功能。首先我们打开Xcode新建命令行工程，语言选择swift，新建一个类，继承自NSObject，命名为Stack,并且添加其栈顶和栈底指针，和其基本的5个函数。

stack1.png

栈中的元素是以链表结构相链接下一个数据，为了便于操作，我们会在栈初始化的时候，创建一个空的节点（头节点），然后让栈顶和栈底指针指向该节点，实现一个空栈的创建。

在实现空栈创建之前，我们还需要定义栈中的元素对象，由于采用链表结构，如图tu.001.jpeg，栈中元素存在一个数据域（存放数据）和指针域（指向下一个对象的地址）相链接。

//栈元素对象
class Element: NSObject {
    //数据域 存放数据
    var data : NSObject?
    //节点域 指向下一个元素的指针
    var pNext : Element?
}

接下来实现空栈的创建，重写Stack类的init方法

override init() {
        //创建头节点。便于操作栈
        let elment = Element()
        //将栈低指针指向该节点
        bottom = elment
        //由于是空栈，所以此时，栈顶和栈低指针同时指向该节点
        top = bottom
    }

紧接着我们依次实现上面我们提到的基本功能

Stack class code

class Stack: NSObject {

    var top : Element!     //栈顶指针
    var bottom : Element!  //栈底指针，永远指向一个不用的元素
    
    override init() {
        //创建头节点。便于操作栈
        let elment = Element()
        //将栈低指针指向该节点
        bottom = elment
        //由于是空栈，所以此时，栈顶和栈低指针同时指向该节点
        top = bottom
    }
    
    //栈是否是否为空
    func empty() -> Bool {
        //如果 栈顶指针和栈低指针同时指向同一个元素（即头节点），那么这是一个空栈
        if top.isEqual(bottom) {
            return true
        }
        return false
    }
    
    //插入数据
    func push(value:NSObject){
        //首先创建要插入的节点元素
        let element = Element()
        element.data = value
        //紧接着将元素加到栈顶，首先使得该元素的下一个pNext指向栈顶对象
        element.pNext = top
        //接着将最新的元素 设为栈顶元素
        top = element
    }
    
    //删除数据,即只删除栈的最上方的元素
    //swift自动释放机制，只需要将栈顶指针下移即可
    func pop() -> NSObject? {
        if !empty() {
            let elemet = top
            top = top.pNext
            //返回删除的元素
            return elemet
        }
        return nil
    }
    
    //遍历数据，这里只作简单的输出
    func enumerateObjects() {
        //这里只做简单的遍历输出
        //取一个临时的指针，找到栈顶指针，不断下移实现输出
        var element = top
        while !(element?.isEqual(bottom))! {
            print("元素的值为\(element?.data!)")
            element = element?.pNext
        }
    }
}

至此，我们简单的栈的功能就实现啦，你可以尝试创建一个栈，插入和删除元素试试哦。

test.png