Python中链表的最小栈（Min Stack）实现方法

2023-04-11 00:00:00 方法 链表 最小

链表最小栈是一种可以快速获取栈中最小值的数据结构，其实现方式如下：

  1. 定义一个链表节点类，包含当前值、当前节点为止的最小值以及指向下一节点的指针。
  2. 定义一个最小栈类，包含一个头节点、一个计数器以及栈的基本操作方法（压栈、出栈、获取栈顶元素、获取最小值）。
  3. 在压栈时，将当前值与前一个节点的最小值比较，取较小值作为当前节点的最小值。
  4. 在出栈时，返回当前节点的值，并将指针移到下一节点。
  5. 获取栈顶元素时，返回当前指针所指节点的值。
  6. 获取最小值时，返回头节点的最小值属性。

以下是Python语言的代码演示：

class ListNode:
    def __init__(self, val, min_val=None):
        self.val = val
        self.min_val = min_val

    def __str__(self):
        return str(self.val)


class MinStack:
    def __init__(self):
        self.head = None
        self.length = 0

    def push(self, x):
        if self.head is None:
            self.head = ListNode(x, x)
        else:
            cur_min = min(x, self.head.min_val)
            new_node = ListNode(x, cur_min)
            new_node.next = self.head
            self.head = new_node
        self.length += 1

    def pop(self):
        if self.head is not None:
            del_node = self.head
            self.head = del_node.next
            self.length -= 1
            return del_node.val

    def top(self):
        if self.head is not None:
            return self.head.val

    def get_min(self):
        if self.head is not None:
            return self.head.min_val


# 测试代码
s = MinStack()
s.push(3)
s.push(2)
s.push(4)
s.push(1)
print(s.top())  # 输出 1
print(s.get_min())  # 输出 1

s.pop()
s.pop()
print(s.top())  # 输出 2
print(s.get_min())  # 输出 2

相关文章