1、栈的定义

• 栈(stack)是限定仅在表尾进行插入或删除操作的线性表。
  • 栈顶(top)，指表尾端。
  • 栈底(bottom)，指表头端。
  • 空栈，即不含元素的空表。
  • LIFO(Last In First Out)，即栈的修改是按后进先出的原则进行的。
  • 链栈， 指采用链式存储结构实现的栈，通常用单链表来表示。由于栈的主要操作是在栈顶插入和删除，显然以链表的头部作为栈顶是最方便的，而且没有必要像单链表那样为了操作方便附加一个头结点。
    

    链栈示意图
• 由于链栈的插入和删除只在栈顶进行，其他操作和单链表类似，本文只给出了以下基本操作。
  • 取栈顶元素
  • 查看所有元素

2、链栈的初始化

//定义链栈的数据结构--链栈一般为一个无头结点的单链表
type stackNode struct {
    data interface{}
    next *stackNode
}

type stackList struct {
    length int //存储链表的长度
    headNode *stackNode //链表头指针的指向
}

3、链栈的入栈

链栈的入栈图

//链栈的入栈
func (stack *stackList) push(val interface{}) {
    node := new(stackNode)
    node.data = val
    node.next = stack.headNode
    stack.headNode = node
    stack.length ++
}

4、链栈的出栈

链栈的出栈图

//链栈的出栈
func (stack *stackList) pop() interface{} {
    if stack.headNode == nil {return nil}
    val := stack.headNode.data
    stack.headNode = stack.headNode.next
    stack.length --
    return val
}

5、取栈顶元素

//取栈顶元素
func (stack *stackList) getTop() interface{} {
    if stack.headNode == nil {return nil}
    val := stack.headNode.data
    return val
}

6、查看所有元素

//查看栈内所有元素
func (stack *stackList) showAll() {
    if stack.headNode.next == nil {
        fmt.Println("空栈")
        return
    }
    cur := stack.headNode
    for {
        if cur.next != nil {
            fmt.Printf("%v\n", cur.data)
            cur = cur.next
        } else {
            break
        }
    }
}

7、完整代码及结果展示

package main

import "fmt"

//定义链栈的数据结构--链栈一般为一个无头结点的单链表
type stackNode struct {
    data interface{}
    next *stackNode
}

type stackList struct {
    length int //存储链表的长度
    headNode *stackNode //链表头指针的指向
}

//链栈的初始化
func initLinkStack() *stackList {
    node := new(stackNode)
    L := new(stackList)
    L.headNode = node
    L.length = 0
    return L
}

//链栈的入栈
func (stack *stackList) push(val interface{}) {
    node := new(stackNode)
    node.data = val
    node.next = stack.headNode
    stack.headNode = node
    stack.length ++
}

//链栈的出栈
func (stack *stackList) pop() interface{} {
    if stack.headNode == nil {return nil}
    val := stack.headNode.data
    stack.headNode = stack.headNode.next
    stack.length --
    return val
}

//取栈顶元素
func (stack *stackList) getTop() interface{} {
    if stack.headNode == nil {return nil}
    val := stack.headNode.data
    return val
}

//查看栈内所有元素
func (stack *stackList) showAll() {
    if stack.headNode.next == nil {
        fmt.Println("空栈")
        return
    }
    cur := stack.headNode
    for {
        if cur.next != nil {
            fmt.Printf("%v\n", cur.data)
            cur = cur.next
        } else {
            break
        }
    }
}

func main() {
    L := initLinkStack()
    arr := []interface{}{
        "aa",
        "bb",
        "cc",
        "dd",
    }
    for i :=range arr {
        L.push(arr[i])
    }
    L.showAll()
    fmt.Println(L.getTop())
    fmt.Println(L.pop())
    fmt.Println(L.getTop())
}

dd
cc
bb
aa
dd
dd
cc

• 逻辑结构：数据元素之间存在一一对应关系。
• 存储结构：
  • 顺序存储：存储空间预先分配，可能会导致空间闲置或栈满溢出现象；数据元素个数不能自由扩充。
  • 链式存储：动态分配，不会出现闲置或栈满溢出现象，数据元素个数可以自由扩充。
• 运算规则：插入和删除在表的一端(栈顶)完成，后进先出(LIFO)。

7.2 栈的应用

1、数值转换
2、括号匹配的检验
3、表达式求值

• 中缀表达式求值
• 后缀表达式求值

4、在高级语言的编译处理过程中，栈在语法、语义等分析算法中的应用。
5、在程序设计语言中实现递归

• 递归：若在一个函数、过程或者数据结构定义的内部又直接(或间接)出现定义本身的应用，则称它们是递归的，或者是递归定义的。常用于以下三种情形。
  • 定义是递归的。如数学函数中的阶乘函数。
  • 数据结构是递归的。某些数据结构本身具有递归地特性，则它们地操作可递归地描述。例如，链表的定义、创建和遍历链表结点，均可采用递归的方法。
  • 问题的解法是递归的。如Hanoi塔。

在高级语言编制的程序中，调用函数和被调用函数之间的链接及信息交换需要通过栈来进行。通常，当一个函数运行期间调用另一个函数时，在运行被调用函数之前，系统需要先完成三件事：
(1) 将所有的实参、返回地址等信息传递给被调用函数保存；
(2) 为被调用函数的局部变量分配存储区；
(3) 将控制转移到被调函数的入口。
而从被调用函数返回调用函数之前，系统也应完成3件工作：
(1) 保存被调函数的计算结果；
(2) 释放被调函数的数据区
(3) 依照被调函数保存的返回地址将控制转移到调用函数。

• 当有多个函数构成嵌套调用时，按照"后调用先返回"的原则。
• 调用函数和被调函数间的信息传递和控制转移需要通过栈来实现，即系统将整个程序运行时所需的数据空间安排在一个栈中，每当调用一个函数时，就为它在栈顶分配一个存储区，每当从一个函数退出时，就释放他的存储区，则当前正运行的函数的数据区就必在栈顶。
• 递归程序在执行时需要系统提供隐式的工作栈来保存调用过程中的参数、局部变量和返回地址，因此递归程序占用内存空间较多，运行效率较低。

7.3 Go语言与栈

7.3.1 Go语言在设计函数调用惯例时选择了使用栈来传递参数和返回值。

• 优点：降低实现的复杂度并支持多返回值，使得编译器更加简单，易于维护。
  • 不需要考虑超过寄存器数量的参数应该如何传递；
  • 不需要考虑不同架构上的寄存器差异；
  • 函数入参和出参的内存空间需要在栈上进行分配。
• 缺点：牺牲了函数调用的性能。

7.3.2 Go语言defer语句

• defer语句用于延迟函数的调用，常用于关闭文件描述符，释放锁等资源释放场景。
• defer语句采用后进先出的设计，类似与栈的方式，函数执行时，每遇到一个defer都会把一个函数压入栈中，多个defer形成一个单链表，函数返回前再将函数从栈中取出该单链表，按照后进先出的方式执行。

7.4 参考资料

栈与递归
Go语言设计和实现
《Go专家编程》

有疑问加站长微信联系（非本文作者）

本文来自：简书

感谢作者：Zppj

查看原文：go语言链栈的表示和实现