【大模型2609·数据结构算法·04】受限线性结构：栈与队列的设计实现及经典括号匹配

专栏导读：受限线性结构在计算机系统与语法解析中无处不在。本篇深度剖析后进先出（LIFO）栈与先进先出（FIFO）队列的工程实现，详解顺序栈、链式栈与环形队列的设计考量，并结合经典 LeetCode“有效括号匹配”算法题展开实战推演。

---

栈

栈的概述

栈（Stack）是一个线性结构，其维护了一个有序的数据列表，列表的一端称为栈顶（top），另一端称为栈底（bottom）。栈对数据的操作有明确限定，插入元素只能从栈顶进行，删除元素也只能栈顶开始逐个进行，通常将插入元素称为入栈（push），删除元素称为出栈（pop）。正是由于上述规定，栈保证了后进先出的原则（LIFO，Last-In-First-Out）。

栈的底层实现既可以选择数组也可以选择链表，只要能保证后进先出的原则即可。

栈的功能定义

方法	说明
size()	返回栈中元素个数
is_empty()	判断栈是否为空
push(item)	将新元素压入栈中
pop()	获取栈顶元素，并将栈顶元素弹出栈
peek()	获取栈顶元素，但不弹出栈

栈的实现

使用动态数组实现一个栈。

class Stack:
    def __init__(self):
        """初始化栈"""
        self.__size = 0
        self.__items = []

    @property
    def size(self):
        """获取栈元素个数"""
        return self.__size

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

    def push(self, item):
        """入栈"""
        self.__items.append(item)
        self.__size += 1

    def pop(self):
        """出栈"""
        if self.is_empty():
            raise Exception("栈为空")
        item = self.__items[self.__size - 1]
        del self.__items[self.__size - 1]
        self.__size -= 1
        return item

    def peek(self):
        """访问栈顶元素"""
        if self.is_empty():
            raise Exception("栈为空")
        return self.__items[self.__size - 1]

栈的应用

有效括号

力扣20题https://leetcode.cn/problems/valid-parentheses/description/

题目描述

给定一个只包括“(”，“)”，“[”，“]”，“{”，“}”的字符串s，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。

每个右括号都有一个对应的相同类型的左括号。

示例

示例 1：

输入：s = “()”

输出：true

示例 2：

输入：s = “()[]{}”

输出：true

示例 3：

输入：s = “(]”

输出：false

示例 4：

输入：s = “([])”

输出：true

思路分析

遇到左括号则入栈，遇到右括号则出栈一个左括号与之匹配，如果能够匹配则继续，如果匹配失败或者栈为空则返回False。

代码实现

class Solution:
    def isValid(self, s):
        stack = []
        for i in s:
            match i:
                case "(" | "[" | "{":
                    stack.append(i)
                case ")":
                    if (not stack) or (stack.pop() != "("):
                        return False
                case "]":
                    if (not stack) or (stack.pop() != "["):
                        return False
                case "}":
                    if (not stack) or (stack.pop() != "{"):
                        return False
        return True if not stack else False

if __name__ == "__main__":
    solution = Solution()
    s = "()[]{}"
    print(s, solution.isValid(s))
    s = "(]"
    print(s, solution.isValid(s))
    s = "([)]"
    print(s, solution.isValid(s))
    s = "{[]}"
    print(s, solution.isValid(s))

队列

队列的概述

队列（Queue）也是一个线性结构，其同样维护了一个有序的数据列表，队列的一端称为队首，另一端称为队尾。队列也对数据操作做出了明确限定，插入元素只能从队尾进行，删除元素只能从队首进行，通常将插入操作称为入队（enqueue），将删除操作称为出队（dequeue）。也正是由于上述限制，队列保证了先进先出（FIFO，First-In-First-Out）的原则。

队列的底层实现既可以选择数组也可以选择链表，只要能保证先进先出的原则即可。

常见的队列包括两种：

单向队列：只能从一端插入数据，从另一端删除数据，遵循先进先出。

双向队列：在队列的两端都可以进行插入和删除操作。

队列的功能定义

方法	说明
size()	返回队列中元素个数
is_empty()	判断队列是否为空
push(item)	向队尾添加元素
pop()	从队首取出元素
peek()	访问队首元素

队列的实现

使用链表实现一个单向队列。

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

class Queue:
    def __init__(self):
        """初始化队列"""
        self.__head = None
        self.__tail = None
        self.__size = 0

    @property
    def size(self):
        """获取队列元素个数"""
        return self.__size

    def is_empty(self):
        """判断队列是否为空"""
        return self.__size == 0

    def push(self, data):
        """入队"""
        node = Node(data)
        if self.is_empty():
            self.__head = node
            self.__tail = node
        else:
            self.__tail.next = node
            self.__tail = node
        self.__size += 1

    def pop(self):
        """ "出队"""
        if self.is_empty():
            raise Exception("队列为空")
        data = self.__head.data
        self.__head = self.__head.next
        self.__size -= 1
        return data

    def peek(self):
        """访问队首元素"""
        if self.is_empty():
            raise Exception("队列为空")
        return self.__head.data