介绍

栈（Stack）是一种具有后进先出（LIFO，Last-In-First-Out）特性的数据结构。类比现实生活中的栈，可以将其想象成一叠盘子，只能从最顶端放入或取出盘子。

栈的主要操作有两个：

• 入栈（Push）：将元素放入栈的顶端，成为栈的新的顶端元素。
• 出栈（Pop）：从栈的顶端取出元素，并将栈的顶端指向下一个元素。

除了入栈和出栈操作之外，栈还有一些其他的常见操作：

• 查看栈顶元素（Peek）：返回栈的顶端元素，但不对栈进行修改。
• 判断栈是否为空（IsEmpty）：检查栈是否不包含任何元素。
• 获取栈的大小（Size）：返回栈中元素的个数。

栈的应用场景包括但不限于：

• 表达式求值：在计算机科学中，栈被广泛用于表达式求值，如括号匹配、中缀表达式转后缀表达式等。
• 函数调用：函数调用时，函数的局部变量和参数值通常存储在一个被称为栈帧的数据结构中，每次函数调用时都会将栈帧入栈，函数返回时再将其出栈。
• 浏览器历史记录：浏览器的返回按钮通常使用栈来记录访问页面的历史记录，每次访问新页面时将其入栈，返回时则将其出栈。

栈可以使用不同的数据结构来实现，常见的实现方式包括基于数组、链表或切片等。

代码示例

切片方式

package main

import "fmt"

type Stack struct {
    // data字段使用切片来存储栈中的元素
    data []interface{}
}

// Push 将元素入栈，将新元素追加到切片的末尾
func (s *Stack) Push(item interface{}) {
    s.data = append(s.data, item)
}

// Pop 将栈顶元素出栈，即取出切片的最后一个元素，并将切片长度减一
func (s *Stack) Pop() interface{} {
    if len(s.data) == 0 {
        return nil
    }
    // len(s.data)-1表示栈顶元素在切片s.data中的索引，通过索引访问栈顶元素，并将其赋值给变量item
    item := s.data[len(s.data)-1]
    // 从切片的开头到栈顶元素前一个位置的子切片，即移除了栈顶元素
    s.data = s.data[:len(s.data)-1]
    // 返回变量item，即出栈的栈顶元素
    return item
}

// Peek 返回栈顶元素，但不将其出栈
func (s *Stack) Peek() interface{} {
    if len(s.data) == 0 {
        return nil
    }
    return s.data[len(s.data)-1]
}

// IsEmpty 判断栈是否为空，即切片的长度是否为零
func (s *Stack) IsEmpty() bool {
    return len(s.data) == 0
}

func main() {
    stack := &Stack{}

    stack.Push(1)
    stack.Push(2)
    stack.Push(3)

    fmt.Println(stack.Pop())
    fmt.Println(stack.Pop())
    fmt.Println(stack.Peek())
    fmt.Println(stack.IsEmpty())
    fmt.Println(stack.Pop())
    fmt.Println(stack.IsEmpty())
}

3
2
1
false
1
true

数组方式

使用数组来实现栈时，需要预先指定存储元素的数组大小。原因如下：

• 内存分配：数组在内存中是连续分配的，因此需要预先知道数组的大小，以便一次性分配足够的内存空间。如果没有预先指定大小，那么每次入栈时都需要进行动态内存分配和拷贝，效率较低。
• 性能：预先指定数组大小可以避免频繁的内存分配和释放操作，提高了程序的性能。相比动态调整数组大小的实现方式，固定大小的数组实现更加高效。
• 空间限制：数组的大小是固定的，预先指定大小可以限制栈的容量，避免无限制地扩展栈的大小，从而控制内存的使用。

需要注意的是，预先指定数组大小也存在一定的限制，如果栈的元素数量超过了预先指定的大小，就会发生栈溢出。因此，在选择数组大小时需要根据实际应用场景和需求来合理确定。

package main

import "fmt"

type Stack struct {
    // 用于存储栈中的元素的数组
    data []interface{}
    // 表示栈顶元素在数组中的索引
    top int
    // 表示栈的最大容量
    size int
}

// NewStack 创建一个新的栈对象，接收一个整数参数size作为栈的最大容量，并返回一个指向栈的指针
func NewStack(size int) *Stack {
    return &Stack{
        // 创建了一个大小为size的切片
        data: make([]interface{}, size),
        // top初始化为-1，表示初始时栈是空的
        top:  -1,
        size: size,
    }
}

// Push 将元素入栈，将新元素追加到切片的末尾
func (s *Stack) Push(item interface{}) {
    // 检查栈是否已满，如果栈满了，就不能再入栈
    if s.top == s.size-1 {
        fmt.Println("stack is full")
        return
    }
    // 将栈顶元素索引加一
    s.top++
    // 将元素存储到data数组的对应位置
    s.data[s.top] = item
}

// Pop 将栈顶元素出栈，即取出切片的最后一个元素，并将切片长度减一
func (s *Stack) Pop() interface{} {
    // 检查栈是否为空，如果栈为空，就不能再出栈
    if s.top < 0 {
        fmt.Println("stack is empty")
        return nil
    }
    // 将栈顶元素存储到变量item中
    item := s.data[s.top]
    // 将栈顶元素从数组中删除
    s.data = s.data[:s.top]
    // 将栈顶元素索引减一
    s.top--
    return item
}

// Peek 返回栈顶元素，但不将其出栈
func (s *Stack) Peek() interface{} {
    if s.top < 0 {
        fmt.Println("stack is empty")
        return nil
    }
    // 直接返回栈顶元素
    return s.data[s.top]
}

// IsEmpty 判断栈是否为空
func (s *Stack) IsEmpty() bool {
    // 如果栈顶指针top小于0，则表示栈为空，返回true，否则返回false。
    return s.top < 0
}

func main() {
    stack := NewStack(5)
    stack.Push(1)
    stack.Push(2)
    stack.Push(3)
    fmt.Println(stack.data)

    fmt.Println(stack.Pop())
    fmt.Println(stack.Pop())
    fmt.Println(stack.Peek())
    fmt.Println(stack.data)
    fmt.Println(stack.IsEmpty())
}

[1 2 3 <nil> <nil>]
3
2
1
[1]
&{[1] 0 5}
false

链表方式

使用链表来实现栈时，不需要预先指定存储元素的容量，因为链表的大小可以根据需要进行动态调整。

package main

import "fmt"

// Node 定义链表即栈的节点
type Node struct {
    // data字段用于存储元素值
    data interface{}
    // next字段指向下一个节点
    next *Node
}

// Stack 定义栈
type Stack struct {
    // 指向栈顶节点的指针top
    top *Node
}

// NewStack 创建一个新的栈对象
func NewStack() *Stack {
    // 返回一个指向栈的指针，并将栈的初始状态设置为top为空，size为0
    return &Stack{
        top: nil,
    }
}

// Push 将元素入栈，将新元素追加到链表的末尾
func (s *Stack) Push(item interface{}) {
    // 创建一个新的节点
    node := &Node{
        // 元素存储到node的data字段
        data: item,
        // 将node的next指向当前栈顶节点top
        next: s.top,
    }
    // 将栈顶节点更新为node
    s.top = node
}

func (s *Stack) Pop() interface{} {
    // 检查栈是否为空，如果栈为空，就不能再出栈
    if s.top == nil {
        fmt.Println("stack is empty")
        return nil
    }
    // 将栈顶元素存储到变量item中
    item := s.top.data
    // 将栈顶元素从链表中删除
    s.top = s.top.next
    return item
}

// Peek 返回栈顶元素，但不将其出栈
func (s *Stack) Peek() interface{} {
    if s.top == nil {
        fmt.Println("stack is empty")
        return nil
    }
    return s.top.data
}

func (s *Stack) IsEmpty() bool {
    return s.top == nil
}

func main() {
    stack := NewStack()
    stack.Push(1)
    stack.Push(2)
    stack.Push(3)

    fmt.Println(stack.Pop())
    fmt.Println(stack.Pop())
    fmt.Println(stack.Peek())
    fmt.Println(stack.IsEmpty())
}

3
2
1
false