栈

后进者先出，先进者后出，这就是典型的“栈”结构。

栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。

从功能上来说，数组或链表确实可以替代栈，但特定的数据结构是对特定场景的抽象，而且，数组或链表暴露了太多的操作接口，操作上的确灵活自由，但使用时就比较不可控，自然也就更容易出错。

当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，就应该首选“栈”这种数据结构。

实现栈

栈主要包含两个操作:

• 入栈：在栈顶插入一个数据。

• 出栈：从栈顶删除一个数据。

栈既可以用数组来实现，也可以用链表来实现。

• 用数组实现的栈，我们叫作顺序栈。

• 用链表实现的栈，我们叫作链式栈。

不管是顺序栈还是链式栈，存储数据只需要一个大小为 n 的空间就够了。

• 入栈和出栈过程中，只需要一两个临时变量存储空间，所以空间复杂度是 O(1)。

• 入栈和出栈过程中，只涉及栈顶个别数据的操作，所以时间复杂度都是 O(1)。

注意，存储数据需要一个大小为 n 的空间，并不是说空间复杂度就是 O(n)。因为，这 n 个空间是必须的，无法省掉。所以说空间复杂度的时候，是指除了原本的数据存储空间外，算法运行还需要额外的存储空间。

动态扩容

• 顺序栈在初始化时需要事先指定栈的大小。

• 链式栈大小虽然不受限制，但是存储next指针，内存消耗相对较多。

数组动态扩容：当数组空间不够时，我们就重新申请一块更大的内存，将原来数组中数据统统拷贝过去。

如果要实现一个支持动态扩容的栈，只需要底层依赖一个支持动态扩容的数组就可以了。实际上，支持动态扩容的顺序栈，平时开发中并不常用到。此时出栈的时间复杂度是O（1），入栈的时间复杂度分为有空间O(1)和需要扩容O(n)，入栈的均摊时间复杂度为O(1)。

栈的应用

栈在函数中的应用

栈比较经典的一个应用场景就是函数调用栈。

操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成“栈”这种结构, 用来存储函数调用时的临时变量。每进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。

func main() {
 a, ret, res := 1, 0, 0
 ret = add(3, 5)
 res = a + ret
 fmt.Printf("%d", res)
}

func add(x, y int) int {
 sum := 0
 sum = x + y
 return sum
}

上面代码main()函数调用add()函数，获取计算结果，并且与临时变量a相加，最后打印res的值。在执行add()函数时，函数调用栈的情况如下图：

栈在函数中的应用

栈在表达式求值中的应用

编译器通过两个栈实现表达式求值，其中一个栈保存操作数，另一个栈保存运算符。

1. 从左向右遍历表达式

2. 当遇到数字，直接压入操作数栈

3. 当遇到运算符，就与运算符栈的栈顶元素比较

   1. 如果比栈顶元素优先级高，就将当前运算符压入栈

   2. 如果比栈顶元素优先级低或相同，从运算符栈中取栈顶元素，从操作数栈中取两个操作数，进行计算

4. 把计算结果压入栈操作数栈

5. 继续

如下示例为计算3+5*8-6：

栈在表达式求值中的应用

示例代码

求后缀表达式（逆波兰表达式）使用一个栈来存储操作数：

1. 读取后缀表达式，当遇到操作数直接入栈

2. 当遇到运算符，则从栈中出栈两个数，根据运算符运算后将结果再入栈

3. 不断重复，得到结果

func evalRPN(tokens []string) int {
    if len(tokens) == 0 {
        return 0
    }
    stack := make([]int, 0)
    for i := 0; i < len(tokens); i++ {
        // 判断是操作符还是操作数
        switch tokens[i] {
        case "+", "-", "*", "/":// 判断具体的操作符
            if len(stack) < 2 {
                return -1
            }
            // 这里注意a和b的先后顺序
            b := stack[len(stack)-1]
            a := stack[len(stack)-2]
            stack = stack[:len(stack)-2]
            res := 0
            switch tokens[i] {
            case "+":
                res = a + b
            case "-":
                res = a - b
            case "*":
                res = a * b
            case "/":
                res = a / b
            }
            stack = append(stack, res)
        default:
        // 操作数则转为int后直接入栈
            val, _ := strconv.Atoi(tokens[i])
            stack = append(stack, val)
        }
    }
    // 最终栈中只要一个元素就是结果
    return stack[0]
}

栈在括号匹配中的应用

假设表达式中只包含三种括号：

• 圆括号()

• 方括号[]

• 花括号{}

它们可以任意嵌套。

比如：

• 合法格式：{[]()[{}]}或[{()}([])]等

• 不合法格式：{[}()]或[({)]等

用栈来判断一个包含三种括号的表达式字符串是否合法。

1. 用栈来保存未匹配的左括号，从左到右依次扫描字符串

2. 当扫描到左括号时，则将其压入栈中

3. 当扫描到右括号时，从栈顶取出一个左括号

   1. 如果能够匹配，比如“(”跟“)”匹配，“[”跟“]”匹配，“{”跟“}”匹配，则继续扫描剩下的字符串

   2. 如果扫描的过程中，遇到不能配对的右括号，或者栈中没有数据，则说明为非法格式

4. 当所有的括号都扫描完成之后，如果栈为空，则说明字符串为合法格式；否则，说明有未匹配的左括号，为非法格式

示例代码

// 判断括号是否有效
func isValid(s string) bool {
    n := len(s)
    // 长度小2或者是奇数个直接false
    if n < 2 || n%2 != 0 {
        return false
    }

    stack := make([]byte, 0)
    // 注意这里是一个逆向思维
    dict := map[byte]byte{
        ')': '(',
        '}': '{',
        ']': '[',
    }

    for i := 0; i < n; i++ {
        if _, ok := dict[s[i]];!ok {
            stack = append(stack, s[i])
        } else {
            if len(stack) < 1 {
                return false
            } else {
                if dict[s[i]] == stack[len(stack)-1] {
                    stack = stack[:len(stack)-1]
                } else {
                    stack = append(stack, dict[s[i]])
                }
            }
        }
    }

    if len(stack) == 0 {
        return true
    } else {
        return false
    }
}

栈在浏览器中的应用

使用两个栈实现浏览器中前进后退的功能，假设两个栈分别为X和Y。

1. 把首次浏览的页面压入栈X

2. 当点击后退按钮时，再依次从栈X中出栈，并将出栈的数据依次压入栈Y中

3. 当点击前进按钮时，再依次从栈Y中出栈，并将出栈的数据依次压入栈X中

4. 当X中没有数据，说明没有可以继续后退浏览的页面

5. 当Y中没有数据，说明没有可以继续前进浏览的页面

常见考点

最小栈

设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。

思路

用两个栈实现，一个数据栈，一个最小栈，在最小栈中始终保证最小值在栈顶。

入栈Push操作：

1. 从最小栈顶获取当前最小值，判断待入栈的值与当前最小值的大小

2. 如果待入栈的值更小，则将这个值同时放入数据栈和最小栈的栈顶

3. 否则将当前最小值再次入栈，将待入栈的值放入数据栈的栈顶（因为出栈的时候同时删除两个栈的栈顶元素）

出栈Pop操作：

1. 如果数据栈为空，则直接返回

2. 否则同时将数据栈和最小栈的栈顶元素出栈

获取栈顶元素Top操作：

1. 如果数据栈为空，则直接返回0

2. 否则返回数据栈的栈顶元素

示例代码

type MinStack struct {
    min   []int
    stack []int
}

func New() MinStack {
    return MinStack{min: make([]int, 0), stack: make([]int, 0)}
}

// 入栈
func (s MinStack) Push(x int) {
    min := s.GetMin()
    if x < min {
        s.min = append(s.min, x)
    }else{
      s.min = append(s.min, min)
   }
    s.stack = append(s.stack, x)
}

// 出栈
func (s MinStack) Pop() {
    if len(s.stack) == 0 {
        return
    }
    s.stack = s.stack[:len(s.stack)-1]
    s.min = s.min[:len(s.min)-1]
}

// 获取（数据栈）栈顶元素
func (s MinStack) Top() int {
    if len(s.stack) == 0 {
        return 0
    }
    return s.stack[len(s.stack)-1]
}

// 获取最小值 O(1)时间复杂度
func (s MinStack) GetMin() int {
    if len(s.min) == 0 {
        return 1<<31 - 1
    }
    return s.min[len(s.min)-1]
}

解码字符串

给定一个经过编码的字符串，返回它解码后的字符串。编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。输入：s = "3[a2[c]]"，输出："accaccacc"。

思路

通过栈辅助进行操作，从前往后遍历字符串。

1. 判断当前读取到的是否为]，如果不是则直接入栈

2. 否则，将栈中元素出栈并保存到临时数组中，直到栈顶元素为[

3. 将栈顶的[出栈

4. 判断[前有几个数字

5. 将对应位数的数字出栈

6. 将临时数字中的字符从后往前放回栈中（注意临时数组中的字符是逆序的，因为执行了入栈和出栈操作），重复多次直到与对应数字相等

7. 输出栈中的内容就是结果

示例代码

func decodeString(s string) string {
    if len(s) == 0 {
        return ""
    }
    stack := make([]byte, 0)
    for i := 0; i < len(s); i++ {
        switch s[i] {
        case ']':
            temp := make([]byte, 0)
            for len(stack) != 0 && stack[len(stack)-1] != '[' {
                v := stack[len(stack)-1]
                stack = stack[:len(stack)-1]
                temp = append(temp, v)
            }
            // pop '['
            stack = stack[:len(stack)-1]
            // pop num
            idx := 1
            for len(stack) >= idx && stack[len(stack)-idx] >= '0' && stack[len(stack)-idx] <= '9' {
                idx++
            }
            // 注意索引边界
            num := stack[len(stack)-idx+1:]
            stack = stack[:len(stack)-idx+1]
            count, _ := strconv.Atoi(string(num))
            for j := 0; j < count; j++ {
                // 把字符正向放回到栈里面
                for j := len(temp) - 1; j >= 0; j-- {
                    stack = append(stack, temp[j])
                }
            }
        default:
            stack = append(stack, s[i])

        }
    }
    return string(stack)
}

栈实现队列

使用栈实现队列的push、pop、peek、empty操作。

思路

栈是先进后出的，队列是先进先出的，因此需要使用一个入队栈，一个出队栈来实现。

1. 入队时，如果入队栈为空，则直接入队

2. 否则将入队栈中的元素全部出栈并压入出队栈，然后将待入队的数据压入队栈

3. 出队时，如果出队栈有数据，则直接将出队栈栈顶的元素出栈

4. 否则将入队栈中的元素全部出栈并压入出队栈，然后在将出队栈栈顶元素出栈

示例代码

type MyQueue struct {
    in  []int
    out []int
}

/** Initialize your data structure here. */
func Constructor() MyQueue {
    return MyQueue{in: make([]int, 0), out: make([]int, 0)}
}

/** Push element x to the back of queue. */
func (q *MyQueue) Push(x int) {
    // 如果入队栈不为空
    // 入队栈中元素先出栈到出队栈中，再入队
    for len(q.in) != 0 {
        val := q.in[len(q.in)-1]
        q.in = q.in[:len(q.in)-1]
        q.out = append(q.out, val)
    }
    // 如果入队栈为空，直接入队
    q.in = append(q.in, x)
}

/** Removes the element from in front of queue and returns that element. */
func (q *MyQueue) Pop() int {
    if len(q.out) != 0 {
        res := q.out[len(q.out)-1]
        q.out = q.out[:len(q.out)-1]
        return res
    }
    for len(q.in) != 0 {
        val := q.in[len(q.in)-1]
        q.in = q.in[:len(q.in)-1]
        q.out = append(q.out, val)
    }
    res := q.out[len(q.out)-1]
    q.out = q.out[:len(q.out)-1]
    return res
}

/** Get the front element. */
func (q *MyQueue) Peek() int {
    if len(q.out) != 0 {
        return q.out[len(q.out)-1]
    }
    for len(q.in) != 0 {
        val := q.in[len(q.in)-1]
        q.in = q.in[:len(q.in)-1]
        q.out = append(q.out, val)
    }
    return q.out[len(q.out)-1]
}

/** Returns whether the queue is empty. */
func (q *MyQueue) Empty() bool {
    return len(q.in) == 0 && len(q.out) == 0
}