数据结构基础 入门——栈

用 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 协议》,转载必须注明作者和本文链接
滴水穿石,石破天惊----马乂
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!