栈

栈(stack)是一种遵循先入后出逻辑的线性数据结构。

我们把堆叠元素的顶部称为“栈顶”，底部称为“栈底”。将把元素添加到栈顶的操作叫作“入栈”，删除栈顶元素的操作叫作“出栈”。

stack

常见操作

在此，我们以常见的 push()、pop()、peek() 命名为例。

方法	描述	时间复杂度
`push()`	元素入栈（添加至栈顶）	$O(1)$
`pop()`	栈顶元素出栈	$O(1)$
`peek()`	访问栈顶元素	$O(1)$

/* 初始化栈 */
// 在 Go 中，推荐将 Slice 当作栈来使用
var stack []int
 
/* 元素入栈 */
stack = append(stack, 1)
stack = append(stack, 3)
stack = append(stack, 2)
stack = append(stack, 5)
stack = append(stack, 4)
 
/* 访问栈顶元素 */
peek := stack[len(stack)-1]
 
/* 元素出栈 */
pop := stack[len(stack)-1]
stack = stack[:len(stack)-1]
 
/* 获取栈的长度 */
size := len(stack)
 
/* 判断是否为空 */
isEmpty := len(stack) == 0

基于链表实现栈

使用链表实现栈时，我们可以将链表的头节点视为栈顶，尾节点视为栈底。

入链表头部，这种节点插入方法被称为“头插法”。而对于出栈操作，只需将头节点从链表中删除即可

/* 基于链表实现的栈 */
type linkedListStack struct {
    // 使用内置包 list 来实现栈
    data *list.List
}
 
/* 初始化栈 */
func newLinkedListStack() *linkedListStack {
    return &linkedListStack{
        data: list.New(),
    }
}
 
/* 入栈 */
func (s *linkedListStack) push(value int) {
    s.data.PushBack(value)
}
 
/* 出栈 */
func (s *linkedListStack) pop() any {
    if s.isEmpty() {
        return nil
    }
    e := s.data.Back()
    s.data.Remove(e)
    return e.Value
}
 
/* 访问栈顶元素 */
func (s *linkedListStack) peek() any {
    if s.isEmpty() {
        return nil
    }
    e := s.data.Back()
    return e.Value
}
 
/* 获取栈的长度 */
func (s *linkedListStack) size() int {
    return s.data.Len()
}
 
/* 判断栈是否为空 */
func (s *linkedListStack) isEmpty() bool {
    return s.data.Len() == 0
}
 
/* 获取 List 用于打印 */
func (s *linkedListStack) toList() *list.List {
    return s.data
}

基于数组实现栈

由于入栈的元素可能会源源不断地增加，因此我们可以使用动态数组，这样就无须自行处理数组扩容问题。

/* 基于数组实现的栈 */
type arrayStack struct {
    data []int // 数据
}
 
/* 初始化栈 */
func newArrayStack() *arrayStack {
    return &arrayStack{
        // 设置栈的长度为 0，容量为 16
        data: make([]int, 0, 16),
    }
}
 
/* 栈的长度 */
func (s *arrayStack) size() int {
    return len(s.data)
}
 
/* 栈是否为空 */
func (s *arrayStack) isEmpty() bool {
    return s.size() == 0
}
 
/* 入栈 */
func (s *arrayStack) push(v int) {
    // 切片会自动扩容
    s.data = append(s.data, v)
}
 
/* 出栈 */
func (s *arrayStack) pop() any {
    val := s.peek()
    s.data = s.data[:len(s.data)-1]
    return val
}
 
/* 获取栈顶元素 */
func (s *arrayStack) peek() any {
    if s.isEmpty() {
        return nil
    }
    val := s.data[len(s.data)-1]
    return val
}
 
/* 获取 Slice 用于打印 */
func (s *arrayStack) toSlice() []int {
    return s.data
}

两者对比

基于数组实现的栈在触发扩容时效率会降低，但由于扩容是低频操作，因此平均效率更高。
基于链表实现的栈可以提供更加稳定的效率表现。

栈的应用

浏览器中的后退与前进、软件中的撤销与反撤销。每当我们打开新的网页，浏览器就会对上一个网页执行入栈，这样我们就可以通过后退操作回到上一个网页。后退操作实际上是在执行出栈。如果要同时支持后退和前进，那么需要两个栈来配合实现。
程序内存管理。每次调用函数时，系统都会在栈顶添加一个栈帧，用于记录函数的上下文信息。在递归函数中，向下递推阶段会不断执行入栈操作，而向上回溯阶段则会不断执行出栈操作。
表达式求值。编译器利用栈来实现表达式求值。例如，编译器在编译表达式 1 + 2 * (3 - 4) 时，会将中缀表达式转换为后缀表达式 1 2 3 4 - * +，然后利用栈来实现后缀表达式的求值。
括号匹配。编译器利用栈来检查代码中的括号是否匹配。例如，编译器在编译代码 if (a == b) { c = d; } 时，会利用栈来检查括号是否匹配。

链表(linked list)队列(queue)