数据结构（一）：基础数据结构

数组（Array）

连续内存空间存储的线性结构，支持 O(1) 随机访问。

int arr[5] = {1, 2, 3, 4, 5};
printf("%d\n", arr[2]);  // 3（O(1) 访问）

• 优点：随机访问快
• 缺点：插入/删除慢（O(n)）

链表（Linked List）

节点通过指针连接，非连续存储。

struct Node {
    int data;
    struct Node* next;
};

• 优点：插入/删除快（O(1)）
• 缺点：不支持随机访问（O(n)）

栈（Stack）

后进先出（LIFO）。

// 数组模拟栈
int stack[100], top = -1;
stack[++top] = 1;     // push
int val = stack[top--]; // pop

队列（Queue）

先进先出（FIFO）。

// 数组模拟队列
int queue[100], front = 0, rear = 0;
queue[rear++] = 1;    // enqueue
int val = queue[front++]; // dequeue

各结构时间复杂度对比

操作	数组	链表	栈	队列
访问	O(1)	O(n)	O(n)	O(n)
插入/删除头部	O(n)	O(1)	—	—
插入/删除尾部	O(1)	O(n)	O(1)	—
push/pop	—	—	O(1)	O(1)