数据结构基础 入门——栈

用 Go 来实现链表、栈、队列、散列表、树、二叉树、堆、图

线性结构：数据组成一条线的结构，只有前后方向（数据 链表 栈 队列）
非线性结构：树、二叉树、堆、图

栈的认识

第一印象：先进后出结构

栈（Stack）又叫堆栈，是限定只能在一端进行插入和删除操作的线性表，并且满足后进先出（LIFO）的特点，即最后插入的最先被读取。我们把允许插入和删除的一端叫做栈顶，另一个端叫做栈底，不含任何数据的栈叫做空栈。

栈支持通过数组或链表实现，通过数组实现的通常叫做顺序栈，通过链表实现的叫做链栈。

常见应用场景

栈在日常开发和软件使用中，应用非常广泛，比如我们的浏览器前进、倒退功能，编辑器/IDE 中的撤销、取消撤销功能，程序代码中的函数调用、递归、四则运算等等

用链表实现

package main

import "fmt"

//定义链表节点
type Node struct {
    Value int
    Next  *Node
}

//初始化栈结构（空栈）
var size = 0
var stack = new(Node)

//进栈
func Push(v int) bool {
    // 空栈的话直接将值放入头节点即可
    if stack == nil {
        stack = &Node{v, nil}
        size = 1
        return true
    }

    //否则将插入节点作为栈的头节点
    temp := &Node{v, nil}
    temp.Next = stack
    stack = temp
    size++
    return true
}

//出栈
func Pop(t *Node) (int, bool) {
    //空栈
    if size == 0 {
        return 0, false
    }

    //只有一个节点
    if size == 1 {
        size = 0
        stack = nil
        return t.Value, true
    }

    //将栈的头节点指针向下一个节点，并返回之前的节点数据
    stack = stack.Next
    size--
    return t.Value, true
}

//遍历（不删除任何节点，只读取值）
func traverse(t *Node) {
    if size == 0 {
        fmt.Println("空栈！")
        return
    }

    for t != nil { //单个循环条件
        fmt.Printf("%d -> ", t.Value)
        t = t.Next //这一句省略将死循环
    }
    fmt.Println()
}

func main() {
    stack = nil
    //读取空栈
    v, b := Pop(stack)
    if b {
        fmt.Print(v, "")
    } else {
        fmt.Println("Pop() 失败！")
    }

    //进栈
    Push(100)
    //遍历栈
    traverse(stack)
    //再次进栈
    Push(200)
    //再次遍历栈
    traverse(stack)

    //批量进栈
    for i := 0; i < 10; i++ {
        Push(i)
    }

    //批量出栈
    for i := 0; i < 15; i++ {
        v, b := Pop(stack)
        if b {
            fmt.Print(v, " ")
        } else {
            //如果是空栈 则退出循环
            break
        }
    }

    fmt.Println()
    //再次遍历栈
    traverse(stack)
}

$ go run xxx.go

Pop() 失败！
100 ->
200 -> 100 ->
9 8 7 6 5 4 3 2 1 0 200 100 
空栈！

参考链接

geekr.dev/posts/go-data-structure-...

本作品采用《CC 协议》，转载必须注明作者和本文链接