数据结构与算法：线性表（二）—— 栈

发表于 | 更新于: | 分类于 | 阅读次数:
字数统计: 4.8k | 阅读时长 ≈ 19

理论篇

逻辑结构

栈(Stack)：只允许在一端进行插入或删除操作的线性表。

  • 栈顶：允许插入和删除的那一端
  • 栈底：不允许插入和删除的那一端

存储结构

栈多以顺序存储的方式进行存储，同时附设一个top指针指示当前栈顶位置。

C语言实现：

1
2
3
4
5
# define Maxsize 50
typedef strucet{
    Elemtype data[Maxsize];
    int top;
}

Python中的列表可直接作为栈的实现：

1
stack = []

栈也可以采用链式存储，将头结点作为栈顶，方便节点的插入和删除。

基本操作

  • 创建空栈：InitStack(S)
  • 入栈：push(S)
  • 出栈：pop(S)
  • 读取栈顶：gettop(S)
  • 判断栈是否为空：is_empty(S)

python实现：

1
2
3
4
5
6
7
8
9
10
11
12
# 创建空栈
stack = []
# 入栈
stack.append(obj)
# 出栈
p = stack.pop()
# 获取栈顶/栈底对象
stack[-1]
stack[0]
# 判断栈是否为空
if stack:
    pass

应用篇

栈的使用核心是解决以下三个问题(类似于递归)：

  1. 入栈和出栈条件(调用前的处理及返回条件)；
  2. 入栈元素(函数参数)；
  3. 出栈处理(返回后的处理)
1
2
3
4
5
6
7
# 将序列中的元素依次通过栈的处理
s = []
for i,value in enumerate(a):
    while s and condition(s[-1],value):
        top = s.pop()
        visit(top)
    s.append(value)

括号匹配

  • 问题：[LeetCode 20] 有效的括号
1
2
3
4
5
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效，有效字符串需满足：

1. 空字符串，或者满足以下两条
2. 左括号必须用相同类型的右括号闭合
3. 左括号必须以正确的顺序闭合
  • 思路：左空入栈，右出栈相消，不能消或者最终栈非空返回False
  • 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def isValid(self, s):
    """
    :type s: str
    :rtype: bool
    """
    d = {'(':')','[':']','{':'}',')':'(',']':'[','}':'{'}
    stack = []
    for c in s:
        if not stack or c in '({[':
            stack.append(c)
        elif stack[-1] == d[c]:
            stack.pop()
        else:
            return False
    return not stack

表达式计算

前/中/后缀表达式

常用的表达式：

  1. 中缀表达式：运算符位于操作数中间，运算符按照优先级依次运算。A+B×(C-D)-E/F；
  2. 前缀表达式：运算符位于操作数前面，运算符符自右向左依次运算。-+A×B-CD/EF；
  3. 后缀表达式：运算符位与操作数后面，运算符自左向右依次运算。ABCD-×+EF/-；

表达式是递归定义的，前一个运算符的运算结果会作为下一个运算符的操作数，下一个运算符的运算结果又会作为下下一个运算符的操作数，最终返回整个运算的结果。前缀表达式又称为波兰式，后缀表达式称为逆波兰式(Reverse Polish notation，RPN)。

表达式可以表示为一颗表达式树：运算符作为内部节点，操作数作为叶节点，子表达式作为内部节点的左右子树。

  1. 中缀表达式：对应表达式树的中序遍历
  2. 前缀表达式：对应表达式树的先序遍历
  3. 后缀表达式：对应表达式树的后序遍历

表达式转换

转换方法：虽然中缀表达式、前缀表达式、后缀表达式表现方式不一样，但是运算符的运算顺序却是是统一的。因此按照表达式的统一的运算顺序，依次将旧表达式的字表达式转化为新表达式的子表达式，最终得到整个新表达式。

中缀表达式转后缀表达式
  • 思路：
1
2
3
4
5
6
7
8
9
1. 设置栈内、栈外操作符优先级，栈内1356栈外6241；操作符栈和操作数栈；
2. 遍历中缀表达式
    1. 如果是数字，入数字栈
    2. 如果是操作符
        1. 如果操作符栈非空，且操作符优先级低于操作符栈顶，则操作符出栈、操作数栈入栈；
        2. 如果操作符栈栈非空，且操作符优先级等于操作符栈顶，则操作符出栈；
        3. 否则，操作符入操作符栈；
3. 如果操作符栈非空，则不断出栈移入操作数栈；
4. 顺序返回操作数栈中的元素；
  • 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
mid = 'A+B*(C-D)-E/F'
def mid_pos(str):
    dic_in = {'(':1,'+':3,'-':3,'*':5,'/':5,')':6}
    dic_out = {'(':6,'+':2,'-':2,'*':4,'/':4,')':1}
    ope = []
    res = []
    
    for c in mid:
        if c.isalpha():
            res.append(c)
        else:
            while ope and dic_out[c] < dic_in[ope[-1]]:
                res.append(ope.pop())
            if ope and dic_out[c] == dic_in[ope[-1]]:
                ope.pop()
            else:
                ope.append(c)
                
    while ope:
        res.append(ope.pop())
    return ''.join(res)

mid_pos(mid)
'ABCD-*+EF/-'
中缀表达式转前缀表达式

  • 思路：与中缀转后缀类似，只需做三个切换即可：反向遍历、反向输出、栈内站外优先级互换；

  • 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
mid = 'A+B*(C-D)-E/F'
def mid_pos(str):
    # 1. 栈内栈外优先级互换
    dic_out = {'(':1,'*':5,'/':5,'+':3,'-':3,')':6}
    dic_in = {'(':6,'*':4,'/':4,'+':2,'-':2,')':1}
    ope = []
    res = []
    
    # 2.反向遍历
    for c in mid[::-1]:
        if c.isalpha():
            res.append(c)
        else:
            while ope and dic_out[c] < dic_in[ope[-1]]:
                res.append(ope.pop())
            if ope and dic_out[c] == dic_in[ope[-1]]:
                ope.pop()
            else:
                ope.append(c)
    while ope:
        res.append(ope.pop())
        
    # 3. 反向输出
    return ''.join(res[::-1])
    
mid_pos(mid)
'-+A*B-CD/EF'

计算表达式

计算中缀表达式

虽然中缀表达式是人们所习惯的表达方式，但是对于计算机来说它却很复杂，而后缀和前缀表达式则很容易求值。在计算中缀表达式的值时，通常需要先将中缀表达式转化为后缀或前缀表达式，然后再求值。

  • 问题：将中缀表达式”A+B*(C-D)-E/F”转化为后缀表达式，并求值。其中每个字母表示一个正整数。
  • 思路：
1
2
3
4
5
6
7
8
9
1. 设定栈内(1356)栈外优先级，操作符函数，操作符栈和操作数栈；
2. 遍历中缀表达式：
    1. 如果是数字，收集多位数数值，并入数字栈；
    2. 如果是操作符
        1. 如果栈非空，且栈外操作符优先级小于栈顶优先级，则不断出栈操作符，并从操作数栈出栈两个元素，计算出结果后再次入操作数栈；
        2. 如果栈非空，且栈外优先级等于栈顶优先级，则出栈；
        3. 否则，操作数直接入操作符栈；
3. 如果操作符栈不为空，则操作符出栈、操作数出栈两个操作数，计算结果后再入栈操作数
4. 最后返回操作数栈中的数值；
  • 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
def mid_pos(mid):
    dic_in = {'(':1,'+':3,'-':3,'*':5,'/':5,')':6}
    dic_out = {'(':6,'+':2,'-':2,'*':4,'/':4,')':1}
    dic_fun = {'+':lambda x,y:x+y,'-':lambda x,y:x-y,'*':lambda x,y:x*y,'/':lambda x,y:x/y,}
    ope = []
    res = []
    
    n = len(mid)
    num = 0
    for i,c in enumerate(mid):
        if c.isdigit():
            num = num * 10 +int(c)
            if i == n - 1 or not mid[i+1].isdigit():
                res.append(num)
                num = 0
        else:
            while ope and dic_out[c] < dic_in[ope[-1]]:
                y = res.pop()
                res[-1] = dic_fun[ope.pop()](res[-1],y)
            if ope and dic_out[c] == dic_in[ope[-1]]:
                ope.pop()
            else:
                ope.append(c)
    while ope:
        y = res.pop()
        res[-1] = dic_fun[ope.pop()](res[-1],y)
    return res[-1]

N = input()
for _ in xrange(N):
    line = raw_input().strip()
    if line:
        # 防止首字符为负号
        if line[0] == '-':
            line = '0' + line
        print mid_pos(line)
    else:
        print 0
计算后缀表达式
  • 思路：
1
2
3
4
5
1. 初始化中间结果栈res
2. 从左向右扫描表达式
3. 遇到多位数字时，先计算数字真实值，num = num *10 + int(c),如果当前字符是数字且是最后一个字符或当前为运算符，则将刚刚保存的数值压入res
4. 遇到操作符时，出栈两个元素运算后将结果压入栈
5. 扫描结束，栈中的唯一元素就是表达式的结果
  • 算法：略，很容易实现，但后缀前缀表达式不好区分多位数，在后面计算中缀表达式时也会涉及这个过程。
计算前缀表达式
  • 思路：只需改变扫描方向，还有多位数字的处理
1
2
3
4
5
1. 初始化中间结果栈res
2. 从右向左扫描表达式
3. 遇到多位数字时，先计算数字真实值，num = num + int(c) * 10,如果当前字符是数字且是最后一个字符或当前为运算符，则将刚刚保存的数值压入res
4. 遇到操作符时，出栈两个元素运算后将结果压入栈
5. 扫描结束，栈中的唯一元素就是表达式的结

卡特兰数

卡特兰数(Dyck word)：满足以下条件的序列的个数称为n阶卡特兰数：

  1. 序列由n个X和n个Y组成；
  2. 所有的前缀序列中X的个数大于等于Y的个数；
1
XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY

卡特兰通项：

证明：镜像法。令1表示进栈，0表示出栈，则可转化为求一个2n位、含n个1、n个0的二进制数，满足从左往右扫描到任意一位时，经过的0数不多于1数。显然含n个1、n个0的2n位二进制数共有 $\binom{2n}{n}$个。下面考虑不满足要求的数目，考虑一个含n个1、n个0的2n位二进制数，扫描到第2m+1位上时有m+1个0和m个1（容易证明一定存在这样的情况），则后面的0-1排列中必有n-m个1和n-m-1个0。将2m+2及其以后的部分0变成1、1变成0，则对应一个n+1个0和n-1个1的二进制数$\binom{2n}{n+1}$。

卡特兰数可用于分析“同等数量的两种状态交替出现”的问题。

合法的进出栈序列个数

n个不同元素的出栈序列个数=卡特兰数：如果将入栈作为X，出栈作为Y，则每个进出栈过程可表示为01序列，且出入栈次数相等，任何前缀中进栈次数大于等于出栈次数。每个合法的进出序列都唯一对应于一种出栈序列。

1
进出进进出进出出

合法的括号表达式个数

n对括号组成的合法序列数=卡特兰数：左括号作为X，右括号作为Y，合法括号等价于括号序列的所有前缀中左括号个数大于等于右括号个数，且左右总括号数相等。

1
()((()()))

合法的二叉树形态个数

n个节点组成的二叉树的形态数=卡特兰数：节点作为X，空节点作为Y，空节点数比节点树多一，且二叉树的先序遍历序列尾节点一定是空节点，去掉最后一个空节点，那么每一个先序遍历序列都满足卡特兰定理。

推广： n个内部节点组成的满二叉树个数=卡特兰数：将内部节点作为X，叶节点作为Y

合法的不超过对角线的网格路径个数

n×n 网格不越过对角线的路径数=卡特兰数：X代表“向右”，Y代表“向上”。

[LeetCode 331] 验证二叉树的先序序列化
  • 问题：序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #。例如，上面的二叉树可以被序列化为字符串 “9,3,4,#,#,1,#,#,2,#,6,#,#”，其中 # 代表一个空节点。给定一串以逗号分隔的序列，验证它是否是正确的二叉树的前序序列化。
1
2
3
4
5
6
7
     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #
  • 思路：任意前缀中虚拟叶子节点(#)数不超过内部节点数，且最终虚拟叶子节点(#)数等于内部节点数，等价于该序列是合法先序序列
  • 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    """
    思路：
        1. 末尾节点为虚节点，去掉末尾节点后
        2. 任何前缀中节点数大于等于虚节点数
        3. 前缀节点总个数=虚节点总个数
    """
    def isValidSerialization(self, preorder):
        """
        :type preorder: str
        :rtype: bool
        """
        if preorder[-1] != '#':
            return False
        
        preorder = preorder.split(',')[:-1]
        count = 0
        for i in xrange(len(preorder)):
            count += [1,-1][preorder[i] == '#']
            if count < 0:
                return False
        return count == 0

递归转非递归

  1. 递归调用：相当于入栈，函数参数相当于入栈元素；
  2. 递归返回：相当于出栈后做处理的结果；
  3. 递归深度：栈的深度；

树的先中后序非递归遍历是最好的实例，详见树的遍历。

递增递减栈

“递增/递减栈”用于查找线性表中每个元素左右两侧第一个更小/更大(小于等于/大于等于)的元素。有以下几种变形：

  1. 前向递增栈：寻找每个元素右侧第一个小于/小于等于它的元素；
  2. 后向递增栈：寻找每个元素左侧第一个小于/小于等于它的元素；
  3. 前向递减栈：寻找每个元素右侧第一个大于/大于等于它的元素；
  4. 后向递减栈：寻找每个元素左侧第一个大于/大于等于它的元素；

以前向递增栈为例，维护递增栈的一般过程：

  1. 如果栈非空且入栈元素小于栈顶元素，则不断出栈直至条件不满足；出栈时，待入栈元素是栈顶元素右侧第一个小于它的元素；
  2. 将入栈元素下标入栈；入栈时，栈顶元素是待入栈元素左侧第一个小于等于它的元素；

说明：递增递减栈的灵活性很强，递增栈找邻近更小，递减栈找邻近更大；前向后向，等号视情况而定。

[LeetCode 496] 下一个更大元素
  • 问题：给定两个没有重复元素的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出-1。
  • 思路：递减栈，寻找a两边最近的比它大的值，可以通过递减栈，入栈元素比栈顶小则入栈，否则一直出栈，直至比栈顶小，每次出栈元素右侧第一个最大就是当前入栈元素，O(n+m)
  • 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def nextGreaterElement(self, findNums, nums):
    """
    :type findNums: List[int]
    :type nums: List[int]
    :rtype: List[int]
    """
    stack = []
    d = {}
    for i,num in enumerate(nums):
        while stack and num > nums[stack[-1]]:
            d[nums[stack[-1]]] = num
            stack.pop()
        stack.append(i)    
    
    print d,stack
    res = []
    for num in findNums:
        if num in d:
            res.append(d[num])
        else:
            res.append(-1)
    return res
[LeetCode 456] 132模式
  • 问题：给定一个整数序列：a1, a2, …, an，一个132模式的子序列 ai, aj, ak 被定义为：当 i < j < k 时，ai < ak < aj。设计一个算法，当给定有 n 个数字的序列时，验证这个序列中是否含有132模式的子序列。注意：n 的值小于15000。
  • 思路：后向递减栈；从后向前遍历数组，如果入栈元素比上一个出栈元素小则返回True，如果入栈元素比栈顶大则出栈直至栈空或不大于栈顶，入栈；否则最后返回False。
  • 代码：
1
2
3
4
5
6
7
8
9
10
11
def find132pattern(self, nums):
    n = len(nums)
    s = []
    pre = float('-inf')
    for num in nums[::-1]:
        if num < pre:
            return True
        while s and num > s[-1]:
            pre = s.pop()
        s.append(num)
    return False
[LeetCode 402] 移掉K位数字
  • 问题：给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。注意:num 的长度小于 10002 且 ≥ k。num 不会包含任何前导零。

  • 思路：

    1
    2
    3
    4
    5
    思路：前向递增栈+拼接；
            1. 如果待入栈元素比栈顶元素小，则出栈，去掉出栈元素，直至大于等于栈顶或栈为空
            2. 入栈
            出栈个数等于k则结束，去掉出栈元素后的字符串，去掉前导0
            出栈个数不足k则将末尾的差额元素去掉，去掉前导零

  • 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def removeKdigits(self, num, k):
    n = len(num)
    s = []
    ns = set()
    for i,x in enumerate(num):
        while s and x < num[s[-1]] and k:
            ns.add(s.pop())
            k -= 1
        s.append(i)
        if k == 0:
            break
    
    tmp = [num[i] for i in xrange(n) if i not in ns and i < n - k]
    res = ''.join(tmp).lstrip('0')
    
    return res or '0'
[LeetCode 42] 接雨水
  • 问题：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
  • 思路：维护递减栈，如果入栈元素小于栈顶则入栈，如果入栈元素大于栈顶则出栈，如果相等则pass，此时次栈顶元素a<栈顶元素b<入栈元素c，且a,c是b两侧最近的较大元素，abc可以理解为以b为底，ab为两边所能装下的水，将元素全部装入栈的过程统计水和。
  • 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def trap(self, height):
    """
    :type height: List[int]
    :rtype: int
    """
    res = 0
    s = []
    for i,w in enumerate(height):
        while s and w >= height[s[-1]]:
            top = s.pop()
            if s:
                res += (min(w,height[s[-1]]) - height[top]) * (i - s[-1] - 1)
        if not s or w < height[s[-1]]:
            s.append(i)
    return res

栈实现队列

  • 问题：使用栈实现队列的下列操作：
    • push(x) — 将一个元素放入队列的尾部。
    • pop() — 从队列首部移除元素。
    • peek() — 返回队列首部的元素。
    • empty() — 返回队列是否为空。
  • 思路：
1
2
3
4
5
使用两个栈instack, outstack来模拟队列，push入instack，pop出outstack，只有在outstack中没有元素时才会向instack借
    1. 初始化，两个空栈
    2. push，入A
    3. pop从B出，B无则将A中所有元素放入B中
    3. peek，返回队首元素，返回B中栈顶，如果没有则将A中所有元素放入B中，A也没有的话返回空
  • 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class MyQueue(object):
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.instack = []
        self.outstack = []
        

    def push(self, x):
        """
        Push element x to the back of queue.
        :type x: int
        :rtype: void
        """
        self.instack.append(x)
        

    def pop(self):
        """
        Removes the element from in front of queue and returns that element.
        :rtype: int
        """
        if not self.outstack:
            while self.instack:
                self.outstack.append(self.instack.pop())
        return self.outstack.pop()

    def peek(self):
        """
        Get the front element.
        :rtype: int
        """
        if not self.outstack:
            while self.instack:
                self.outstack.append(self.instack.pop())
        return self.outstack[-1]

    def empty(self):
        """
        Returns whether the queue is empty.
        :rtype: bool
        """
        return not (self.instack or self.outstack)
坚持原创技术分享，您的支持将鼓励我继续创作！