数据结构与算法–栈、队列篇

一、计算机领域的地位

​ 在计算机科学的广袤领域中，数据结构犹如一座精巧的大厦，为信息的存储和处理提供了坚实的框架。而在众多的数据结构中，栈和队列宛如两颗璀璨的明珠，各自闪耀着独特的光芒。

​ 栈和队列虽然看似简单，却蕴含着深刻的逻辑和强大的功能。它们是解决众多复杂问题的基石，从程序的执行流程控制到各种算法的优化，从操作系统的任务调度到网络通信中的数据传输，栈和队列都发挥着不可或缺的作用。

​ 深入理解栈和队列，不仅能够提升我们对数据组织和操作的认知，更能为我们在编程和算法设计中打开新的思路，使我们能够更加高效、优雅地解决实际问题。在接下来的篇章中，让我们一同走进栈和队列的精彩世界，探索它们的奥秘与魅力。

二、栈（Stack）的详解

栈是一种特殊的线性表，其操作遵循“后进先出（Last In First Out，LIFO）”的原则。

一、栈的定义

​ 栈只允许在一端进行插入（入栈）和删除（出栈）操作，这一端被称为栈顶，而另一端则被称为栈底。

二、栈的基本操作

1. 入栈（Push）：将元素添加到栈顶。
   • 例如，一个初始为空的栈，依次入栈元素 10、20、30 ，此时栈顶元素为 30 。
2. 出栈（Pop）：删除栈顶元素。
   • 对于上述栈，执行出栈操作，先弹出的是 30 。
3. 读取栈顶元素（Peek）：获取栈顶元素的值，但不删除它。
4. 判空（IsEmpty）：判断栈是否为空。

三、栈的实现方式

1. 顺序栈：使用数组来实现。

• 优点：操作简单，随机访问速度快。
• 缺点：需要预先分配固定大小的空间，可能造成空间浪费或溢出。

下面是用python实现的顺序栈结构：

# 顺序栈实现
class SequentialStack:
    def __init__(self, size=10):
        """
        初始化顺序栈

        参数:
        size (int): 栈的初始大小
        """
        self.stack = [None] * size  # 存储栈元素的列表
        self.top = -1  # 栈顶指针

    def is_empty(self):
        """
        判断栈是否为空

        返回:
        bool: 如果栈为空返回 True，否则返回 False
        """
        return self.top == -1

    def is_full(self):
        """
        判断栈是否已满

        返回:
        bool: 如果栈已满返回 True，否则返回 False
        """
        return self.top == len(self.stack) - 1

    def push(self, element):
        """
        向栈中压入元素

        参数:
        element: 要压入栈的元素

        异常:
        Exception: 如果栈已满，抛出"Stack Overflow"异常
        """
        if self.is_full():
            raise Exception("Stack Overflow")
        self.top += 1
        self.stack[self.top] = element

    def pop(self):
        """
        从栈中弹出元素

        返回:
        弹出的元素

        异常:
        Exception: 如果栈为空，抛出"Stack Underflow"异常
        """
        if self.is_empty():
            raise Exception("Stack Underflow")
        element = self.stack[self.top]
        self.stack[self.top] = None
        self.top -= 1
        return element

    def peek(self):
        """
        查看栈顶元素但不弹出

        返回:
        栈顶元素

        异常:
        Exception: 如果栈为空，抛出"Stack is empty"异常
        """
        if self.is_empty():
            raise Exception("Stack is empty")
        return self.stack[self.top]

​ 2. 链式栈：使用链表来实现。

• 优点：灵活，不受固定空间限制。
• 缺点：访问节点需要遍历，效率相对较低。

下面是用python实现的链式栈结构：

# 链式栈节点
class Node:
    def __init__(self, data=None):
        """
        初始化链式栈节点

        参数:
        data: 节点存储的数据，默认为 None
        """
        self.data = data
        self.next = None


# 链式栈实现
class LinkedStack:
    def __init__(self):
        """
        初始化链式栈
        """
        self.top = None  # 栈顶节点

    def is_empty(self):
        """
        判断链式栈是否为空

        返回:
        bool: 如果为空返回 True，否则返回 False
        """
        return self.top is None

    def push(self, element):
        """
        向链式栈中压入元素

        参数:
        element: 要压入的元素
        """
        new_node = Node(element)  # 创建新节点
        new_node.next = self.top  # 新节点指向当前栈顶
        self.top = new_node  # 更新栈顶

    def pop(self):
        """
        从链式栈中弹出元素

        返回:
        弹出的元素

        异常:
        Exception: 如果栈为空，抛出"Stack Underflow"异常
        """
        if self.is_empty():
            raise Exception("Stack Underflow")
        element = self.top.data  # 获取栈顶节点数据
        self.top = self.top.next  # 更新栈顶
        return element

    def peek(self):
        """
        查看链式栈栈顶元素但不弹出

        返回:
        栈顶元素

        异常:
        Exception: 如果栈为空，抛出"Stack is empty"异常
        """
        if self.is_empty():
            raise Exception("Stack is empty")
        return self.top.data

四、栈的应用场景

1. 函数调用：函数的调用和返回可以通过栈来管理。

• 当一个函数被调用时，相关的参数、局部变量等信息被压入栈中；函数返回时，这些信息从栈中弹出。

1. 表达式求值：如中缀表达式转后缀表达式，然后进行计算。
2. 括号匹配：检查表达式中的括号是否正确匹配。
3. 回溯算法：在搜索过程中保存当前状态，以便回溯。

​ 总之，栈虽然结构简单，但在计算机科学的众多领域中发挥着重要作用，是理解和解决许多复杂问题的基础工具。

三、队列(Queue)的详解

一、队列的定义

​ 队列只允许在一端进行插入操作（称为队尾，Rear），在另一端进行删除操作（称为队头，Front）。

二、队列的基本操作

1. 入队（Enqueue）：将元素添加到队尾。
   • 例如，一个初始为空的队列，依次入队元素 5、15、25 ，此时队头元素为 5 。
2. 出队（Dequeue）：删除队头元素。
   • 对于上述队列，执行出队操作，先弹出的是 5 。
3. 读取队头元素（Front）：获取队头元素的值，但不删除它。
4. 判空（IsEmpty）：判断队列是否为空。
5. 判满（IsFull）：对于有固定大小的队列，判断是否已满。

三、队列的实现方式

1. 顺序队列：使用数组来实现。
   • 可能会出现“假溢出”的情况，即队列未满但无法再插入元素。
   • 为解决此问题，可采用循环队列的方式。

以下是用python代码实现的顺序队列：

class SequentialQueue:
    def __init__(self, size=10):
        self.queue = [None] * size
        self.front = 0
        self.rear = 0

    def is_empty(self):
        return self.front == self.rear

    def is_full(self):
        return (self.rear + 1) % len(self.queue) == self.front

    def enqueue(self, element):
        if self.is_full():
            raise Exception("Queue Overflow")
        self.queue[self.rear] = element
        self.rear = (self.rear + 1) % len(self.queue)

    def dequeue(self):
        if self.is_empty():
            raise Exception("Queue Underflow")
        element = self.queue[self.front]
        self.queue[self.front] = None
        self.front = (self.front + 1) % len(self.queue)
        return element

    def get_front(self):
        if self.is_empty():
            raise Exception("Queue is empty")
        return self.queue[self.front]

​ 创建一个队列对象即可使用。

1. 链式队列：使用链表来实现。

以下是用python实现的链式队列：

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

class Queue:
    def __init__(self):
        self.front = None
        self.rear = None

    def enqueue(self, data):
        new_node = Node(data)
        if not self.rear:
            self.front = new_node
            self.rear = new_node
        else:
            self.rear.next = new_node
            self.rear = new_node

    def dequeue(self):
        if not self.front:
            return "Queue is empty"
        temp = self.front
        if self.front == self.rear:
            self.front = None
            self.rear = None
        else:
            self.front = self.front.next
        return temp.data

    def is_empty(self):
        return self.front is None

    def print_queue(self):
        current = self.front
        while current:
            print(current.data, end=" ")
            current = current.next
        print()

# 测试队列
q = Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
q.print_queue()  
print(q.dequeue())  
q.print_queue()  

经测试，得出链式队列具有较强的稳定性。

四、队列的应用场景

1. 任务调度：操作系统按照任务进入队列的先后顺序进行调度。
2. 消息队列：在分布式系统中用于消息的传递和处理。
3. 广度优先搜索：在图的遍历中使用队列来保存待访问的节点。

​ 总之，队列以其独特的先进先出特性，在计算机科学和实际应用中发挥着重要作用，为数据的有序处理提供了有效的手段。

四、BFS（广度优先搜索）和队列的关系：

​ BFS 通常使用队列来实现。在 BFS 中，我们先访问起始节点，然后将其相邻节点放入队列。接着依次取出队列头部的节点，并将其未访问过的相邻节点放入队列。这个过程一直持续，直到队列为空。

例如，对于一个简单的二叉树：

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

# 构建二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

def bfs(root):
    queue = [root]
    while queue:
        current = queue.pop(0)
        print(current.value)
        if current.left:
            queue.append(current.left)
        if current.right:
            queue.append(current.right)

bfs(root)

五、DFS（深度优先搜索）和栈的关系：

​ DFS 通常使用栈来实现。在 DFS 中，我们先访问起始节点，然后将其相邻节点压入栈。接着取出栈顶节点，并将其未访问过的相邻节点压入栈。这个过程一直持续，直到栈为空。

以下是一个使用栈实现 DFS 的示例：

def dfs(root):
    stack = [root]
    while stack:
        current = stack.pop()
        print(current.value)
        if current.right:
            stack.append(current.right)
        if current.left:
            stack.append(current.left)

dfs(root)

总结：

​ 队列是先进先出的数据结构，适合 BFS 逐层扩展搜索。栈是先进后出的数据结构，适合 DFS 深入一条路径后再回溯。通过这些数据结构的特性，能够有效地实现不同的搜索策略。

​ 例如，在图的遍历中，如果要尽快找到距离起始节点较近的所有节点，通常使用 BFS；而如果要探索整个图的所有可能路径或者找到一条到达目标节点的最长路径，可能会使用 DFS。

“且将新火试新茶，诗酒趁年华”——《望江南·超然台作》