软考知识点——数组、链表、队列、栈的定义、存储和基本运算

以下是数组、链表、队列和栈的详细定义、存储方式及基本运算的总结，涵盖核心概念与操作：

一、数组（Array）

1. 定义

• 连续内存存储的线性数据结构，通过**索引（下标）**直接访问元素。
• 特点：固定大小（静态数组）或动态扩容（动态数组，如C++的vector、Python的list）。

2. 存储方式

• 顺序存储：元素在内存中连续排列，地址计算公式：
  地址 = 基地址 + 索引 × 元素大小
  （例如：int arr[5] 中，arr[2] 的地址 = arr + 2 × sizeof(int)）。

3. 基本运算

• 访问：O(1) 时间复杂度（直接通过索引计算地址）。
• 插入/删除：
  • 尾部操作：O(1)（动态数组可能触发扩容，均摊O(1)）。
  • 中间或头部操作：O(n)（需移动后续元素）。
• 查找：
  • 按值查找：O(n)（无序数组）。
  • 按索引查找：O(1)。

二、链表（Linked List）

1. 定义

• 非连续内存存储的线性结构，通过指针连接节点（每个节点包含数据域和指针域）。
• 分类：
  • 单链表：每个节点指向下一个节点。
  • 双向链表：节点包含前驱和后继指针。
  • 循环链表：尾节点指向头节点。

2. 存储方式

• 离散存储：节点通过指针/引用动态分配内存，无需连续空间。

3. 基本运算

• 访问：O(n)（需从头节点遍历）。
• 插入/删除：
  • 已知节点位置：O(1)（修改指针指向）。
  • 查找后插入/删除：O(n)（需先遍历定位）。
• 查找：O(n)（按值遍历）。

三、队列（Queue）

1. 定义

• 先进先出（FIFO）的线性结构，允许在队尾插入，队头删除。
• 分类：
  • 顺序队列：基于数组实现，需处理假溢出（循环队列优化）。
  • 链式队列：基于链表实现，无容量限制。

2. 存储方式

• 数组实现：需维护front和rear指针，循环队列通过模运算复用空间。
• 链表实现：头节点为队头，尾节点为队尾（插入需O(1)时间）。

3. 基本运算

• 入队（Enqueue）：O(1)（链表尾插或循环队列尾指针移动）。
• 出队（Dequeue）：O(1)（链表头删或循环队列头指针移动）。
• 访问队头/队尾：O(1)。
• 判空：O(1)（检查front == rear）。

四、栈（Stack）

1. 定义

• 后进先出（LIFO）的线性结构，仅允许在栈顶插入和删除。
• 应用：函数调用栈、表达式求值、括号匹配等。

2. 存储方式

• 数组实现：维护top指针指向栈顶元素。
• 链表实现：头节点作为栈顶（插入/删除均为O(1)）。

3. 基本运算

• 压栈（Push）：O(1)（栈顶指针上移或链表头插）。
• 弹栈（Pop）：O(1)（栈顶指针下移或链表头删）。
• 访问栈顶：O(1)。
• 判空：O(1)（检查top == -1或链表头是否为null）。

五、对比总结

六、代码示例（Python）

1. 数组

arr = [1, 2, 3]
arr.append(4)  # 插入尾部 O(1)
arr.insert(1, 5)  # 插入中间 O(n)
print(arr[2])  # 访问 O(1)

2. 链表

class ListNode:
    def __init__(self, val=0):
        self.val = val
        self.next = None

# 插入节点
head = ListNode(1)
head.next = ListNode(2)
new_node = ListNode(3)
new_node.next = head.next  # 插入到头部后
head.next = new_node

3. 队列（使用collections.deque）

from collections import deque
q = deque()
q.append(1)  # 入队
q.append(2)
print(q.popleft())  # 出队 1

4. 栈

stack = []
stack.append(1)  # 压栈
stack.append(2)
print(stack.pop())  # 弹栈 2

通过理解这些数据结构的定义、存储方式和操作，可以灵活选择适合场景的工具（如数组用于快速访问，链表用于动态插入，队列/栈管理任务顺序）。