当前位置：首页 > news >正文

嵌入式开发学习———Linux环境下数据结构学习（四）

news 2025/7/29 12:08:32

队列（Queue）

队列是一种先进先出（FIFO）的数据结构，元素从一端（队尾）添加，从另一端（队首）移除。
常见操作包括入队（enqueue）和出队（dequeue）。

from collections import deque
queue = deque()
queue.append(1)  # 入队
queue.append(2)
queue.popleft()  # 出队，返回1

栈（Stack）

栈是一种后进先出（LIFO）的数据结构，元素只能从同一端（栈顶）插入和删除。
常见操作包括压栈（push）和弹栈（pop）。

stack = []
stack.append(1)  # 压栈
stack.append(2)
stack.pop()      # 弹栈，返回2

哈希表

哈希表通过键值对存储数据，利用哈希函数将键映射到固定大小的数组索引。理想情况下，插入、删除和查找操作的时间复杂度为O(1)，但哈希冲突可能影响性能。

解决冲突的方法

链地址法：每个数组元素指向链表，冲突元素追加到链表末尾。
开放寻址法：冲突时探测下一个空闲位置（如线性探测、二次探测）。

示例代码（链地址法）

class HashTable:def __init__(self, size):self.size = sizeself.table = [[] for _ in range(size)]def _hash(self, key):return hash(key) % self.sizedef insert(self, key, value):idx = self._hash(key)for item in self.table[idx]:if item[0] == key:item[1] = value  # Update existing keyreturnself.table[idx].append([key, value])  # Add new key-value pairdef get(self, key):idx = self._hash(key)for item in self.table[idx]:if item[0] == key:return item[1]return None

树

树是分层数据结构，由节点（根、内部、叶）和边组成，常见类型包括二叉树、二叉搜索树（BST）、AVL树等。

核心特性

二叉树：每个节点最多两个子节点（左、右）。
BST：左子树所有节点值小于根，右子树所有节点值大于根。
平衡树（如AVL）：通过旋转保持高度平衡，确保操作时间复杂度为O(log n)。

示例代码（BST插入）

class TreeNode:def __init__(self, val):self.val = valself.left = Noneself.right = Noneclass BST:def insert(self, root, val):if not root:return TreeNode(val)if val < root.val:root.left = self.insert(root.left, val)else:root.right = self.insert(root.right, val)return root

应用场景