数据结构介绍（一）

1. 数组：

数组是一种线性数据结构，用于存储具有相同数据类型的元素。数组可以通过索引访问元素，索引从 0 开始计数。

特点：

• 固定大小：数组一旦创建，大小通常固定。
• 连续存储：数组的元素在内存中是连续存储的，因此可以通过索引高效访问。

Python 示例：

# 创建一个整数数组
integer_array = [1, 2, 3, 4, 5]

# 访问数组元素
print(integer_array[0])  # 输出：1
print(integer_array[2])  # 输出：3

2. 链表：

链表是一种动态数据结构，它由一系列节点组成，每个节点存储数据和指向下一个节点的指针。

特点：

• 动态大小：链表可以动态添加或删除节点，大小不固定。
• 随机访问较慢：访问元素需要从头节点开始遍历，时间复杂度较高。

Python 示例：

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

# 创建一个链表
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)

# 遍历链表
current = head
while current:
    print(current.data)
    current = current.next

3. 栈：

栈是一种后进先出（LIFO）的数据结构，类似于一堆叠盘子。元素只能从栈顶添加和移除。

特点：

• 后进先出：最后添加的元素最先被移除。
• 常用于递归、表达式求值等场景。

Python 示例：

stack = []
stack.append(1)   # 入栈
stack.append(2)
stack.append(3)

print(stack.pop())  # 出栈并输出：3
print(stack.pop())  # 出栈并输出：2

4. 队列：

队列是一种先进先出（FIFO）的数据结构，类似于排队等候。

特点：

• 先进先出：最早添加的元素最先被移除。
• 常用于任务调度、广度优先搜索等场景。

Python 示例：

from collections import deque

queue = deque()
queue.append(1)   # 入队
queue.append(2)
queue.append(3)

print(queue.popleft())  # 出队并输出：1
print(queue.popleft())  # 出队并输出：2

5. 二叉树：

二叉树是一种层次结构，每个节点最多有两个子节点：左子节点和右子节点。

特点：

• 树结构：具有层次性，每个节点可以有零到两个子节点。
• 常用于搜索、排序、计算表达式等场景。

Python 示例：

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

# 创建一个二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)