【Python 数据结构 5.栈】

目录

一、栈的基本概念

1.栈的概念

2.入栈

入栈的步骤

3.出栈

出栈的步骤

4.获取栈顶元素

获取栈顶元素的步骤

二、 Python中的栈

顺序表实现

链表实现

三、栈的实战

1.LCR 123. 图书整理 I

思路与算法

2.LCR 027. 回文链表

思路与算法

3.1614. 括号的最大嵌套深度

思路与算法

四、栈的应用

轻舟快船，祝你好过春山

—— 25.3.3

一、栈的基本概念

1.栈的概念

栈是仅限在表尾进行插入和删除的线性表，它遵循后进先出(Last-In-First-Out，LIFO)的原则。栈可以类比为一叠盘子，你只能访问顶部的盘子，而添加或删除盘子只能在顶部进行。在计算机科学中，栈通常用于实现：函数调用、递归、表达式求值等操作。我们一般可以用顺序表或者链表来实现栈。

2.入栈

栈元素的插入操作叫做入栈，也可称为进栈、压栈。直接将元素添加到栈的顶部即可。这个操作类似于将盘子添加到叠盘子的顶部。

入栈的步骤

第1步：将元素压入栈中，并将栈顶指针或索引指向新的栈顶元素。

第2步：栈的大小增加了 1，顶部元素为刚刚入栈的元素。

3.出栈

栈元素的删除操作叫做出栈，也可称为弹栈。直接将栈的顶部元素删除即可。这个操作类似于将叠盘子的顶部的盘子拿走的过程。

出栈的步骤

第1步：将栈顶元素删除掉，并将栈顶指针或索引指向新的顶元素。

第2步：栈的大小减小了 1。

4.获取栈顶元素

返回栈顶元素的值，无论是链表还是顺序表，都可以通过栈顶指针在 O(1) 的时间复杂度获取到栈顶元素。

获取栈顶元素的步骤

第1步：利用栈顶指针获取栈顶元素，由于是查询操作，所以不会改变栈本身的数据

二、 Python中的栈

顺序表实现

class Stack:
    def __init__(self):
        self.data = []

    # 入栈操作 直接相当于列表的append操作
    def push(self, val):
        self.data.append(val)

    # 出栈操作 直接相当于列表的pop操作
    def pop(self):
        if self.empty():
            return "Stach is empty"
        return self.data.pop()

    # 获取栈顶元素 直接相当于列表的索引[-1]操作
    def top(self):
        if self.empty():
            return "Stach is empty"
        return self.data[-1]

    def size(self):
        return len(self.data)

    def empty(self):
        return len(self.data) == 0

def test():
    stack = Stack()
    stack.push(1)
    stack.push(2)
    stack.push(3)
    stack.push(4)

    while not stack.empty():
        print(f'Top element: {stack.top()}')
        print(f'Size of stack: {stack.size()}')
        print(f'Popped element: {stack.pop()}')
        print(f'Size of stack: {stack.size()}')
        print("————————————————————————————")
test()

链表实现

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

class Stack:
    def __init__(self):
        self.head = None
        self.len = 0

    # 入栈操作 直接相当于链表的头插法
    def push(self, val):
        new_node = Node(val)
        new_node.next = self.head
        self.head = new_node
        self.len += 1

    # 出栈操作
    def pop(self):
        if self.empty():
            return "St ack is empty"
        val = self.head.val
        self.head = self.head.next
        self.len -= 1
        return val

    # 获取栈顶元素 相当于直接返回链表的头节点
    def top(self):
        if self.empty():
            return "Stach is empty"
        return self.head.val

    def size(self):
        return self.len

    def empty(self):
        return self.len == 0

def test():
    stack = Stack()
    stack.push(1)
    stack.push(2)
    stack.push(3)
    stack.push(4)

    while not stack.empty():
        print(f'Top element: {stack.top()}')
        print(f'Size of stack: {stack.size()}')
        print(f'Popped element: {stack.pop()}')
        print(f'Size of stack: {stack.size()}')
        print("————————————————————————————")
test()

三、栈的实战

1.LCR 123. 图书整理 I

书店店员有一张链表形式的书单，每个节点代表一本书，节点中的值表示书的编号。为更方便整理书架，店员需要将书单倒过来排列，就可以从最后一本书开始整理，逐一将书放回到书架上。请倒序返回这个书单链表。

示例 1：
输入：head = [3,6,4,1]

输出：[1,4,6,3]
提示：

0 <= 链表长度 <= 10000

思路与算法

Ⅰ、栈的使用：代码中使用了栈（Stack）这一数据结构。栈的特点是“后进先出”（LIFO），即最后入栈的元素会最先出栈。利用这一特性，可以将链表中的值依次压入栈中，然后再依次弹出，从而实现反转的效果。

Ⅱ、遍历链表：代码首先通过一个 while 循环遍历链表，将每个节点的值 head.val 压入栈中。遍历结束后，栈中存储了链表所有节点的值，且顺序与链表中的顺序相反。

Ⅲ、反转并生成结果：接着，代码通过另一个 while 循环将栈中的元素依次弹出，并追加到结果列表 res 中。由于栈的 LIFO 特性，弹出的顺序与压入的顺序相反，因此 res 中的元素顺序与链表中的顺序相反，实现了反转的效果。

Ⅳ、返回结果：最后，代码返回 res，即反转后的链表值列表。

列表.append()：用于在列表的末尾添加一个元素。它会直接修改原列表，而不是返回一个新的列表。

参数名	说明	是否必填
`element`	要添加到列表末尾的元素	是

列表.pop()：用于从列表中移除并返回指定索引处的元素。如果不指定索引，默认移除并返回最后一个元素。

参数名	说明	是否必填
`index`	要移除的元素的索引（从0开始）	否

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBookList(self, head: Optional[ListNode]) -> List[int]:
        # 用Python实现数据结构——栈
        Stack = []

        res = []
        while head != None:
            Stack.append(head.val)
            head = head.next
        while len(Stack) > 0:
            res.append(Stack.pop())
        return res

2.LCR 027. 回文链表

给定一个链表的 头节点 head ，请判断其是否为回文链表。

如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。

示例 1：
输入: head = [1,2,3,3,2,1]
输出: true
示例 2：
输入: head = [1,2]
输出: false
提示：

链表 L 的长度范围为 [1, 105]
0 <= node.val <= 9

思路与算法

Ⅰ、使用栈存储链表的值：首先，函数通过遍历链表，将每个节点的值依次压入栈 Stack 中。由于栈是“后进先出”的数据结构，因此栈中存储的节点顺序是链表节点值的逆序。

Ⅱ、比较链表与栈中的值：接着，函数再次遍历链表，同时从栈中弹出元素，将链表节点的值与栈中弹出的值进行比较。如果所有值都匹配，则链表是回文链表；否则，链表不是回文链表。

列表.append()：用于在列表的末尾添加一个元素。它会直接修改原列表，而不是返回一个新的列表。

参数名	说明	是否必填
`element`	要添加到列表末尾的元素	是

列表.pop()：用于从列表中移除并返回指定索引处的元素。如果不指定索引，默认移除并返回最后一个元素。

参数名	说明	是否必填
`index`	要移除的元素的索引（从0开始）	否

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        # 列表逆序也可以用栈
        Stack = []
        tmp = head
        while tmp != None:
            Stack.append(tmp.val)
            tmp = tmp.next
        while head:
            if head.val != Stack.pop():
                return False
            head = head.next
        return True

3.1614. 括号的最大嵌套深度

给定 有效括号字符串 s，返回 s 的 嵌套深度。嵌套深度是嵌套括号的最大数量。

示例 1：

输入：s = "(1+(2*3)+((8)/4))+1"

输出：3

解释：数字 8 在嵌套的 3 层括号中。

示例 2：

输入：s = "(1)+((2))+(((3)))"

输出：3

解释：数字 3 在嵌套的 3 层括号中。

示例 3：

输入：s = "()(())((()()))"

输出：3

提示：

1 <= s.length <= 100
s 由数字 0-9 和字符 '+'、'-'、'*'、'/'、'('、')' 组成
题目数据保证括号字符串 s 是 有效的括号字符串

思路与算法

初始化：top 初始化为 0，表示当前嵌套深度为 0。res 初始化为 0，用于记录最大嵌套深度。

遍历字符串：对于字符串中的每个字符 x：如果 x 是 "("，表示进入一个新的嵌套层级，因此 top 增加 1，并更新 res 为 max(res, top)，以确保 res 始终记录最大深度。如果 x 是 ")"，表示退出当前嵌套层级，因此 top 减少 1。

返回结果：遍历结束后，res 即为字符串中嵌套括号的最大深度。

class Solution:
    def maxDepth(self, s: str) -> int:
        top = 0
        res = 0
        for x in s:
            if x == "(":
                top += 1
                res = max(res, top)
            elif x == ")":
                top -= 1
        return res