队列（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 = size
self.table = [[] for _ in range(size)]
def _hash(self, key):
return hash(key) % self.size
def insert(self, key, value):
idx = self._hash(key)
for item in self.table[idx]:
if item[0] == key:
item[1] = value # Update existing key
return
self.table[idx].append([key, value]) # Add new key-value pair
def 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 = val
self.left = None
self.right = None
class 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
应用场景
- 哈希表：快速查找（如字典、缓存）。
- 树：有序数据存储（如数据库索引、文件系统）。
作业：
1.牛客网刷题
