在 Python 编程的广阔天地中，数据结构是组织和存储数据的重要方式，如同精心规划的仓库布局，能让数据的管理与访问高效有序。接下来，我们一同深入了解栈、队列、链表、树、图这几种常用的数据结构。
栈（Stack）后进先出的 “弹匣”栈是一种后进先出（LIFO，Last In First Out）的数据结构，形象地说，它就像一个弹匣，最后压入弹匣的子弹会最先被射出。在栈中，数据的插入和删除操作都在栈顶进行。
Python 中的栈实现在 Python 里，使用列表（list）就可以轻松模拟栈的行为。例如：
stack = [] # 初始化一个空栈
stack.append(1) # 将元素1压入栈顶
stack.append(2) # 将元素2压入栈顶
top_element = stack.pop() # 弹出栈顶元素，此时top_element为2
print(stack) # 输出: [1]应用场景
栈在很多场景中都大显身手，比如表达式求值。以计算后缀表达式 “3 4 2 *” 为例，我们从左到右扫描表达式，遇到数字就压入栈，遇到运算符就从栈中弹出相应数量的操作数进行运算，再将结果压回栈中。通过栈的这种特性，能高效地完成表达式的计算。此外，在处理括号匹配问题时，栈也发挥着关键作用。当遇到左括号时将其压入栈，遇到右括号时从栈中弹出对应的左括号进行匹配，以此判断括号是否成对出现。
队列（Queue）先进先出的 “排队” 结构队列与栈相反，是一种先进先出（FIFO，First In First Out）的数据结构，就像人们排队买票，先到的人先买到票离开队列。在队列中，元素从队尾入队，从队头出队。
Python 中的队列实现Python 的collections模块提供了deque（双端队列），可以方便地实现队列。示例如下：
from collections import deque
queue = deque() # 初始化一个空队列
queue.append(1) # 将元素1加入队尾
queue.append(2) # 将元素2加入队尾
front_element = queue.popleft() # 从队头移除并返回元素，此时front_element为1
print(queue) # 输出: deque([2])应用场景
队列在广度优先搜索（BFS）算法中不可或缺。在对图或树进行广度优先遍历的时候，需要使用队列来存储待访问的节点。从起始节点开始，将其邻居节点依次加入队列，然后按照先进先出的顺序访问队列中的节点，从而实现一层一层地遍历。在任务调度系统中，队列也常被用来存储等待执行的任务，确保任务按照提交的顺序依次执行。
链表（Linked List）灵活的链式存储链表是一种线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针（在双向链表中还包含指向前一个节点的指针）。与数组不同，链表的节点在内存中不一定是连续存储的，这使得链表在插入和删除操作上具有很高的灵活性。
Python 中的链表实现下面是一个简单的单向链表实现示例：
class Listnode:
def __init__(self, data=0, next=None):
self.data = data
self.next = next
#创建链表 1 -> 2 -> 3
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node1.next = node2
node2.next = node3应用场景
链表在需要频繁进行插入和删除操作的场景中表现出色。例如，在实现文本编辑器的撤销功能时，每一次编辑操作可以被视为一个节点，通过链表将这些操作串联起来。当用户执行撤销操作时，只需从链表中删除对应的节点即可，而不需要像数组那样移动大量元素。在操作系统的内存管理中，链表也用于管理空闲内存块，方便地分配和回收内存。
树（Tree）层次分明的 “家族谱系”树是一种层次数据结构，由节点组成，其中一个节点是根节点，其他节点通过边连接，形成一种类似家族谱系的结构。每个节点可以有零个或多个子节点，除了根节点外，每个节点都有且仅有一个父节点。二叉树是一种特殊的树，每个节点最多有两个子节点，分别称为左子节点和右子节点。
Python 中的树实现以二叉树为例，以下是一个简单的二叉树插入和中序遍历的实现：
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class BinaryTree:
def insert(self, root, key):
if root is None:
return TreeNode(key)
else:
if root.val < key:
root.right = self.insert(root.right, key)
else:
root.left = self.insert(root.left, key)
return root
def inorder(self, root):
if root:
return self.inorder(root.left) [root.val] self.inorder(root.right)
else:
return []
#使用示例
bt = BinaryTree()
root = None
root = bt.insert(root, 5)
root = bt.insert(root, 3)
root = bt.insert(root, 7)
print(bt.inorder(root)) # 输出: [3, 5, 7]应用场景
树在很多领域都有广泛应用。在文件系统中，目录结构就可以用树来表示，根节点是文件系统的根目录，子节点可以是子目录或文件。在搜索算法中，二叉搜索树（BST）能高效地进行查找、插入和删除操作，其平均时间复杂度为 O (log n)，其中 n 是树中节点的数量。决策树算法在机器学习领域用于分类和回归问题，通过对数据特征的层层判断来做出决策。
图（Graph）复杂关系的 “网络地图”图是一种非线性数据结构，由一组顶点（Vertex）和连接这些顶点的边（Edge）组成。图可以用来表示各种复杂的关系，比如社交网络中人与人之间的关系、城市之间的交通网络等。图可以分为有向图（边有方向）和无向图（边没有方向）。
Python 中的图实现在 Python 中，可以使用字典来实现图。例如，以下是一个简单的无向图实现：
class Graph:
def __init__(self):
self.graph = {}
def add_edge(self, u, v):
if u not in self.graph:
self.graph[u] = []
if v not in self.graph:
self.graph[v] = []
self.graph[u].append(v)
self.graph[v].append(u)
def print_graph(self):
for vertex in self.graph:
print(vertex, "->", self.graph[vertex])
#使用示例
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.print_graph() # 输出: 0 -> [1, 2] 1 -> [0, 2] 2 -> [0, 1]应用场景
图在社交网络分析中用于研究用户之间的关系，通过分析图的结构可以发现社区、影响力最大的用户等。在路径规划算法中，如 Dijkstra 算法和 A * 算法，将地图抽象为图，顶点表示地点，边表示地点之间的连接和距离，通过算法计算出从起点到终点的最短路径。在计算机网络中，图也用于描述网络拓扑结构，帮助进行网络故障诊断和优化。
通过对栈、队列、链表、树和图这几种常用数据结构的学习，我们为 Python 编程打下了更坚实的基础。在实际编程中，根据不同的需求选择合适的数据结构，能让程序的性能和效率得到极大提升。
,
