双向链表、循环链表、栈
双向循环链表
class Node:
#显性定义出构造函数
def __init__(self,data):
self.data = data #普通节点的数据域
self.next = None #保存下一个节点的链接域
self.prior = None #保存前一个节点饿链接域
class DoubleLinkLoop:
def __init__(self, node = Node):
self.head = node
self.size = 0
# 判空
def is_empty(self):
return self.size == 0
# 尾插
def add_tail(self,data):
node = Node(data)
# 判空
if self.is_empty():
self.head = node
node.next = node
node.prior = node
else:
q = self.head
while q.next != self.head:
q = q.next
q.next = node
node.prioe = q
node.next = self.head
self.head.prior = node
self.size += 1
# 遍历
def show(self):
if self.is_empty():
print("链表为空,无法遍历")
return
q = self.head
while True:
print(q.data, end=" ")
q = q.next
if q == self.head: # 遇到头节点结束循环
break
print()
# 尾删
def del_tial(self):
if self.is_empty():
print("删除失败")
return
else:
if self.size == 1:
self.head = None
else:
q = self.head
i = 1
while i < self.size - 1:
q = q.next
i += 1
q.next = self.head
self.head.prior = q
self.size -= 1
# 测试
if __name__ == "__main__":
doubleLinkLoop = DoubleLinkLoop()
# 尾插
doubleLinkLoop.add_tail(10)
doubleLinkLoop.add_tail(20)
doubleLinkLoop.add_tail(30)
doubleLinkLoop.add_tail(40)
# 遍历
doubleLinkLoop.show()
# 尾删
doubleLinkLoop.del_tial()
doubleLinkLoop.show()
链式栈
class Node:
"""定义链式栈的节点"""
def __init__(self, data=None):
self.data = data # 节点存储的数据
self.next = None # 指向下一个节点
class LinkedStack:
"""链式栈的实现"""
def __init__(self):
self.top = None # 栈顶指针
self.size = 0 # 栈的大小
def is_empty(self):
"""判断栈是否为空"""
return self.top is None
def push(self, data):
"""添加数据到栈顶"""
new_node = Node(data)
new_node.next = self.top # 新节点指向当前栈顶
self.top = new_node # 更新栈顶为新节点
self.size += 1
def pop(self):
"""弹出栈顶元素"""
if self.is_empty():
raise IndexError("pop from an empty stack")
popped_data = self.top.data
self.top = self.top.next # 栈顶指针下移
self.size -= 1
return popped_data
def peek(self):
"""返回栈顶元素"""
if self.is_empty():
raise IndexError("peek from an empty stack")
return self.top.data
def traverse(self):
"""遍历栈中的所有元素"""
elements = []
current = self.top
while current:
elements.append(current.data)
current = current.next
return elements
def get_size(self):
"""返回栈的大小"""
return self.size
测试
stack = LinkedStack()
# 添加数据
stack.push(10)
stack.push(20)
stack.push(30)
print("栈中的元素:", stack.traverse()) # 输出: [30, 20, 10]
print("栈顶元素:", stack.peek()) # 输出: 30
print("栈的大小:", stack.get_size()) # 输出: 3
# 弹出栈顶元素
print("弹出栈顶:", stack.pop()) # 输出: 30
print("栈中的元素:", stack.traverse()) # 输出: [20, 10]
# 判空
print("栈是否为空:", stack.is_empty()) # 输出: False
# 清空栈后判空
stack.pop()
stack.pop()
print("栈是否为空:", stack.is_empty()) # 输出: True
思维导图
原文地址:https://blog.csdn.net/qq_65009672/article/details/144040832
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!