什么是栈
关于什么是栈, 我们可以先看百度百科给的解释
栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
或许你现在很迷茫? 其实很好理解, 我们先来理解一些基础的概念
你可以把栈理解为一个这样的一水杯
此时这个水杯里面没有水,这种情况对于栈来说叫做空栈
那么此时我们来倒入一些水
我们平时接水时是不是先进入杯子的在底部, 而后进入的则在上面 ( 请暂时忽略掉水作为液体的特性 )
我们接水的动作,对于栈来说则被称为入栈
而倒水的动作被,对于栈来说则被称为出栈
就像水杯里面的水一样, 栈内数据遵循一个规则,那就是先进后出,后进先出, 在栈里面可不讲究先来后到
那如果杯子里的水溢出来了呢?
对于栈来说这就被叫做栈溢出
如果接的是热水,那是不是就烫到手了; 而栈在计算机里也是,溢出了也是要报错的,那如何防止出现这种情况呢?
我们可以通过一个概念来进行判断, 那就是栈是否栈满
接下来,我们来小结一下, 栈的基本概念/状态
- 栈内数据遵循: 先进后出, 后进先出规则
- 栈内添加元素: 入栈
- 栈内取出元素: 出栈
- 栈内元素满了: 满栈
- 栈内没有元素: 空栈
- 栈内元素溢出: 栈溢出
不必去记住这些术语, 主要理解栈内的基本数据流程
GO+ 实现栈
终于要动手了, 现在我们来实现出栈 的数据结构.
要设计栈, 我们需要需要有一个变量才存储栈内的元素.
我们先设计出基本的变量来, 为了防止栈溢出所以我们需要一个变量来限制栈的元素容量.
遵守先进后出, 后进先出的规则, 我们操作都需要对最顶部的元素进行操作, 所以我们还需要一个变量来标记栈顶元素的索引.
分析到这里，栈的数据结构已经呼之欲出了。我们就直接写出栈的数据结构和他的构造方法。
TIps
& 是取地址符号 , 即取得某个变量的地址 , 如: &a
* 是指针运算符 , 表示一个变量是指针类型 , 也可表示指针变量所指向的存储单元 , 也就是这个地址所存储的值 .
/ 定义栈的结构体 type Stack struct { // 用装元素的切片 stackSet []string // 栈顶位置标记 stackTop int // 栈的容量 stackSize int } // 初始化栈 func NewStack(size int) *Stack { // 返回栈的初始值 return &Stack{ stackSet: make([]string, size), stackTop: 0, stackSize: size, } }
栈顶指针初始可以指向0, 也可以指向-1
你可以这样理解-1: 当第一个元素入栈的时候, 栈顶指针就可以通过自加指向0元素，从而避免其它判断.
栈的基本操作
介绍
当我们了解了栈的基本概念之后, 接下来就简单多了
对于一个栈来说，如果我们将基本概念融入到代码之中, 其基本操作分为以下四种
- 入栈 : 存入数据
- 出栈 : 取出数据
- 满栈判断 : 避免栈溢出
- 空栈判断 : 避免栈空了以后还有出栈的请求
接下来我们准备四个方法来进行实现
入栈
// 功能: 元素入栈 // 返回: 入栈成功返回true,返之返回false func (s *Stack) Push(e string) bool { // 判断栈是否为满栈 if s.IsFull() { return false } // 在栈的顶部添加数据 s.stackSet[s.stackTop] = e // 重新定位栈顶的位置 s.stackTop++ return true }
出栈
// 功能: 元素出栈 // 返回: 出栈成功返回true + 原始栈, 返之返回false + 取出之后的新栈 func (s *Stack) Pop() (flag bool, ret string) { // 判断是否为空栈 if s.IsEmpty() { return false, ret } // 取出元素 ret = s.stackSet[s.stackTop-1] // 重新定位栈顶的位置 s.stackTop-- return true, ret }
判断是否空栈
// 功能: 判断栈是否为空 // 返回: 空栈返回true,返之返回false func (s *Stack) IsEmpty() bool { // 直接判断栈顶元素即可 if s.stackTop == 0 { return true } return false }
判断是否满栈
// 功能: 判断栈是否为空 // 返回: 满栈返回true,返之返回false func (s *Stack) IsFull() bool { // 判断栈顶位置是否和最大容量一样 if s.stackTop == s.stackSize { return true } return false }
案例
实现主函数
func main() { // 初始化栈 stack := NewStack(3) println "\n初始的栈：", stack // 先测试下空栈是否能删除元素 println stack.Pop() stack.Push("您好，我是uiu") stack.Push("我的博客链接: uiuing.com") println "\n元素入栈之后：", stack, "\n" // 删除掉刚刚的两天数据试试 println stack.Pop() println stack.Pop() println "\n元素出栈之后：", stack }
完整代码
package main // 定义栈的结构体 type Stack struct { // 用装元素的切片 stackSet []string // 栈顶位置标记 stackTop int // 栈的容量 stackSize int } // 初始化栈 func NewStack(size int) *Stack { // 返回栈的初始值 return &Stack{ stackSet: make([]string, size), stackTop: 0, stackSize: size, } } // 功能: 元素入栈 // 返回: 入栈成功返回true,返之返回false func (s *Stack) Push(e string) bool { // 判断栈是否为满栈 if s.IsFull() { return false } // 在栈的顶部添加数据 s.stackSet[s.stackTop] = e // 重新定位栈顶的位置 s.stackTop++ return true } // 功能: 元素出栈 // 返回: 出栈成功返回true + 原始栈, 返之返回false + 取出之后的新栈 func (s *Stack) Pop() (flag bool, ret string) { // 判断是否为空栈 if s.IsEmpty() { return false, ret } // 取出元素 ret = s.stackSet[s.stackTop-1] // 重新定位栈顶的位置 s.stackTop-- return true, ret } // 功能: 判断栈是否为空 // 返回: 空栈返回true,返之返回false func (s *Stack) IsEmpty() bool { // 直接判断栈顶元素即可 if s.stackTop == 0 { return true } return false } // 功能: 判断栈是否为空 // 返回: 满栈返回true,返之返回false func (s *Stack) IsFull() bool { // 判断栈顶位置是否和最大容量一样 if s.stackTop == s.stackSize { return true } return false } func main() { // 初始化栈 stack := NewStack(3) println "\n初始的栈：", stack // 先测试下空栈是否能删除元素 println stack.Pop() stack.Push("您好，我是uiu") stack.Push("我的博客链接: uiuing.com") println "\n元素入栈之后：", stack, "\n" // 删除掉刚刚的两天数据试试 println stack.Pop() println stack.Pop() println "\n元素出栈之后：", stack }
运行结果
如果还不清楚栈的实现, 请认真看完整代码的注释
最后，留给大家一道思考题，根据栈的特性，其有何处可以应用？
