「数据结构&算法」必知必会系列：8. 常见数据结构——栈

系列文章请查看「数据结构&算法」必知必会系列：1. 开篇#计划路线

本文为系列文章：常见数据结构——栈，将具体介绍栈的特性和基本代码实现，另外列举了几个栈的具体应用场景。

栈的实现

栈(stack) 的数据结构较为简单，但在计算机中使用广泛。

栈最显著的特征是 LIFO (Last In, First Out,，后进先出)。

栈可以用很多生活中示例来理解，如堆叠的📚，放只能放在最上面，拿也只能先拿最上面的。

栈主要包含两个操作，入栈和出栈，它是一种 操作受限的线性表，只允许在一端插入和删除数据。

了解栈的定义和基本操作，我们如何用代码实现呢？

结合之前的基础数据结构，栈可以用数组（顺序栈）和链表（链式栈）实现。

用数组实现的栈，叫作顺序栈；用链表实现的栈，叫作链式栈。术语了解即可。

顺序栈

笔者使用 Go，结构体(struct) 类似其他语言的类(class)，简单定义一个存放 int 的栈，实现入栈 Push，出栈Pop即可

// Stack 是用于存放 int 的 栈
type Stack struct {
	nums []int
}

// NewStack 返回 *kit.Stack
func NewStack() *Stack {
	return &Stack{nums: []int{}}
}

// Push 入栈
func (s *Stack) Push(n int) {
	s.nums = append(s.nums, n)
}

// Pop 出栈
func (s *Stack) Pop() int {
	res := s.nums[len(s.nums)-1]
	s.nums = s.nums[:len(s.nums)-1]
	return res
}

https://goplay.tools/snippet/_w_ZiwI1-Nj 可自行 Play~

复杂度分析？🙌 入栈 O(1) 出栈O(1)

除了入栈和出栈，常用方法有从栈中获得顶部元素 ，通常我们定义其为 top 函数，自行 Coding 一下吧~

链式栈

用链表实现栈，使用链表头作为栈顶元素（思考下为什么使用链表头？），然后就先自行 Coding 一下吧~

对链表数据结构不熟悉的，可回炉「数据结构&算法」必知必会系列：6. 常见数据结构——链表（上）


type ListNode struct {
	val  int
	next *ListNode
}

// Stack 存放链表 list head
type Stack struct {
	head *ListNode
}

// NewStack 返回 *Stack nil
func NewStack() *Stack {
	return &Stack{nil}
}

// Push 入栈
func (s *Stack) Push(n int) {
	new := &ListNode{n, s.head}
	s.head = new
}

// Top 查看栈顶元素的值
func (s *Stack) Top() interface{} {
	if s.head == nil {
		return nil
	}
	return s.head.val
}

// Pop 出栈
func (s *Stack) Pop() interface{} {
	if s.head == nil {
		return nil
	}
	s.head = s.head.next
	if s.head == nil {
		return nil
	}
	return s.head.val
}

https://goplay.tools/snippet/rGLXqPYyksG 可自行 Play~

复杂度分析？🙌 入栈 O(1) 出栈O(1)

支持动态扩容的顺序栈

基于数组实现的栈（顺序栈），是一个固定大小的栈，也就是说，在初始化栈时需要事先指定栈的大小。当栈满之后，就无法再往栈里添加数据了。

而链式栈，大小不受限，但要存储 next 指针，内存消耗相对较多。

那我们如何基于数组实现一个可以支持动态扩容的栈呢？

我们需要底层依赖一个支持动态扩容的数组，当栈满了之后，我们就申请一个更大的数组，将原来的数据搬移到新数组中。

实际上，支持动态扩容的顺序栈，我们平时开发中并不常用到。但是，顺序栈存在的边界情况是我们需要了解并重视的。

栈的应用

函数调用栈

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

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

表达式求值

栈的另一个常见的应用场景，编译器利用栈来实现表达式求值。

除去括号等，将算数表达式简化为只包含加减乘除的四则运算，如：1+2*3-4/2。小学生可以口算出来，但对于计算机，理解表达式并不是易事。

实际上，编译器就是通过两个栈来实现的。其中一个保存操作数的栈，另一个是保存运算符的栈。我们从左向右遍历表达式，当遇到数字，我们就直接压入操作数栈；当遇到运算符，就与运算符栈的栈顶元素进行比较。

如果比运算符栈顶元素的优先级高，就将当前运算符压入栈；如果比运算符栈顶元素的优先级低或者相同，从运算符栈中取栈顶运算符，从操作数栈的栈顶取 2 个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较。

这样用两个栈来解决的思路是不是非常巧妙？有些 LeetCode 算法题也可用写入两个栈的思路来解题。

括号的匹配

除了用栈来实现表达式求值，我们还可以借助栈来检查表达式中的括号是否匹配。

假设表达式中只包含三种括号，圆括号 ()、方括号[]和花括号{}，并且它们可以任意嵌套。比如，{[] ()[{}]}或[{()}([])]等都为合法格式，而{[}()]或[({)]为不合法的格式。

现在给你一个包含三种括号的表达式字符串，如何检查它是否合法呢？这里也可以用栈来解决。

我们用栈来保存未匹配的左括号，从左到右依次扫描字符串。当扫描到左括号时，则将其压入栈中；当扫描到右括号时，从栈顶取出一个左括号。如果能够匹配，比如“(”跟“)”匹配，“[”跟“]”匹配，“{”跟“}”匹配，则继续扫描剩下的字符串。如果扫描的过程中，遇到不能配对的右括号，或者栈中没有数据，则说明为非法格式。

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

总结

栈（Stack）就是一种操作受限的线性表，只允许入栈和出栈，特性是 LIFO (Last In, First Out, 后进先出)。

栈可以用数组实现顺序栈，也可以用链表实现链式栈。你应该可以熟练地写出构造及 Push Pop 函数代码。

对程序来说，函数调用应该不陌生，其 后进先出 的特性，用栈来实现是很顺理成章的。

对于栈这一数据结构，我们理应熟知其特性，并能合理地运用于实际场景中。