数据结构基础：栈和队列的应用

# 1. 数据结构概述

## 1.1 数据结构的定义与作用
数据结构是指数据元素之间的关系，以及对这些关系操作的方法。它在计算机科学中起着至关重要的作用，能够帮助我们更有效地组织和处理数据。

## 1.2 数据结构分类
数据结构可以分为线性结构和非线性结构。线性结构包括数组、链表、栈和队列；非线性结构包括树和图等。

## 1.3 栈和队列的基本概念
栈和队列是常见的数据结构，它们分别具有后进先出（LIFO）和先进先出（FIFO）的特性。栈包括入栈和出栈操作；队列包括入队和出队操作。这些基本概念为后续章节讨论栈和队列的应用打下了基础。

# 2. 栈的应用

栈是一种具有特殊操作约束的线性表，后进先出（LIFO，Last In First Out）。在本章中，我们将深入探讨栈的特点、常见操作以及栈在计算机领域中的应用。

### 2.1 栈的特点与操作

栈具有如下特点：
- 只能在栈顶进行插入和删除操作
- 不支持随机访问
- 后进先出的特点适用于很多实际场景

栈常见的操作包括：
- `push(element)`: 将元素压入栈顶
- `pop()`: 弹出栈顶元素
- `peek()`: 返回栈顶元素但不弹出
- `isEmpty()`: 判断栈是否为空
- `size()`: 返回栈中元素的个数

### 2.2 栈在计算机中的应用

栈在计算机领域中有广泛的应用，其中包括但不限于：
- **递归函数调用的实现**：函数调用时参数、返回地址和局部变量通过栈来管理
- **表达式求值**：中缀表达式转后缀表达式、后缀表达式求值的算法中使用栈
- **浏览器的历史记录**：浏览器使用栈来记录用户的访问历史
- **编译器中的语法分析**：编译器将中缀表达式转换为后缀表达式的算法中使用栈

### 2.3 栈的实际案例分析

以下是一个使用栈的实际案例，利用栈来判断括号匹配：

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

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def peek(self):
        return self.items[-1]

    def isEmpty(self):
        return self.items == []

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

def isParenthesisMatch(str):
    stack = Stack()
    mapping = {")": "(", "}": "{", "]": "["}
    for char in str:
        if char in mapping.values():
            stack.push(char)
        elif char in mapping.keys():
            if stack.isEmpty():
                return False
            else:
                top_element = stack.pop()
                if mapping[char] != top_element:
                    return False
    return stack.isEmpty()

print(isParenthesisMatch("(){}[]"))  # Output: True
print(isParenthesisMatch("([)]"))    # Output: False

上述代码演示了如何使用栈来检查括号匹配，其中 `Stack` 类实现了栈的基本操作，并通过遍历括号字符串的方式来判断括号是否匹配。

# 3. 队列的应用

队列是一种先进先出（FIFO）的数据结构，具有以下特点：

- 队列的基本操作包括入队（enqueue）和出队（dequeue），即在队列尾部添加元素和在队列头部移除元素。
- 队列的应用场景广泛，例如处理任务调度、实现消息队列、BFS算法等。

#### 3.1 队列的特点与操作

队列的特点使其适合于需要严格按照顺序处理元素的场景，如任务等待队列、消息传递等。队列的操作包括：

- 入队操作（enqueue）：在队列尾部添加元素。
- 出队操作（dequeue）：从队列头部移除元素。
- 队列为空判断（isEmpty）：判断队列是否为空。
- 获取队首元素（front）：查看队列头部元素但不移除。
- 获取队列长度（size）：计算队列中元素的数量。

class Queue:
    def __init__(self):
        self.items = []

    def enqueue(self, item):