Python算法应用实战之栈

栈是什么，你可以理解为一种先入后出的数据结构（First In Last Out），一种操作受限的线性表。下面这篇文章主要给大家介绍了Python中栈的应用实战，文中给出了多个实例，需要的朋友可以参考借鉴，下面来一起看看吧。

栈(stack)

栈又称之为堆栈是一个特殊的有序表，其插入和删除操作都在栈顶进行操作，并且按照先进后出，后进先出的规则进行运作。

如下图所示

例如枪的弹匣，第一颗放进弹匣的子弹反而在发射出去的时候是最后一个，而最后放入弹匣的一颗子弹在打出去的时候是第一颗发射出去的。

栈的接口

如果你创建了一个栈，那么那么应该具有以下接口来进行对栈的操作

知道栈需要上述的接口后，那么在Python中，列表就类似是一个栈，提供接口如下：

Python中的栈接口使用实例：

# 创建一个栈In [1]: s = []# 往栈内添加一个元素In [2]: s.append(1)In [3]: sOut[3]: [1]# 删除栈内的一个元素In [4]: s.pop()Out[4]: 1In [5]: sOut[5]: []# 判断栈是否为空In [6]: not s<i style="color:transparent">本文来源gaodai$ma#com搞$代*码*网(</i>Out[6]: TrueIn [7]: s.append(1)In [8]: not sOut[8]: False# 获取栈内元素的数量In [9]: len(s)Out[9]: 1In [10]: s.append(2)In [11]: s.append(3)# 取栈顶的元素In [12]: s[-1]Out[12]: 3

一大波实例

在了解栈的基本概念之后，让我们再来看几个实例，以便于理解栈。

括号匹配

题目

假如表达式中允许包含三中括号()、[]、{}，其嵌套顺序是任意的，例如：

正确的格式

{()[()]},[{({})}]

错误的格式

[(]),[()),(()}

编写一个函数，判断一个表达式字符串，括号匹配是否正确

思路

1. 创建一个空栈，用来存储尚未找到的左括号；

2. 便利字符串，遇到左括号则压栈，遇到右括号则出栈一个左括号进行匹配；

3. 在第二步骤过程中，如果空栈情况下遇到右括号，说明缺少左括号，不匹配；

4. 在第二步骤遍历结束时，栈不为空，说明缺少右括号，不匹配；

解决代码

建议在pycharm中打断点，以便于更好的理解

#!/use/bin/env python# _*_ coding:utf-8 _*_LEFT = {'(', '[', '{'} # 左括号RIGHT = {')', ']', '}'} # 右括号def match(expr): """ :param expr: 传过来的字符串 :return: 返回是否是正确的 """ stack = [] # 创建一个栈 for brackets in expr: # 迭代传过来的所有字符串 if brackets in LEFT: # 如果当前字符在左括号内  stack.append(brackets) # 把当前左括号入栈 elif brackets in RIGHT: # 如果是右括号  if not stack or not 1 <= ord(brackets) - ord(stack[-1]) <= 2:  # 如果当前栈为空，()]  # 如果右括号减去左括号的值不是小于等于2大于等于1  return False # 返回False  stack.pop() # 删除左括号 return not stack # 如果栈内没有值则返回True，否则返回Falseresult = match('[(){()}]')print(result)

喜欢 (0)赏

[搞代码]

分享 (0)