栈是一种遵循后进先出（LIFO）原则的线性数据结构，只允许在栈顶进行插入和删除操作。

我们可以将栈类比为桌面上的一摞盘子，规定每次只能移动一个盘子，那么想取出底部的盘子，则需要先将上面的盘子依次移走。我们将盘子替换为各种类型的元素（如整数、字符、对象等），就得到了栈这种数据结构。

核心特性

• 受限访问：只能访问栈顶元素，无法直接访问中间或底部元素
• 动态大小：栈的大小随着元素入栈出栈而动态变化
• 操作单一：所有操作都在栈顶进行，包括插入（入栈）和删除（出栈）

应用场景

• 函数调用栈管理
• 表达式求值和括号匹配
• 浏览器前进后退功能
• 撤销操作机制

---

栈可以使用数组和链表来实现

使用数组实现栈

数组实现栈利用连续内存空间，通过栈顶指针来管理栈的操作。

构造数组栈

设计原理

• 固定容量：预先分配固定大小的数组空间
• 栈顶指针：使用 top 变量指示栈顶位置，初始值为 -1 表示空栈
• 边界控制：通过栈顶指针判断栈空和栈满条件

关键理解点

• 索引选择：top = -1 表示空栈，便于后续的递增操作
• 内存预分配：数组大小固定，需要合理估计最大容量
• 简单高效：数组实现具有缓存友好性和访问速度快的特点

CommonUseA.cpp

const int MAX_SIZE = 101;
int A[MAX_SIZE]{};
int top = -1;

入栈操作

函数参数说明

• x：要入栈的元素值
• 无返回值，直接修改全局数组和栈顶指针

操作原理

1. 栈满检查：检查栈顶指针是否达到数组最大索引
2. 栈顶移动：先递增栈顶指针，再存入元素
3. 元素存储：将新元素存入栈顶位置

关键理解点

• 先增后存：使用 ++top 先移动指针再存储，避免索引错误
• 溢出处理：必须检查栈满条件，防止数组越界
• 原子操作：入栈操作应该是原子的，保证数据一致性

PushUseA.cpp

void PushUseA(int x) {
	using std::cout;
	if (top == MAX_SIZE - 1) {
		cout << "错误，栈溢出";
		return;
	}
	A[++top] = x;
}

出栈操作

操作原理

1. 栈空检查：检查栈顶指针是否为 -1（空栈）
2. 栈顶移动：递减栈顶指针，逻辑上移除栈顶元素
3. 内存回收：数组实现中实际数据仍存在，但无法访问

关键理解点

• 逻辑删除：出栈只是移动指针，并不实际清除数组数据
• 下溢防护：必须检查栈空条件，避免无效操作
• 指针管理：通过指针移动实现元素的逻辑移除

PopUseA.cpp

void PopUseA() {
	using std::cout;
	if (top == -1) {
		cout << "错误，链表为空";
		return;
	}
	top--;
}

访问栈顶元素

操作原理

• 直接访问：通过栈顶指针索引直接返回栈顶元素
• 无副作用：访问操作不改变栈的状态

关键理解点

• 只读操作：访问栈顶不会影响栈的结构
• 空栈处理：在实际应用中应考虑空栈的返回值策略

TopUseA.cpp

int TopUseA() {
	return A[top];
}

打印栈元素

操作原理

• 顺序遍历：从栈底到栈顶遍历数组元素
• 状态展示：显示栈中所有元素的当前状态

关键理解点

• 遍历范围：从索引 0 到 top，包含所有有效元素
• 调试工具：主要用于调试和可视化栈的状态

PrintUseA.cpp

void PrintUseA() {
	using std::cout;
	cout << "stack: ";
	for (int i = 0; i <= top; i++) {
		cout << A[i] << " ";
	}
	cout << "\n";
}

使用链表实现栈

链表实现栈利用动态内存分配，可以灵活适应栈大小的变化。

构造栈节点

设计原理

• 节点结构：每个节点包含数据域和指向下一节点的指针
• 动态内存：节点在堆中动态分配，无固定大小限制
• 头指针：使用头指针指向栈顶节点

关键理解点

• 内存灵活性：链表栈可以动态增长，不受固定容量限制
• 额外开销：每个节点需要额外的指针空间
• 头部操作：选择链表头部作为栈顶以保证 O(1) 时间复杂度

构造栈节点

CommonUseL.cpp

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

入栈操作（链表头部插入节点）

函数参数说明

• top：当前栈顶节点指针
• x：要入栈的元素值
• 返回值：新的栈顶节点指针

操作原理

1. 创建节点：在堆中分配新节点内存
2. 设置数据：将元素值存入新节点的数据域
3. 连接节点：新节点的 next 指针指向原栈顶
4. 更新栈顶：栈顶指针指向新节点

关键理解点

• 头插法：在链表头部插入保证 O(1) 时间复杂度
• 指针更新：必须返回新的栈顶指针，因为栈顶已改变
• 内存分配：每次入栈都需要动态分配内存

PushUseL.cpp

Node* PushUseL(Node* top, int x) {
	Node* temp = new Node();
	temp->data = x;
	temp->next = top;
	top = temp;
	return top;
}

出栈操作（链表头部删除节点）

函数参数说明

• top：当前栈顶节点指针
• 返回值：新的栈顶节点指针

操作原理

1. 栈空检查：检查栈顶指针是否为 NULL
2. 临时保存：保存原栈顶节点指针用于内存释放
3. 更新栈顶：栈顶指针指向下一个节点
4. 释放内存：删除原栈顶节点，释放内存

关键理解点

• 内存管理：必须手动释放出栈节点的内存
• 边界处理：空栈出栈应有适当的错误处理
• 指针安全：确保在释放内存前更新栈顶指针

PopUseL.cpp

Node* PopUseL(Node* top) {
	Node* temp;
	if (top == NULL) {
		return;
	}
	temp = top;
	top = top->next;
	delete temp;
	return top;
}

打印栈元素

函数参数说明

• top：当前栈顶节点指针

操作原理

1. 临时指针：使用临时指针遍历栈，避免修改原栈顶
2. 顺序遍历：从栈顶到栈底遍历所有节点
3. 数据输出：输出每个节点的数据值

关键理解点

• 遍历保护：使用临时指针避免破坏栈结构
• 顺序显示：按入栈顺序的逆序显示（栈顶到栈底）
• 调试功能：主要用于验证栈的正确性

PrintUseL.cpp

void PrintUseL(Node* top) {
	using std::cout;
	Node* temp = top;
	while (temp != NULL) {
		cout << temp->data << " ";
		temp = temp->next;
	}
	cout << "\n";
}

访问栈顶元素

函数参数说明

• top：当前栈顶节点指针
• 返回值：栈顶元素值或错误标识

操作原理

• 直接访问：通过栈顶指针访问节点的数据域
• 空栈处理：对空栈访问返回特定值（如 -1）表示错误

关键理解点

• 只读操作：访问操作不影响栈结构
• 错误处理：应有明确的空栈处理策略
• 数据安全：确保在访问前检查指针有效性

TopUseL.cpp

int TopUseL(Node* top) {
    if (top != NULL) {
        return top->data;
    }
    return -1; // 返回-1表示栈为空
}

两种实现方式对比

特性	数组实现	链表实现
内存分配	静态预分配	动态分配
最大容量	固定	理论上无限
内存开销	较小	每个节点有指针开销
访问速度	较快（缓存友好）	相对较慢
实现复杂度	简单	较复杂
适用场景	大小可预估的场景	大小变化大的场景