线性表之-栈

ByWhat'sUs

线性表之-栈

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

栈支持通过数组或链表实现，通过数组实现的通常叫做顺序栈，通过链表实现的叫做链栈。通过链表实现没有空间限制，并且插入和删除元素的效率更高，显然更加合适一些，下面我们基于 Go 语言来实现一个简单的链栈。

链栈本质上就是一个特殊的链表，特殊之处在于只能从头部插入节点，然后从头部读取（并删除）节点，因此实现起来非常简单，我们为这个栈提供了进栈、出栈和遍历功能：

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)
}