外贸soho先做网站,大连网站建设费用,wordpress 自适应,网站建设成都公司文章目录栈的概念栈的特点栈的操作Python 实现栈栈的简单应用#xff1a;括号匹配问题栈的简单应用#xff1a;倒序输出一组元素栈的概念
栈#xff08;stack#xff09;又名堆栈#xff0c;栈是一种线性数据结构#xff0c;用先进后出或者是后进先出的方式存储数据括号匹配问题栈的简单应用倒序输出一组元素栈的概念
栈stack又名堆栈栈是一种线性数据结构用先进后出或者是后进先出的方式存储数据栈中数据的插入删除操作都是在栈的顶端进行这一端被称为栈顶相对地把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈它是把新元素放到栈顶元素的上面使之成为新的栈顶元素从一个栈删除元素又称作出栈或退栈它是把栈顶元素删除掉使其相邻的元素成为新的栈顶元素。 栈的特点
元素后进先出Last in First OutLIFO 栈的操作
push(item)进栈向栈顶添加元素pop()出栈删除栈顶元素top()查看栈顶元素empty()判断栈是否为空 Python 实现栈
栈并不是 Python 的内建类型在必要的时候可以使用列表来模拟基于数组的栈。如果将列表的末尾看作是栈的顶列表方法 append() 就是将元素压入到栈中进栈而列表方法 pop() 会删除并返回栈顶的元素出栈列表索引的方式 arr[-1] 可以查看栈顶元素。具体代码实现如下
class Stack:def __init__(self):self.stack []def push(self, item):self.stack.append(item)def pop(self):if self.empty():return Noneelse:return self.stack.pop()def top(self):if self.empty():return Noneelse:return self.stack[-1]def empty(self):return len(self.stack) 0栈的简单应用括号匹配问题
问题描述
给定一个字符串字符串中只包含小括号 ()、中括号 []、大括号 {}求该字符串中的括号是否匹配。匹配规则成对出现或者左右对称出现例如
()[]{}匹配{[()]}匹配({}]不匹配()]不匹配({)}不匹配
通过栈来解决
有字符串 ()[{}]依次取每个括号只要是左括号就进栈只要是右括号就判断栈顶是否为对应的左括号具体步骤如下
① 遇到左小括号 (执行进栈操作② 遇到右小括号 )判断此时栈顶是否为左小括号 (是则让左小括号 ( 出栈此时栈为空;③ 遇到左中括号 [执行进栈操作④ 遇到左大括号 {执行进栈操作⑤ 遇到右大括号 }判断此时栈顶是否为左大括号 {是则让左大括号 { 出栈此时栈为空⑥ 遇到右中括号 ]判断此时栈顶是否为左中括号 [是则让左中括号 [ 出栈此时栈为空⑦ 判断最终的栈是否为空是则表示匹配不是则表示不匹配。其中第 ② ⑤ ⑥ 步中若判断为不是则直接表示不匹配。
Python 代码实现
class Stack:def __init__(self):self.stack []def push(self, item):self.stack.append(item)def pop(self):if self.empty():return Noneelse:return self.stack.pop()def top(self):if self.empty():return Noneelse:return self.stack[-1]def empty(self):return len(self.stack) 0def brackets_match(s):match_dict {}: {, ]: [, ): (}stack Stack()for ch in s:if ch in [(, [, {]: # 如果为左括号则执行进栈操作stack.push(ch)else: # 如果为右括号if stack.empty(): # 如果栈为空则不匹配即多了一个右括号没有左括号匹配return Falseelif stack.top() match_dict[ch]: # 如果栈顶的元素为对应的左括号则让栈顶出栈stack.pop()else: # 如果栈顶元素不是对应的左括号则不匹配return Falseif stack.empty(): # 最后的栈如果为空则匹配否则不匹配return Trueelse:return Falseprint(brackets_match([{()}(){()}[]({}){}]))
print(brackets_match(()[{}]))
print(brackets_match(({)}))
print(brackets_match([]}))输出结果
True
True
False
False栈的简单应用倒序输出一组元素
把元素存入栈再顺序取出
class Stack:def __init__(self):self.stack []def push(self, item):self.stack.append(item)def pop(self):if self.empty():return Noneelse:return self.stack.pop()def top(self):if self.empty():return Noneelse:return self.stack[-1]def empty(self):return len(self.stack) 0def reverse_list(s):stack Stack()for ch in s:stack.push(ch)new_list []while not stack.empty():new_list.append(stack.pop())return new_listprint(reverse_list([A, B, C, D, E]))输出结果
[E, D, C, B, A]
