算法基础之栈的理论和应用

2024-07-13 01:13| 来源: 网络整理| 查看: 265

算法基础之栈的理论和应用 1.栈的基础定义2.栈的实现3.栈的应用3.1有效的括号（20）3.2四则运算表达式求值3.3设计一个有getMin功能的栈（代码面试题）

1.栈的基础定义

官方定义：栈是限定仅在表尾进行插入和删除操作的线性表。解释：栈也是一种线性结构，相比数组，栈对应的操作是数组的子集，只能从一端添加元素，也只能一端取出元素。把允许删除和删除的一端称为栈顶（top），另一端称为栈底（bottom）在这里插入图片描述栈是一种**后进先出（Last in First out, LIFO）**的数据结构。思考：最先进栈的元素，是不是就只能是最后出栈呢？当然不是啦！

2.栈的实现

因为栈的操作基本是数组操作的子集，我们只需要把栈初始化为一个空数组，再实现它的各个操作即可。基本需求：在这里插入图片描述

class Stack(object): """栈""" def __init__(self): self.items = [] def is_empty(self): """判断是否为空""" return self.items == [] def push(self, item): """加入元素""" self.items.append(item) def pop(self): """弹出元素""" return self.items.pop() def peek(self): """返回栈顶元素""" return self.items[len(self.items)-1] def size(self): """返回栈的大小""" return len(self.items)

用下面代码检验一下吧

if __name__ == "__main__": stack = Stack() stack.push("HELLO") stack.push("MY") stack.push("FRIEND") print(stack.items) print(stack.size()) print(stack.peek()) print(stack.pop()) print(stack.items) print(stack.pop()) print(stack.pop()) print(stack.items) ['HELLO', 'MY', 'FRIEND'] 3 FRIEND FRIEND ['HELLO', 'MY'] MY HELLO []

应该是OK了。

3.栈的应用

一般撤销操作应用到的就是栈的原理，接下来我们结合一些Leetcode题来领悟一下。

3.1有效的括号（20）

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.Open brackets must be closed in the correct order. 在这里插入图片描述

这题让我们知道编译器是怎么知道括号是否匹配的呢，其实用的就是栈的原理。注意的是，翻译版题目里的‘闭合’其实就是匹配对的意思。先直观理解一下，不论大中小括号，只要是左括号就把它压入栈；如果是右括号，就看栈顶的是否是匹配的左括号，匹配则出栈。最终是空栈了，说明是合法的括号匹配。在这里插入图片描述

再来看个不合法的例子：

在这里插入图片描述所以，栈顶元素反映了在嵌套的层次关系中，最近的需要匹配的元素。概括一下这题的思路：从前向后扫描字符串：遇到左括号X，就压栈x。遇到右括号y：如果发现栈顶元素x和该括号y匹配，则栈顶元素出栈，继续判断下一个字符；如果栈顶元素x和该括号不匹配，字符串不匹配，如果栈为空，字符串不匹配。扫描完成后，如果栈恰好为空，则字符串匹配，否则，字符串不匹配。

#有效的括号 class Solution: def isValid(self, s): """ :type s: str :rtype: bool """ stack = [] for ch in s: if ch in ['(','[','{']: stack.append(ch) else: if stack: left = stack.pop()#栈顶元素出栈 else: return False if left=='[' and ch ==']' or left=='(' and ch==')' or left=='{' and ch=='}': continue else: return False if stack == []: return True else: return False 3.2四则运算表达式求值

一般四则运算除了加减乘除，还有括号，我们一般称作中缀表达式比如下面例子： 9 + （3 - 1） * 3 + 10 / 2 然而机器更容易理解的是后缀表示法，即所有的符号要在运算数字的后面出现： 9 3 1 - 3 * + 10 2 / + 下面我们来看一下计算器怎么理解的，一开始从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到是符号把栈顶的两个数字拿出来进行运算，运算结果再进栈。在这里插入图片描述因此，我们根据此原理写出它的实现：

#四则运算表达式 class Solution: def evalRPN(self, tokens): """ :type tokens: List[str] :rtype: int """ stack = [] for s in tokens: if s in ['+','-','*','/']: b = stack.pop() a = stack.pop() if s == '+': stack.append(a+b) elif s == '-': stack.append(a-b) elif s == '*': stack.append(a*b) else: stack.append(int(a/b)) else: stack.append(int(s)) ans = int(stack.pop()) return ans

这时，我们会好奇那这个后缀表达式是怎么推导出来的呢？再用原来的例子解释一下，中缀表达式：9 + （3 - 1） * 3 + 10 / 2 后缀表达式：9 3 1 - 3 * + 10 2 / + 中缀转换成后缀的规则是：从左到右遍历中缀表达式每个数字和符号，若是数字就输出，即成为后缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或优先级低于栈顶符号（乘除优先加减）则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。在这里插入图片描述

3.3设计一个有getMin功能的栈（代码面试题）

在这里插入图片描述我们设计出俩个栈，一个是普通栈（stackData）里面放数据，另一个栈（stackMin）里面放栈中最小值。第一种方法：在压栈时判断插入时为空栈或者元素小于等于当前栈顶元素,压入最小值栈中。如果弹栈元素大于等于（不可能小于）最小值栈顶元素，同时从最小值栈中弹出。最终，stackMin里从底到顶的元素大小是从大到小排的，因此最小值就是栈顶元素。在这里插入图片描述

#设计一个有getMin功能的栈-方法1 class NewStack1: def __init__(self): self.stackData = [] self.stackMin = [] def push(self, newNum): self.stackData.append(newNum) if len(self.stackMin) == 0 or newNum

【本文地址】

算法基础之栈的理论和应用

算法基础之栈的理论和应用

今日新闻

推荐新闻