### 数据结构之——栈
#### 一、栈的基本概念
栈是一种特殊的线性表，它只允许在一端进行插入和删除操作。这一端被称为栈顶（top），另一端则称为栈底（bottom）。栈遵循“先进后出”（Last In First Out, LIFO）的原则，即最后进入栈的元素最先被移除。
#### 二、栈的应用场景
栈在计算机科学中有广泛的应用：
1. **函数调用与返回**：每次函数调用时，系统会将调用者的信息压入栈中；函数执行完毕后，再从栈中弹出这些信息。
2. **表达式求值**：如逆波兰表示法的计算过程。
3. **括号匹配**：用于检查代码中的括号是否正确配对。
4. **回溯算法**：在搜索问题的解空间树时，可以通过栈来保存路径上的选择状态。
5. **页面浏览**：浏览器的历史记录通常采用栈结构实现前进和后退功能。
#### 三、栈的存储结构
栈可以通过两种方式实现存储：**静态数组**和**动态链表**。
1. **静态栈**：使用固定大小的数组来实现。优点是简单易实现，但缺点是无法扩展，一旦栈满就无法继续入栈。
```c
typedef struct {
int data[100]; // 假设栈的最大容量为100
int top; // 栈顶指针
} STACK;
```
2. **动态栈**：使用链表实现，可以动态地调整栈的空间。当栈满时可以通过分配更多内存来扩展。
```c
typedef struct Node {
int data;
struct Node *pNext;
} NODE, *PNODE;
typedef struct stack {
PNODE pTop;
PNODE pBottom;
} STACK, *PSTACK;
```
#### 四、栈的基本操作
栈的主要操作包括：
1. **入栈**（Push）
2. **出栈**（Pop）
3. **获取栈顶元素**（Top）
4. **判断栈是否为空**（IsEmpty）
下面详细介绍动态栈的具体实现：
##### 入栈（Push）
入栈操作是将一个元素添加到栈顶。实现代码如下：
```c
void push(PSTACK ps, int val) {
PNODE pNew = (PNODE)malloc(sizeof(NODE));
if (NULL == pNew) { // 检查内存分配是否成功
printf("动态内存分配失败!\n");
exit(-1);
}
pNew->data = val;
pNew->pNext = ps->pTop;
ps->pTop = pNew;
}
```
##### 出栈（Pop）
出栈操作是从栈顶移除一个元素，并返回该元素的值。实现代码如下：
```c
bool pop(PSTACK ps, int *pval) {
if (is_empty(ps)) { // 检查栈是否为空
return false;
}
PNODE p = ps->pTop;
*pval = p->data;
ps->pTop = p->pNext;
free(p);
p = NULL;
return true;
}
```
##### 获取栈顶元素（Top）
获取栈顶元素是指不删除栈顶元素的情况下查看其值。
```c
int top(PSTACK ps) {
if (is_empty(ps)) {
printf("栈为空\n");
return -1; // 或其他错误标识
}
return ps->pTop->data;
}
```
##### 判断栈是否为空（IsEmpty）
判断栈是否为空的操作非常简单。
```c
bool is_empty(PSTACK ps) {
return ps->pTop == ps->pBottom;
}
```
#### 五、示例程序分析
给定的示例程序中演示了如何使用动态栈。程序首先定义了栈的结构体和节点结构体，并实现了初始化、入栈、出栈、遍历等基本操作。
1. **初始化**：创建空栈。
2. **入栈**：向栈中添加元素。
3. **遍历**：打印栈中的所有元素。
4. **出栈**：移除并返回栈顶元素。
5. **清空栈**：释放栈中所有元素占用的内存，将栈清空。
示例程序展示了如何使用这些基本操作来实现栈的功能，以及如何管理内存。通过这段代码的学习，可以加深对栈这一数据结构的理解。
