什么是栈呢？
简单来说，栈是一种存储数据的格式，分配内存的一种方式。
类似于线性表(通过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
网友评论