深入理解数据结构：栈与队列的实现与应用

在计算机科学中，数据结构是组织和存储数据的一种方式。栈（Stack）和队列（Queue）是两种非常基础且重要的线性数据结构。本文将详细介绍栈与队列的基本概念、操作方法，并通过Python代码实现它们的功能，最后探讨其实际应用场景。

栈（Stack）

基本概念

栈是一种后进先出（LIFO, Last In First Out）的数据结构。这意味着最后被添加到栈中的元素会最先被移除。这种特性使得栈在许多场景下都非常有用，比如函数调用、表达式求值等。

基本操作

Python实现

我们可以使用Python列表来模拟栈的行为：

class Stack:    def __init__(self):        self.items = []    def is_empty(self):        return len(self.items) == 0    def push(self, item):        self.items.append(item)    def pop(self):        if not self.is_empty():            return self.items.pop()        else:            raise IndexError("pop from empty stack")    def peek(self):        if not self.is_empty():            return self.items[-1]        else:            raise IndexError("peek from empty stack")    def size(self):        return len(self.items)# 示例使用s = Stack()s.push(1)s.push(2)print(s.peek())  # 输出: 2s.pop()print(s.size())  # 输出: 1

队列（Queue）

基本概念

队列是一种先进先出（FIFO, First In First Out）的数据结构。这意味着最早被添加到队列中的元素会最先被移除。队列通常用于任务调度、缓冲处理等领域。

基本操作

Python实现

同样地，我们可以使用Python列表来模拟队列的行为，但为了效率考虑，这里推荐使用collections.deque，它提供了双端队列的支持，适合频繁的插入和删除操作：

from collections import dequeclass Queue:    def __init__(self):        self.items = deque()    def is_empty(self):        return len(self.items) == 0    def enqueue(self, item):        self.items.append(item)    def dequeue(self):        if not self.is_empty():            return self.items.popleft()        else:            raise IndexError("dequeue from empty queue")    def front(self):        if not self.is_empty():            return self.items[0]        else:            raise IndexError("front from empty queue")    def size(self):        return len(self.items)# 示例使用q = Queue()q.enqueue('a')q.enqueue('b')print(q.front())  # 输出: 'a'q.dequeue()print(q.size())  # 输出: 1

应用场景

栈的应用

表达式求值

栈可以用来解析和计算数学表达式。例如，我们可以使用两个栈分别存储数字和运算符来实现基本的计算器功能。

def evaluate_expression(expression):    operators = set(['+', '-', '*', '/'])    priority = {'+':1, '-':1, '*':2, '/':2}    op_stack = []    num_stack = []    tokens = expression.split()    for token in tokens:        if token.isdigit():            num_stack.append(int(token))        elif token in operators:            while (op_stack and op_stack[-1] in operators and                   priority[op_stack[-1]] >= priority[token]):                num2 = num_stack.pop()                num1 = num_stack.pop()                operator = op_stack.pop()                result = apply_operator(operator, num1, num2)                num_stack.append(result)            op_stack.append(token)        elif token == '(':            op_stack.append(token)        elif token == ')':            while op_stack[-1] != '(':                num2 = num_stack.pop()                num1 = num_stack.pop()                operator = op_stack.pop()                result = apply_operator(operator, num1, num2)                num_stack.append(result)            op_stack.pop()  # 弹出'('    while op_stack:        num2 = num_stack.pop()        num1 = num_stack.pop()        operator = op_stack.pop()        result = apply_operator(operator, num1, num2)        num_stack.append(result)    return num_stack[0]def apply_operator(op, a, b):    if op == '+': return a + b    if op == '-': return a - b    if op == '*': return a * b    if op == '/': return a / b# 示例expr = "3 + ( 4 * 5 )"print(evaluate_expression(expr))  # 输出: 23

队列的应用

广度优先搜索（BFS）

队列常用于图的广度优先搜索算法中。以下是一个简单的BFS示例，展示如何使用队列遍历图的所有节点。

from collections import defaultdictdef bfs(graph, start):    visited = set()    queue = Queue()    queue.enqueue(start)    visited.add(start)    while not queue.is_empty():        vertex = queue.dequeue()        print(vertex, end=" ")        for neighbour in graph[vertex]:            if neighbour not in visited:                visited.add(neighbour)                queue.enqueue(neighbour)# 示例图graph = defaultdict(list)graph['A'] = ['B', 'C']graph['B'] = ['D', 'E']graph['C'] = ['F']graph['E'] = ['F']bfs(graph, 'A')  # 输出: A B C D E F

总结来说，栈和队列作为基础的数据结构，在解决各种计算问题时发挥着重要作用。通过上述代码示例，我们不仅了解了它们的理论知识，也学会了如何在实际编程中应用这些结构。