共计 2642 个字符，预计需要花费 7 分钟才能阅读完成。
之前讲了一个链表，明天咱们来说说这个栈（stack）的工作原理及使用。
1. 什么叫做栈
栈是一种非凡的序列，栈内的元素只能通过序列的一端拜访，这一端称为栈顶。栈被称为一种 LIFO（last-in-first-out，后入先出）的数据结构。
因为栈具备后入先出的特点，所以任何不在栈顶的元素都无法访问。为了失去栈底的元素，必须先拿掉下面的元素。
对栈的两种次要操作是将一个元素压入栈和将一个元素弹出栈。入栈应用 push() 办法，出栈应用 pop() 办法。
另一个罕用的操作是预览栈顶的元素。pop() 办法尽管能够拜访栈顶的元素，然而调用该办法后，栈顶元素也从栈中被永久性地删除了。peek() 办法则只返回栈顶元素，而不删除它。
为了记录栈顶元素的地位，同时也为了标记哪里能够退出新元素，咱们应用变量 top，当向栈内压入元素时，该变量增大；从栈内弹出元素时，该变量减小。
push()、pop() 和 peek() 是栈的 3 个次要办法，然而栈还有其余办法和属性。
Stack() 建设一个空的栈对象
push() 把一个元素增加到栈的最顶层
pop() 删除栈最顶层的元素，并返回这个元素
peek() 返回最顶层的元素，并不删除它
isEmpty() 判断栈是否为空
size() 返回栈中元素的个数 那么接下来咱们来创立一个栈
class Node():
"""节点"""
def __init__(self, item=None, next=None):
self.item = item
self.next = next
class Stack():
"""栈"""
def __init__(self, node=None):
self.head = node
def push(self, item):
"""栈顶插入元素"""
self.head = None(item, self.head)
def pop(self):
"""弹出栈顶元素"""
if self.head:
self.head=self.head.next
return
return "栈为空栈"
def peek(self):
"""返回栈顶元素"""
if self.head:
return self.head.item
return "栈为空栈"
def is_empty(self):
"""判断是否为空栈"""
return self.head==None
def size(self):
"""返回元素个数"""
num = 0
node = self.head
if node==None:
return num
num += 1
while node.next!=None:
node = node.next
num += 1
return num- 栈的利用
那么当初大家应该对于栈是个什么货色大略曾经理解了，然而这个栈它在咱们的 python 中哪里回去用到它呢？这里就给大家举几个例子。
2.1 括号匹配
需要：
如果表达式中容许蕴含三中括号 ()、[]、{}，其嵌套程序是任意的，编写一个函数，判断一个表达式字符串，括号匹配是否正确。
思路：
创立一个空栈，用来存储尚未找到的左括号；
遍历字符串，遇到左括号则压栈，遇到右括号则出栈一个左括号进行匹配；
在第二步骤过程中，如果空栈状况下遇到右括号，阐明短少左括号，不匹配；
在第二步骤遍历完结时，栈不为空，阐明短少右括号，不匹配；
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，否则返回 False
result = match(LEFT)
result1 = match(RIGHT)
print(result)
print(result1)2.2 十进制转化为二进制
def decimal_to_bin(dec):
stack = Stack()
bin_str = ''
if dec == 0:
stack.push(0)
while dec > 0:
a = dec % 2
stack.push(a)
dec = int(dec / 2)
while not stack.is_Empty():
bin_str += str(stack.pop())
return bin_str那么这个就是栈，你学废了吗？
