1
def push(self, val: int):
2
    """元素入堆"""
3
    # 添加节点
4
    self.max_heap.append(val)
5
    # 从底至顶堆化
6
    self.sift_up(self.size() - 1)
7

8
def sift_up(self, i: int):
9
    """从节点 i 开始，从底至顶堆化"""
10
    while True:
11
        # 获取节点 i 的父节点
12
        p = self.parent(i)
13
        # 当“越过根节点”或“节点无须修复”时，结束堆化
14
        if p < 0 or self.max_heap[i] <= self.max_heap[p]:
15
            break
16
        # 交换两节点
17
        self.swap(i, p)
18
        # 循环向上堆化
19
        i = p

1
def pop(self) -> int:
2
    """元素出堆"""
3
    # 判空处理
4
    if self.is_empty():
5
        raise IndexError("堆为空")
6
    # 交换根节点与最右叶节点（即交换首元素与尾元素）
7
    self.swap(0, self.size() - 1)
8
    # 删除节点
9
    val = self.max_heap.pop()
10
    # 从顶至底堆化
11
    self.sift_down(0)
12
    # 返回堆顶元素
13
    return val
14

15
def sift_down(self, i: int):
16
    """从节点 i 开始，从顶至底堆化"""
17
    while True:
18
        # 判断节点 i, l, r 中值最大的节点，记为 ma
19
        l, r, ma = self.left(i), self.right(i), i
20
        if l < self.size() and self.max_heap[l] > self.max_heap[ma]:
21
            ma = l
22
        if r < self.size() and self.max_heap[r] > self.max_heap[ma]:
23
            ma = r
24
        # 若节点 i 最大或索引 l, r 越界，则无须继续堆化，跳出
25
        if ma == i:
26
            break
27
        # 交换两节点
28
        self.swap(i, ma)
29
        # 循环向下堆化
30
        i = ma

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

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

9
    def size(self) -> int:
10
        """获取栈的长度"""
11
        return self._size
12

13
    def is_empty(self) -> bool:
14
        """判断栈是否为空"""
15
        return not self._peek
16

17
    def push(self, val: int):
18
        """入栈"""
19
        node = ListNode(val)
20
        node.next = self._peek
21
        self._peek = node
22
        self._size += 1
23

24
    def pop(self) -> int:
25
        """出栈"""
26
        num = self.peek()
27
        self._peek = self._peek.next
28
        self._size -= 1
29
        return num
30

31
    def peek(self) -> int:
32
        """访问栈顶元素"""
33
        if self.is_empty():
34
            raise IndexError("栈为空")
35
        return self._peek.val
36

37
    def to_list(self) -> list[int]:
38
        """转化为列表用于打印"""
39
        arr = []
40
        node = self._peek
41
        while node:
42
            arr.append(node.val)
43
            node = node.next
44
        arr.reverse()
45
        return arr

1
class ArrayStack:
2
    """基于数组实现的栈"""
3

4
    def __init__(self):
5
        """构造方法"""
6
        self._stack: list[int] = []
7

8
    def size(self) -> int:
9
        """获取栈的长度"""
10
        return len(self._stack)
11

12
    def is_empty(self) -> bool:
13
        """判断栈是否为空"""
14
        return self._stack == []
15

16
    def push(self, item: int):
17
        """入栈"""
18
        self._stack.append(item)
19

20
    def pop(self) -> int:
21
        """出栈"""
22
        if self.is_empty():
23
            raise IndexError("栈为空")
24
        return self._stack.pop()
25

26
    def peek(self) -> int:
27
        """访问栈顶元素"""
28
        if self.is_empty():
29
            raise IndexError("栈为空")
30
        return self._stack[-1]
31

32
    def to_list(self) -> list[int]:
33
        """返回列表用于打印"""
34
        return self._stack