python中一些复合数据结构通过类的封装来实现的。双向循环链表与链栈也在其中。

双向循环链表

双向循环链表是一种特殊类型的链表，它结合了双向链表和循环链表的特点。在双向循环链表中，每个节点不仅包含数据，还持有指向前一个和后一个节点的指针，而且链表的最后一个节点指向第一个节点，形成一个闭环。

封装

就像上面介绍的一样，每一个结点（头结点除外）都有前驱，后继，以及数据域。由此创建结点类。

# 创建双向链表节点
# 双向链表结点有前驱有后继有数据域
class Node:def __init__(self,data):self.data = dataself.prior = Noneself.next = None

头结点

不是必须的，但为了方便对链表的操作，我们还是会创建。和其他链表的头结点一样，包含链表长度和head的成员变量。

#创建头结点便于操作链表
class Double:# 头结点记录链表地址，链表长度def __init__(self,node = None):self.head = nodeself.size = 0

判空

同样由于链式存储的优点，我们只需要判空。

    # 判空def is_empty(self):return self.size == 0

双向链表的插入与删除，根据表内元素个数不同，需要分开编写代码

尾插法

#尾插 根据链表是否为空有不同的插入方法def insert_rear(self,value):node = Node(value)# 当表为空时if self.is_empty():# 当只有一个元素时，循环链表前驱和后继指向自己self.head = nodenode.next =  nodenode.prior = nodeelse:# 变量指向最后一个结点，即head的前驱p = self.head.priornode.next = p.nextnode.prior = pp.next.prior = nodep.next = nodeself.size += 1

尾删法

# 尾删def del_rear(self):if self.is_empty():print("删除失败")elif self.size == 1:self.head = Noneelse:# 尾删直接将头结点的前驱指向前前结点，同时将现前结点的后继指向头结点q = self.head.prior.priorself.head.prior = qq.next = self.headself.size -= 1

遍历

双向循环列表可以使用前驱遍历和后继遍历两种方式

# 后继 def show(self):if self.size == 0:print("遍历失败")returnelse:p = self.headwhile p.next != self.head:print(f"{p.data}",end=" ")p = p.nextprint(f"{p.data}")#前驱def r_show(self):if self.size == 0:print("遍历失败")returnelse:p = self.headwhile p.prior != self.head:print(f"{p.data}", end=" ")p = p.priorprint(f"{p.data}")

全部代码

# 创建双向链表节点
# 双向链表结点有前驱有后继有数据域
class Node:def __init__(self,data):self.data = dataself.prior = Noneself.next = None#创建头结点便于操作链表
class Double:# 头结点记录链表地址，链表长度def __init__(self,node = None):self.head = nodeself.size = 0# 判空def is_empty(self):return self.size == 0#尾插 根据链表是否为空有不同的插入方法def insert_rear(self,value):node = Node(value)# 当表为空时if self.is_empty():# 当只有一个元素时，循环链表前驱和后继指向自己self.head = nodenode.next =  nodenode.prior = nodeelse:# 变量指向最后一个结点，即head的前驱p = self.head.priornode.next = p.nextnode.prior = pp.next.prior = nodep.next = nodeself.size += 1# 根据链表长度遍历输出def show(self):if self.size == 0:print("遍历失败")returnelse:i = 1p = self.headwhile p.next != self.head:print(f"{p.data}",end=" ")p = p.nexti+=1print(f"{p.data}")def r_show(self):if self.size == 0:print("遍历失败")returnelse:i = 1p = self.headwhile p.prior != self.head:print(f"{p.data}", end=" ")p = p.priori += 1print(f"{p.data}")# 尾删def del_rear(self):if self.is_empty():print("删除失败")elif self.size == 1:self.head = Noneelse:# 尾删直接将头结点的前驱指向前前结点，同时将现前结点的后继指向头结点q = self.head.prior.priorself.head.prior = qq.next = self.headself.size -= 1if __name__ =="__main__":d = Double()# 尾插法d.insert_rear(10)d.insert_rear(20)d.insert_rear(30)d.insert_rear(40)d.show()d.r_show()# 尾删法d.del_rear()d.show()d.del_rear()d.show()d.del_rear()d.show()d.del_rear()d.show()

10 20 30 40
10 40 30 20
10 20 30
10 20
10
遍历失败

链栈

链栈（Linked Stack）是一种基于链表实现的栈结构。在链栈中，每个元素都是一个节点，包含数据域和指向下一个节点的指针。链栈不需要像顺序栈那样预先分配固定大小的存储空间，它可以动态地分配和释放内存，因此更加灵活。

经过之前的练习，对于链式存储已经得心应手，简单完成栈的结点与头结点的封装

结点

和我们学习的线性表相同，链栈的结点也是由数据域与链接域组成。

# 创建链栈
# 创建链栈的结点，包含数据域data与链接域next
class Node:def __init__(self,data):self.data = dataself.next = None

 头结点

栈没有像线性表一样，计算长度的实例变量。有一个指向栈顶元素的top

# 封装链栈 一个永远指向栈顶的头结点，不限于统计链栈长度 ，记录栈顶位置
class LinkStack:def __init__(self,top = None):self.top = top

判空

    # 判空def is_empty(self):return self.top is None

入栈

类似之前线性表的头插法 ，新结点指向栈顶，top指向新的结点

   # 入栈 每个新元素充当栈顶def push(self,value):node = Node(value)
#         根据是否栈空这里有不同的插入方法if self.is_empty():self.top = nodeelse:node.next = self.topself.top = node

出栈

先入后出是栈的特性，最后入栈的元素后出来。出栈会返回该元素并删除。

     出栈 返回栈顶元素并删除def pop(self):
#         这里根据元素的多少有两种写法i = self.topif self.is_empty():print("栈空操作失败")return ielse:if self.top.next is None:self.top = Nonereturn i.dataelse:self.top = self.top.nextreturn i.data

返回栈顶元素

    def peek(self):#         这里根据元素的多少有两种写法i = self.topif self.is_empty():print("栈空操作失败")return ielse:self.top = self.top.nextreturn i

统计栈的大小

    def size(self):i = 0p = self.topwhile p:p = p.nexti+=1return i

遍历栈的元素

  def show(self):if self.is_empty():print("栈空操作失败")else:p =self.topwhile p:print(f"{p.data}",end=" ")p = p.nextprint()

全部代码

# 创建链栈
# 创建链栈的结点，包含数据域data与链接域next
class Node:def __init__(self,data):self.data = dataself.next = None# 封装链栈 一个永远指向栈顶的头结点，不限于统计链栈长度 ，记录栈顶位置
class LinkStack:def __init__(self,top = None):self.top = top# 判空def is_empty(self):return self.top is None# 入栈 每个新元素充当栈顶def push(self,value):node = Node(value)
#         根据是否栈空这里有不同的插入方法if self.is_empty():self.top = nodeelse:node.next = self.topself.top = node#     出栈 返回栈顶元素并删除def pop(self):
#         这里根据元素的多少有两种写法i = self.topif self.is_empty():print("栈空操作失败")return ielse:if self.top.next is None:self.top = Nonereturn i.dataelse:self.top = self.top.nextreturn i.datadef peek(self):#         这里根据元素的多少有两种写法i = self.topif self.is_empty():print("栈空操作失败")return ielse:self.top = self.top.nextreturn idef size(self):i = 0p = self.topwhile p:p = p.nexti+=1return idef show(self):if self.is_empty():print("栈空操作失败")else:p =self.topwhile p:print(f"{p.data}",end=" ")p = p.nextprint()if __name__ == "__main__":s = LinkStack()s.push(10)s.push(20)s.push(30)s.push(40)s.push(50)print(s.size())s.show()s.pop()s.show()s.peek()s.show()s.pop()s.show()s.pop()s.show()s.pop()s.show()s.pop()s.show()

D:\xn\hqyj\pythonProject\.venv\Scripts\python.exe C:\Users\31284\OneDrive\Desktop\PYTHON\数据结构\day03\03.py 
5
50 40 30 20 10 
40 30 20 10 
30 20 10 
20 10 
10 
栈空操作失败
栈空操作失败
栈空操作失败进程已结束，退出代码为 0