【数据结构与算法】栈

一、是什么

一种先进后出的线性表数据结构，只支持出栈和入栈操作

二、使用场景

• 函数调用栈（先定义的局部变量，最晚释放）
• 浏览器的前进后退
• 编译器通过两个栈，进行加减乘除计算

三、工作原理

只在栈顶插入或删除数据

四、实现

• 代码实现

type stack []interface{}

func NewStack() *stack {
    newStack := make(stack, 0)
    return &newStack
}

func stackPush(newStack *stack, a ...interface{}) {
    *newStack = append(*newStack, a...)
}

func stackPop(newStack *stack) (stackObj interface{}) {
    length := len(*newStack)
    if length <= 0 {
        return flase
    }
    stackObj = (*newStack)[length-1]
    *newStack = (*newStack)[:length-1]
    return
}

• Redis实现

lpush + lpop = stack（栈）

五、优劣

• 优点：

1. 出栈和入栈的时间复杂度都为 O(1)
2. 操作受限，使用比较可控，不容易出错（和数组、链表相比较）

• 缺点：

1. 在内存中，栈结构里的数据大小和生命周期是固定的，缺乏灵活性

六、替代性技术

• 数组
• 链表

七、经典应用

内存分为栈、堆、静态数据区、代码区四个部分：

• 栈： 空间小，与cpu结合灵活，释放也灵活，适合存定长的数据
• 堆： 空间大，一般数组、字符串、对象保存在堆中
• 静态数据区： 存储全局变量、静态变量、常量，释放不灵活
• 代码区： 保存代码结构

八、延伸应用

单调栈

定义： 满足单调性（递增 or 递减）的栈结构（PS：类似的应用还有单调队列）

实现： 为了保持栈内的单调性，在进栈时需要做元素的检查工作。以递增栈（栈顶到栈尾的顺序是递增的，小的先出栈，大的最后出栈）为例：如果发现待进栈的元素比目前栈顶元素大，如果此时入栈则会破坏栈内的单调性，所以需要将目前比待入栈元素大的栈顶元素弹出，弹出后继续比较待入栈元素和新栈顶元素的大小，直到待入栈元素小于栈顶元素或者栈为空，可将该元素进栈

代码实现：

// 单调递增栈：栈顶到栈底递增
func dandiaoAddStack(height []int) (result []int) {
    current := 1
    stack := []int{height[0]}
    for {
        // 如果游标是否到达尾部
        if current > len(height) - 1 {
            break
        }
        // 循环比较栈顶元素和待入栈元素
        for {
            // 如果栈为空，则直接跳出循环
            if len(stack) == 0 {
                break
            }
            if height[current] > stack[len(stack)-1] {
                // 栈顶元素出栈
                stack = stack[:len(stack)-1]
            } else {
                break
            }
        }
        stack = append(stack,height[current])
        current++
    }

    return stack
}

功能用途： 由于栈内元素时刻保持单调性，所以在遇见待进栈的元素比栈顶元素小时，对于当前栈顶元素，这个待进栈的元素是它第一次见到的比它小的元素。利用这一性质，可以求一个元素 左/右 边第一个比它 大/小 的元素

应用实例：

• leetcode - 42 接雨水