使用Python函数实现数据结构操作：栈、队列和链表

数据结构是计算机科学中非常重要的内容，它是指不同数据元素之间的相互关系以及这些关系在计算机中的组织方式。在程序设计中，使用数据结构可以更加高效地处理问题，提高程序运行速度。而栈、队列和链表则是常用的数据结构。

Python 作为一种脚本语言，在数据结构方面的支持非常完备。本文将分别介绍如何使用 Python 函数实现栈、队列和链表的相关操作。

一、栈

1. 基本操作

栈是一种后进先出（Last In First Out，LIFO）的数据结构，相当于一个箱子，后进去的元素会被放在箱子的顶部，先进去的元素则会放在底部，需要先取出底部的元素才能获得顶部的元素。下面我们来实现栈的基本操作：压入、弹出、读取栈顶元素和判断栈是否为空。

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

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

    def pop(self):
        if not self.is_empty():
            return self.stack.pop()

    def peek(self):
        if not self.is_empty():
            return self.stack[-1]

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

2. 括号匹配

栈在括号匹配问题中非常有用。对于输入的字符串，如果左括号和右括号能够完全匹配，则该字符串是合法的，否则是不合法的。下面我们来实现一个验证括号匹配的函数。

def is_match(p1, p2):
    if p1 == '(' and p2 == ')':
        return True
    elif p1 == '{' and p2 == '}':
        return True
    elif p1 == '[' and p2 == ']':
        return True
    else:
        return False

def check_parentheses(input_str):
    stack = Stack()
    for char in input_str:
        if char in '({[':
            stack.push(char)
        elif char in ')}]':
            if stack.is_empty():
                return False
            if not is_match(stack.pop(), char):
                return False

    return stack.is_empty()

二、队列

1. 基本操作

队列是一种先进先出（First In First Out，FIFO）的数据结构，相当于排队，先进队列的元素会被先取出队列，后进队列的元素则会在后面等待。下面我们来实现队列的基本操作：入队、出队、读取队头元素和判断队列是否为空。

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

    def enqueue(self, item):
        self.queue.append(item)

    def dequeue(self):
        if not self.is_empty():
            return self.queue.pop(0)

    def peek(self):
        if not self.is_empty():
            return self.queue[0]

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

2. 广度优先搜索

队列在广度优先搜索算法（Breadth First Search，BFS）中非常有用。BFS 是一种图搜索算法，从图的某个顶点开始，依次访问其相邻的顶点，重复这个过程，直到所有顶点都被访问。下面我们来实现 BFS 算法。

# 实现有向图
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

def bfs(graph, start):
    visited = set()
    queue = Queue()

    visited.add(start)
    queue.enqueue(start)

    while not queue.is_empty():
        node = queue.dequeue()
        print(node, end=' ')

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.enqueue(neighbor)

三、链表

1. 基本操作

链表是一种基于指针的数据结构，每个节点都包含一个数据元素和一个指向下一个节点的指针。相比于数组，链表的插入和删除操作非常高效。下面我们来实现链表的基本操作：添加节点、删除节点和遍历链表。

# 定义节点类
class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

# 定义链表类
class LinkedList:
    def __init__(self):
        self.head = None

    def add_node(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        curr_node = self.head
        while curr_node.next is not None:
            curr_node = curr_node.next
        curr_node.next = new_node

    def delete_node_by_value(self, value):
        if self.head is None:
            return
        curr_node = self.head
        if curr_node.data == value:
            self.head = curr_node.next
            return
        while curr_node.next is not None and curr_node.next.data != value:
            curr_node = curr_node.next
        if curr_node.next is None:
            return
        curr_node.next = curr_node.next.next

    def traverse(self):
        curr_node = self.head
        while curr_node is not None:
            print(curr_node.data, end=' ')
            curr_node = curr_node.next

2. 链表翻转

链表翻转是链表操作中的一道经典问题，即将链表中的节点按照相反的顺序排列。下面我们来实现这个函数。

def reverse_linked_list(head):
    prev_node = None
    curr_node = head
    while curr_node is not None:
        next_node = curr_node.next
        curr_node.next = prev_node
        prev_node = curr_node
        curr_node = next_node
    return prev_node

以上就是使用 Python 函数实现数据结构操作的示例代码。这些代码具有一些通用性，因此可以在 Python 编程中得到广泛的应用。除了以上这些常见的数据结构操作，Python 还提供了更多有用的数据结构和函数，帮助程序员更加高效地解决问题。