栈的链式存储结构与顺序存储结构对比分析

# 2.1 链式存储结构的原理和特点

### 2.1.1 结点的组织方式

链式存储结构中的栈由结点组成，每个结点包含数据域和指针域。数据域存储实际数据，指针域指向下一个结点。栈顶元素的指针域为空，表示栈的末尾。

### 2.1.2 存储空间的分配和回收

链式存储结构采用动态分配机制，根据需要分配和回收存储空间。当入栈时，系统分配一个新的结点，并将数据存储在数据域中；当出栈时，系统释放出栈结点的存储空间。这种机制可以有效利用存储空间，避免内存浪费。

# 2. 链式存储结构

### 2.1 链式存储结构的原理和特点

#### 2.1.1 结点的组织方式

链式存储结构中，栈中的元素存储在称为结点的动态分配的内存块中。每个结点包含两个字段：

- **数据域：**存储栈中的元素值。
- **指针域：**指向下一个结点的地址，或者指向空地址（表示栈顶或栈底）。

结点通过指针域连接成一个线性链表，形成栈的数据结构。

#### 2.1.2 存储空间的分配和回收

链式存储结构使用动态分配的内存来存储结点。当需要创建一个新的结点时，系统会从堆中分配一块内存并将其分配给结点。当结点不再需要时，将其指针域设置为 `NULL`，系统会自动回收该内存块。

### 2.2 链式栈的实现

#### 2.2.1 基本操作：入栈和出栈

**入栈（Push）：**

1. 创建一个新的结点，并将元素值存储在数据域中。
2. 将新结点的指针域指向当前栈顶结点。
3. 更新栈顶指针指向新结点。

**出栈（Pop）：**

1. 获取当前栈顶结点。
2. 将栈顶指针指向下一个结点。
3. 释放当前栈顶结点的内存。

#### 2.2.2 栈的初始化和销毁

**初始化：**

1. 创建一个哨兵结点（一个不包含数据的特殊结点），并将栈顶指针指向该结点。
2. 哨兵结点的指针域指向 `NULL`。

**销毁：**

1. 遍历栈中的所有结点，释放每个结点的内存。
2. 将栈顶指针设置为 `NULL`。

### 2.3 链式栈的优缺点分析

#### 2.3.1 优点：

- **动态分配：**链式存储结构使用动态分配的内存，可以根据需要灵活地分配和回收结点。
- **空间利用率高：**由于结点是动态分配的，因此不会浪费内存空间。

#### 2.3.2 缺点：

- **访问效率低：**访问栈中的元素需要遍历指针，因此访问效率较低。
- **指针管理复杂：**链式存储结构需要维护指针域，这可能会导致指针管理复杂度较高。

**代码块：**

// 创建一个链式栈
struct Node {
    int data;
    Node* next;
};

Node* top = nullptr;  // 栈顶指针

// 入栈
voi