9 数据结构概述之栈和队列

在上篇中，我们讨论了链表这一基本数据结构，它为我们提供了灵活的元素存储方式。在本篇中，我们将探讨两个非常重要的数据结构——栈和队列。这两者虽然简单，但在不同的场景中都有着广泛的应用。

一、栈（Stack）

1.1 栈的概念

栈是一种后进先出（LIFO，Last In First Out）的数据结构。这意味着，最后放入栈中的元素会是第一个被移除的元素。可以想象一个现实中的纸箱，最后放进去的纸张会在最上面，取出的时候只能从最上面开始取。

1.2 栈的基本操作

栈主要支持以下几种操作：

• push(x)：将元素x压入栈中
• pop()：将栈顶元素弹出
• peek()：返回栈顶元素但不移除
• isEmpty()：判断栈是否为空

1.3 栈的应用案例

一个经典的例子是表达式的括号匹配。假设我们需要检查字符串中的括号是否匹配，可以利用栈来实现：

def is_valid_parentheses(s: str) -> bool:
    stack = []
    parentheses_map = {')': '(', '}': '{', ']': '['}
    
    for char in s:
        if char in parentheses_map.values():
            stack.append(char)
        elif char in parentheses_map.keys():
            if stack == [] or parentheses_map[char] != stack.pop():
                return False
    return stack == []

# 测试
print(is_valid_parentheses("()[]{}"))  # 输出: True
print(is_valid_parentheses("(]"))      # 输出: False

在这个示例中，我们通过遍历字符串，使用栈来存储开放的括号，当遇到闭合括号时，检查栈顶元素是否匹配，最终判断字符串的括号是否有效。

二、队列（Queue）

2.1 队列的概念

队列是一种先进先出（FIFO，First In First Out）的数据结构。与栈相反，队列中最先入队的元素会是第一个被出队的元素。可以将其视为排队的过程，最早到达队列的元素会最早被处理。

2.2 队列的基本操作

队列主要支持以下几种操作：

• enqueue(x)：将元素x入队
• dequeue()：将队头元素出队
• peek()：返回队头元素但不移除
• isEmpty()：判断队列是否为空

2.3 队列的应用案例

一个常见的应用是任务调度。我们可以使用队列来管理等待处理的任务。以下是一个简单的例子：

from collections import deque

class TaskQueue:
    def __init__(self):
        self.queue = deque()

    def add_task(self, task):
        self.queue.append(task)

    def process_task(self):
        if not self.is_empty():
            return self.queue.popleft()
        return None

    def is_empty(self):
        return len(self.queue) == 0

# 测试
task_queue = TaskQueue()
task_queue.add_task("Task 1")
task_queue.add_task("Task 2")

while not task_queue.is_empty():
    print("Processing:", task_queue.process_task())

在上述示例中，我们使用deque来实现一个简单的任务队列，能够添加和处理任务。

三、小结

栈和队列是非常基本但强大的数据结构。它们在程序设计中扮演着重要的角色，通过实用的操作和特性，能够帮助我们解决各种问题。在下一篇中，我们将继续探索数据结构概述，讨论更复杂的数据结构——树和图，敬请期待！