1. 数据结构的概念

数据结构大致分为以下几类：

• 线性结构：数组、链表、栈、队列等。

• 非线性结构：树、二叉树、堆、图等。

• 散列：哈希表。

• 索引：B树、B+树等。

2. 常见数据结构

2.1 栈

栈（Stack）是一种遵循**后进先出（LIFO）**原则的线性数据结构。栈的操作主要包括：

• push(element)：将元素压入栈顶。

• pop()：弹出栈顶元素。

• peek()：返回栈顶元素但不移除。

• isEmpty()：判断栈是否为空。

• clear()：清空栈。

• size()：返回栈中元素的数量。

2.1.1 入栈

入栈操作将新元素添加到栈顶。

2.1.2 出栈

出栈操作移除栈顶元素并返回该元素。

2.1.3 代码实现

class Stack:
    def __init__(self, size):
        self.items = []
        self.size = size

    def isFull(self):
        return len(self.items) == self.size

    def push(self, element):
        if self.isFull():
            raise Exception('stack is full')
        self.items.append(element)

    def pop(self):
        if self.isEmpty():
            raise Exception('stack is empty')
        return self.items.pop()

    def peek(self):
        if self.isEmpty():
            raise Exception('stack is empty')
        return self.items[-1]

    def isEmpty(self):
        return len(self.items) == 0

    def clear(self):
        self.items.clear()

2.2 链表

链表是由一系列节点组成的线性数据结构，每个节点包含数据和指向下一个节点的指针。

2.2.1 链表的优缺点

优点：

1. 动态内存分配，内存利用率高。

2. 插入和删除操作简单。

缺点：

1. 无法通过索引直接访问元素。

2. 指针操作复杂，容易出错。

2.2.2 单向链表

单向链表的操作包括插入、遍历和删除。

2.2.2.1 插入

• 尾部插入：将新节点插入到链表末尾。

• 头部插入：将新节点插入到链表头部。

2.2.2.2 遍历

从头节点开始，依次访问每个节点。

2.2.2.3 删除

删除指定节点。

2.2.2.4 代码实现

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = Node()

    def append(self, data):
        new_node = Node(data)
        if self.head.next is None:
            self.head.next = new_node
        else:
            node = self.head.next
            while node.next is not None:
                node = node.next
            node.next = new_node

    def prepend(self, data):
        new_node = Node(data)
        new_node.next = self.head.next
        self.head.next = new_node

    def remove(self, data):
        if self.head.next is None:
            raise Exception('Linked List is empty')
        node = self.head
        while node.next.data != data:
            node = node.next
        node.next = node.next.next

    def display(self):
        node = self.head.next
        while node is not None:
            print(node.data)
            node = node.next

2.3 队列

队列（Queue）是一种遵循**先进先出（FIFO）**原则的线性数据结构。

2.3.1 普通队列

Python中的queue.Queue类实现了线程安全的FIFO队列。

import queue

q = queue.Queue()
q.put(1)
q.put(3)
q.put(2)

print(q.get())  # 输出: 1
print(q.get())  # 输出: 3
print(q.get())  # 输出: 2

2.3.2 双端队列

双端队列（Deque）允许在两端进行插入和删除操作。

from collections import deque

q = deque()
q.append(1)
q.append(2)
q.appendleft(3)
q.appendleft(4)

print(q.pop())  # 输出: 2
print(q.popleft())  # 输出: 4

2.3.3 优先队列

优先队列中的元素按优先级排序，优先级最高的元素最先出队。

import queue

q = queue.PriorityQueue()
q.put((1, 'item1'))
q.put((3, 'item3'))
q.put((2, 'item2'))

print(q.get())  # 输出: (1, 'item1')
print(q.get())  # 输出: (2, 'item2')
print(q.get())  # 输出: (3, 'item3')

2.4 树

树是一种非线性数据结构，常用于表示层次关系。

2.4.1 概念和术语

• 根节点：树的顶层节点。

• 子节点：节点的直接下级节点。

• 叶子节点：没有子节点的节点。

• 深度：树中节点的最大层次。

2.4.2 二叉树

二叉树是每个节点最多有两个子节点的树结构。

2.4.2.1 二叉树的存储

二叉树通常使用链表存储，每个节点包含数据、左子节点和右子节点的引用。

2.4.2.2 二叉树遍历

• 前序遍历：根节点 -> 左子树 -> 右子树。

• 中序遍历：左子树 -> 根节点 -> 右子树。

• 后序遍历：左子树 -> 右子树 -> 根节点。

2.4.3 二叉查找树

二叉查找树（BST）是一种特殊的二叉树，满足以下性质：

1. 左子树的所有节点值小于根节点。

2. 右子树的所有节点值大于根节点。

2.4.3.1 插入节点

class TreeNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

class BinarySearchTree:
    def __init__(self):
        self.root = None

    def insert(self, key):
        if self.root is None:
            self.root = TreeNode(key)
        else:
            self._insert(self.root, key)

    def _insert(self, node, key):
        if key < node.key:
            if node.left is None:
                node.left = TreeNode(key)
            else:
                self._insert(node.left, key)
        elif key > node.key:
            if node.right is None:
                node.right = TreeNode(key)
            else:
                self._insert(node.right, key)

2.4.3.2 删除节点

删除操作分为三种情况：

1. 叶子节点：直接删除。

2. 只有一个子节点：用子节点替换。

3. 有两个子节点：找到右子树的最小节点替换。

def delete(self, key):
    self.root = self._delete(self.root, key)

def _delete(self, node, key):
    if node is None:
        return node

    if key < node.key:
        node.left = self._delete(node.left, key)
    elif key > node.key:
        node.right = self._delete(node.right, key)
    else:
        if node.left is None:
            return node.right
        elif node.right is None:
            return node.left
        temp = self._min_value_node(node.right)
        node.key = temp.key
        node.right = self._delete(node.right, temp.key)
    return node

2.4.3.3 中序遍历

def inorder_traversal(self):
    result = []
    self._inorder_traversal(self.root, result)
    return result

def _inorder_traversal(self, node, result):
    if node:
        self._inorder_traversal(node.left, result)
        result.append(node.key)
        self._inorder_traversal(node.right, result)