当前位置：首页 > article >正文

基于c++版本链栈改-Python思维总结

article 2024/11/15 8:21:59

##栈部分-（叠猫猫）

##抽象数据类型栈的定义：是一种遵循先入后出的逻辑的线性数据结构。

##栈的链式表示

使用链表实现栈时，我们可以将链表的头结点视为栈顶，尾结点视为栈底。

在进行插入元素的时候我们只需要把结点插入链表的头部，这种方法被称为“头插法”。

在进行删除操作时只需要把头结点删除即可。

##链栈示意图

##图解

##Python链栈代码实现

class ListNode(object):
    """定义链表"""
    def __init__(self):
        self.val = None
        self.next = None

class LinkedListStack:
    """基于链表实现的栈"""

    def __init__(self):
        """构造方法"""
        self._peek:ListNode | None = None
        self._size: int = 0

    def size(self):
        """获取栈的长度"""
        return self._size

    def is_empty(self):
        """判断栈是否为空"""
        return self._size

    def push(self,val):
        """入栈"""
        node = ListNode(val)
        node.next = self._peek
        self._peek = node
        self._size += 1

    def pop(self):
        """出栈"""
        if self.is_empty():
            raise  IndexError("栈为空")
        return self._peek.val

    def to_list(self):
        """转化为列表用于打印"""
        arr = []
        node = self._peek
        while node :
            arr.append(node.val)
            node = node.next
        arr.reverse()
        return arr

时间效率：在基于链表的实现中，链表的扩容非常灵活，不存在上述数组扩容时效率降低的问题。但是，入栈操作需要初始化节点对象并修改指针，因此效率相对较低。不过，如果入栈元素本身就是节点对象，那么可以省去初始化步骤，从而提高效率。

空间效率：由于链表节点需要额外存储指针，因此链表节点占用的空间相对较大。