【栈和队列】是计算机科学中两种基本的数据结构，它们在算法和数据结构中扮演着重要的角色。栈，有时也被称为后进先出（LIFO，Last In First Out）结构，是一种只能在一端进行插入和删除操作的线性表。这种结构的特点决定了最新加入的元素（称为栈顶元素）总是最先被移除。
### 1. 什么是栈
栈的逻辑结构是一对一的线性结构，它包含两个主要的操作：Push（入栈/进栈/压入）和Pop（出栈/退栈/弹出）。Push操作在栈顶添加元素，而Pop操作则移除栈顶的元素。当栈中没有元素时，我们称其为空栈。栈的应用广泛，例如在撤销操作、递归调用、内存管理、表达式求值等场景中都有所体现。
### 2. 栈的存储结构
栈有两种常见的存储结构：顺序栈和链栈。
#### 2.1 顺序栈
顺序栈是用数组来实现的特殊顺序表。栈底位置固定，通常设为数组的一端，而栈顶位置则随着Push和Pop操作动态变化，通过一个top指针来指示。当栈满时（即top等于数组的最大索引减一）会发生上溢，尝试Push新元素会导致错误；反之，当栈空时（top等于-1），尝试Pop元素则会导致下溢。在C语言中，可以使用结构体来定义一个顺序栈，如下：
```c
typedef struct {
SElemType data[MAXSIZE]; // 一维数组表示栈，栈的容量为MAXSIZE
int top; // 指示栈顶元素位置
} SqStack;
```
顺序栈的Push和Pop操作的实现如下：
```c
Status Push(SqStack* S, SElemType e) {
if (S->top == MAXSIZE - 1) // 栈满
return ERROR; // 上溢处理
S->top++; // 栈顶指针上移
S->data[S->top] = e; // 新元素入栈
return OK;
}
Status Pop(SqStack* S, SElemType* e) {
if (S->top == -1) // 栈空
return ERROR; // 返回错误信息
*e = S->data[S->top]; // 栈顶元素出栈
S->top--; // 栈顶指针下移
return OK;
}
```
这里的`SElemType`可以是任何类型，如整型、浮点型或自定义类型。
### 3. 栈的应用
栈在计算机科学中有多种应用，包括但不限于：
- **括号匹配**：检查编程语言中的括号是否匹配，例如在编译器中。
- **表达式求值**：计算逆波兰表示法（后缀表达式）。
- **递归调用**：在函数调用过程中，系统使用栈来保存函数的返回地址和局部变量。
- **内存管理**：在某些高级语言中，分配和释放内存的管理使用了栈的概念。
- **网页浏览的前进/后退功能**：浏览器的前进和后退按钮就是基于栈的实现，每次访问新的页面时，旧页面的URL被Push到栈中，点击后退则Pop栈顶的URL并加载页面。
- **深度优先搜索（DFS）**：在图论和树形结构中，深度优先遍历使用栈来决定下一步探索哪个节点。
### 4. 时间复杂度
对于顺序栈，Push和Pop操作的时间复杂度都是O(1)，因为这些操作都发生在数组的同一端，不涉及元素的移动。栈的初始化、清空和判断空栈的时间复杂度同样为O(1)。栈的长度计算取决于是否预先存储了元素个数，如果预先存储，则时间复杂度为O(1)；如果没有，则需要遍历数组，时间复杂度为O(n)。
栈是一种简单但强大的数据结构，它在很多算法和实际问题中都有广泛应用。了解并熟练掌握栈的原理和操作，对于理解和解决计算机科学中的问题至关重要。
