双向循环链表
class Node:#显性定义出构造函数def __init__(self,data):self.data = data #普通节点的数据域self.next = None #保存下一个节点的链接域self.prior = None #保存前一个节点饿链接域
class DoubleLinkLoop:def __init__(self, node = Node):self.head = nodeself.size = 0# 判空def is_empty(self):return self.size == 0# 尾插def add_tail(self,data):node = Node(data)# 判空if self.is_empty():self.head = nodenode.next = nodenode.prior = nodeelse:q = self.headwhile q.next != self.head:q = q.nextq.next = nodenode.prioe = qnode.next = self.headself.head.prior = nodeself.size += 1# 遍历def show(self):if self.is_empty():print("链表为空，无法遍历")returnq = self.headwhile True:print(q.data, end=" ")q = q.nextif q == self.head: # 遇到头节点结束循环breakprint()# 尾删def del_tial(self):if self.is_empty():print("删除失败")returnelse:if self.size == 1:self.head = Noneelse:q = self.headi = 1while i < self.size - 1:q = q.nexti += 1q.next = self.headself.head.prior = qself.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 Nonedef push(self, data):"""添加数据到栈顶"""new_node = Node(data)new_node.next = self.top # 新节点指向当前栈顶self.top = new_node # 更新栈顶为新节点self.size += 1def pop(self):"""弹出栈顶元素"""if self.is_empty():raise IndexError("pop from an empty stack")popped_data = self.top.dataself.top = self.top.next # 栈顶指针下移self.size -= 1return popped_datadef peek(self):"""返回栈顶元素"""if self.is_empty():raise IndexError("peek from an empty stack")return self.top.datadef traverse(self):"""遍历栈中的所有元素"""elements = []current = self.topwhile current:elements.append(current.data)current = current.nextreturn elementsdef 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
思维导图
