python数据结构学习第一章——栈
在这片文章中,我们使用python3.8自制一个具有基本功能的栈结构,它的功能只有push,pop,peek这三个功能
` #!/usr/bin/env python
# * coding: utf-8 *
# @Time : 2024/9/15 19:26
# @Author : Huzhaojun
# @Version:V 1.0
# @File : test.py
# @desc :
# 数据结构复习第一章, 栈结构的实现与运用
class Node:
"""创建节点"""
def __init__(self, data=None):
self.data = data
self.next = None
class stack:
def __init__(self):
self._n = 0 # 记录元素个数
self.top = None # 这是一个永远指向栈顶的指针
self.next = None # 指向下一个元素
def push(self, data): # push 压入函数
node = Node(data) # 新建一个节点,并将其添加入栈中
if self.top: # 如果栈内有元素,就更新top指针的指向内容
node.next = self.top
self.top = node
else: # 否则直接指向新节点
self.top = node
self._n += 1
def pop(self): # pop 弹出函数
if self.top: # 判断栈顶是否存在元素,如果存在则执行下一步操作,否则直接返回None
data = self.top.data # 获取栈顶的值
self._n -= 1
if self.top.next: # 如果栈顶之下还存在其他元素,则替换指向指针的值
self.top = self.top.next
else: # 否则直接定义为None
self.top = None
return data
return None
def peek(self): # 查看栈顶值
if self.top:
return self.top.data
return None
`
使用过程:
x = stack()
x.push(1)
x.push(2)
print(x.peek())
print(x.pop())
print(x.peek())
输出结果:
2
2
1
实战一下
bracket-matching应用程序是一个常用的匹配括号的验证程序,验证包括(),{},【】符号是否平衡,及左右括号数量是否匹配,它还将确保一对括号确实包含在另一对括号中。
我们试着来验证一段xml文件,看看结果如何,注意,我在stack中新添了一个__len__函数:
`
#!/usr/bin/env python
# * coding: utf-8 *
# @Time : 2024/9/15 19:26
# @Author : Huzhaojun
# @Version:V 1.0
# @File : test.py
# @desc :
# 数据结构复习第一章, 栈结构的实现与运用
class Node:
"""创建节点"""
def __init__(self, data=None):
self.data = data
self.next = None
class stack:
def __init__(self):
self._n = 0 # 记录元素个数
self.top = None # 这是一个永远指向栈顶的指针
self.next = None # 指向下一个元素
def __len__(self): # 定义 len 事件
return self._n
def push(self, data): # push 压入函数
node = Node(data) # 新建一个节点,并将其添加入栈中
if self.top: # 如果栈内有元素,就更新top指针的指向内容
node.next = self.top
self.top = node
else: # 否则直接指向新节点
self.top = node
self._n += 1
def pop(self): # pop 弹出函数
if self.top: # 判断栈顶是否存在元素,如果存在则执行下一步操作,否则直接返回None
data = self.top.data # 获取栈顶的值
self._n -= 1
if self.top.next: # 如果栈顶之下还存在其他元素,则替换指向指针的值
self.top = self.top.next
else: # 否则直接定义为None
self.top = None
return data
return None
def peek(self): # 查看栈顶值
if self.top:
return self.top.data
return None
def check_brackets(statement):
Stack = stack()
for ch in statement:
if ch in "({[<":
Stack.push(ch)
if ch in ")}]>":
last = Stack.peek()
if last + ch in ("()", "[]", "{}", "<>"):
Stack.pop()
else:
return False
if len(Stack) > 0:
return False
return True
text = """
<?xml version="1.0" encoding="UTF-8"?>
<ui version="4.0">
<class>MainWindos</class>
<widget class="QDialog" name="MainWindos">
<property name="geometry">
<rect>
<x>0</x>
<y>0</y>
<width>402</width>
<height>575</height>
</rect>
</property>
<property name="windowTitle">
<string>music</string>
</property>
</widget>
<resources/>
<connections/>
</ui>"""
print(check_brackets(text))
`
运行结果:
True
自建的数据结构可以因需求而添加任意想要实现的方法,虽然内置的方法已经可以解决绝大部分问题了,但是在这过程中我们可以学习到更多。OVER