数据结构与算法04-栈和队列

介绍

栈和队列。事实上它们并不是全新的东西，只不过是多加了一些约束条件的数组而已。但正是这些约束条件为它们赋予了巧妙的用法。

栈和队列都是处理临时数据的灵活工具。在操作系统、打印任务、数据遍历等各种需要临时容器才能构造出美妙算法的场景，它们都大有作为。

栈🎰

每次压栈都是把数据加到栈顶（也就是栈的末尾）。如果想把 0 插入到栈底或中间，那是不允许的，因为这就是栈的特性：只能在末尾插入数据。
从栈顶移除数据叫作出栈。这也是栈的限制：只能移除末尾的数据。

压栈和出栈可被形容为 LIFO（last in，first out）后进先出。解释起来就是最后入栈的元素，
会最先出栈。就像无心向学的学生，最迟到校的总是他，最早回家的也是他😹。

在这里插入图片描述

使用场景

用栈去跟踪函数的调用
语法检查
例如检查一段代码或数学表达式中的括号是否正确配对。下面是一个使用Python实现的简单示例，用于检测一个字符串中的圆括号、方括号和花括号是否匹配：

def is_brackets_matched(expression):
    # 定义一个字典，用于匹配括号
    brackets_map = {')': '(', '}': '{', ']': '['}
    # 初始化一个空栈
    stack = []

    for char in expression:
        # 如果当前字符是右括号
        if char in brackets_map:
            # 获取栈顶的元素，如果栈为空或者栈顶的元素不是对应的左括号，则不匹配
            if not stack or stack.pop() != brackets_map[char]:
                return False
        else:
            # 非右括号的字符直接压入栈中
            stack.append(char)

    # 如果最后栈为空，说明所有括号都已匹配；否则，有未匹配的括号
    return not stack

# 测试
test_cases = ["()", "(]", "{[()]}", "{[(])}", "((()))", "[{()}]"]
for case in test_cases:
    print(f"{case}: {is_brackets_matched(case)}")

队列🚃

你可以将队列想象成是电影院排队。排在最前面的人会最先离队进入影院。套用到队列上，
就是首先加入队列的，将会首先从队列移出。因此计算机科学家都用缩写“FIFO”（first in, first out）
先进先出，来形容它。

使用场景

从打印机的作业设置，到网络应用程序的后台任务，都有队列的存在
一个简单的队列使用场景是打印任务调度。假设你有一个打印机，多个用户同时提交打印任务，你可以使用队列来管理这些任务，确保它们按照提交的顺序依次打印。以下是一个简单的Python实现：

class Printer:
    def __init__(self):
        self.print_queue = []

    def submit_job(self, job):
        self.print_queue.append(job)
        print(f"任务 {job} 已加入打印队列")

    def print_next(self):
        if self.print_queue:
            next_job = self.print_queue.pop(0)
            print(f"正在打印任务 {next_job}")
        else:
            print("打印队列为空")

# 创建打印机对象
printer = Printer()

# 用户提交打印任务
printer.submit_job("报告1")
printer.submit_job("报告2")
printer.submit_job("报告3")

# 打印下一个任务
printer.print_next()
printer.print_next()
printer.print_next()

# 输出：
# 任务 报告1 已加入打印队列
# 任务 报告2 已加入打印队列
# 任务 报告3 已加入打印队列
# 正在打印任务 报告1
# 正在打印任务 报告2
# 正在打印任务 报告3