栈 - 简书

栈

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

我们可以把它想象成吃零食的薯片桶，打开薯片桶之后，每次只能拿到最上面的薯片。如图所示，我们把堆叠元素的顶部称为”栈顶“，底部元素称为”栈底“。将把元素添加到栈顶的操作叫做“入栈",删除栈顶元素的操作叫做“出栈”。

栈操作

栈的常用操作

通常情况下，我们可以直接使用编程语言内置的栈类。然而某些语言可能并不提供专门的栈类，这时我们可以将该语言的“数组”或“链表”当作栈来使用，并在逻辑上忽略栈无关的操作。
栈的常用操作有

push(), 元素入栈，将元素添加至栈顶，时间复杂度O(1)
pop(), 元素出栈，将栈顶元素删除，时间复杂度尾O(1)
peek(),访问栈顶元素，时间复杂度O(1)

var stack []int
// 元素入栈
stack = append(stack, 1)
stack = append(stack,2)

// 元素出栈
pop := stack[len(stack)-1]
stack = stack[:len(stack)-1]

// 访问栈顶元素
peek := stack[len(stack)-1]

// 获取栈的长度
size := len(stack)

// 是否为空判断
isEmpty := len(stack) == 0

栈的实现

栈遵循先入后出的原则，因此我们只能在栈顶添加或删除元素，然而，数组和链表都可以在任意位置添加和删除元素，因此栈可以视为一种受限制的数组或链表.换句话说，我们可以屏蔽数组或链表的部分无关操作，使其对外表现得逻辑符合栈的特性。

1. 基于链表的实现

使用链表实现栈时，我们可以将链表头节点视为栈顶，尾节点视为栈底。因为链表是顺序访问的，头节点是我们最先访问的元素，尾节点是最后访问的元素，这个栈的特性一致。
对于入栈操作，我们只需将元素插入链表头部，这种插入方法成为”头插法“。
对于出栈操作，我们只需将头节点从链表中删除。

package main

import (
    "container/list"
    "fmt"
)

type Stack struct {
    *list.List
}

func NewStack() *Stack {
    return &Stack{
        List: list.New(),
    }
}

// 入栈，将元素添加至栈顶，也就是链表的头节点
func (s *Stack) Push(element interface{}) {
    s.List.PushBack(element)
}

// 出栈，将栈顶元素删除，
func (s *Stack) Pop() interface{} {
    if s.IsEmpty() {
        return nil
    }
    e := s.List.Back()
    s.List.Remove(e)
    return e.Value
}

func (s *Stack) Peek() interface{} {
    return s.List.Front()
}

func (s *Stack) Size() int {
    return s.List.Len()
}

func (s *Stack) IsEmpty() bool {
    return s.List.Len() == 0
}

func main() {
    var s = NewStack()
    s.Push(1)
    s.Push(2)
    s.Push(3)
    fmt.Println(s.Pop(), s.Size())
    fmt.Println(s.Pop(), s.Size())
    fmt.Println(s.Pop(), s.Size())
}
/* 输出结果
3
3 2
2 1
1 0
*/

1. 基于数组的实现

使用数组实现栈时，我们可以将数组的尾部作为栈顶，入栈和出栈操作均在数组尾部进行。时间复杂度为O(1)

type StackArray struct {
    data []interface{}
}

func NewStackArray() *StackArray {
    return &StackArray{}
}

func (s *StackArray) Push(element interface{}) {
    s.data = append(s.data, element)
}

// 出栈，将栈顶元素删除，
func (s *StackArray) Pop() interface{} {
    if s.IsEmpty() {
        return nil
    }

    e := s.data[len(s.data)-1]
    s.data = s.data[:len(s.data)-1]
    return e
}

func (s *StackArray) Peek() interface{} {
    if s.IsEmpty() {
        return nil
    }
    return s.data[len(s.data)-1]
}

func (s *StackArray) Size() int {
    return len(s.data)
}

func (s *StackArray) IsEmpty() bool {
    return len(s.data) == 0
}

两种实现对比

时间效率

在基于数组的实现中，入栈和出栈操作都在预先分配好的连续内存中进行，具有很好的缓存本地性，因此效率较高。如果入栈时超出数组容量，会触发扩容机制，导致该入栈操作的时间复杂度变为O(n)。
在基于链表的实现中，链表的扩容十分灵活，不会出现扩容导致的效率地下问题。但是入栈操作需要初始化节点对象并修改指针，因此效率相对较低。
综上所述，当入栈与出栈操作的元素是基本数据类型时，我们可以得出以下结论：

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

栈的典型应用

程序内存管理
每次调用函数时，系统都会在栈顶添加一个栈帧，用于记录函数的上下文信息，在递归函数中，向下递推阶段会不断执行入栈操作，而向上回溯阶段则会不断执行出栈操作。

栈

栈