双向链表、循环链表、栈

双向循环链表

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

思维导图