3.1 栈 Stack
基础概念
相关提炼内容见 stack。
栈的基本概念
- 栈的定义
- 栈是只允许在一端进行插入或删除操作的线性表
- 特性：后进先出 Last In First Out, LIFO
- 栈的数学性质：卡特兰数 Catalan Number
| | <-- 栈顶（top)
| |
| ... |
| b |
| a | <-- 栈底（bottom）
+-----+
栈的基本操作
- InitStack(&S)：初始化操作
- DestroyStack(&S)：销毁栈操作 []
- StackEmpty(S)：判定 S 是否为空栈
- StackLength(S)：求栈的长度 cpp::std::stack::size
- GetTop(S, &e)：取栈顶元素 cpp::std::stack::top
- ClearStack(&S)：栈置空操作 cpp::std::stack::empty
- Push(&S, e)：入栈操作（压栈）cpp::std::stack::push
- Pop(&S, &e)：出栈操作（弹栈）
栈的顺序存储结构
- 结点的类型定义
#define MAXSIZE 100
typedef struct {
ElemType data[MAXSIZE];
int top; // 栈顶指针
} SqStack;-
顺序栈的基本运算
- 初始化
- 判栈空
- 入栈
- 出栈
- 读栈顶元素
-
共享栈
-
栈的链式存储结构
结点的类型定义
typedef struct StackNode {
SElemType data;
struct StackNode *next;
} StackNode, *LinkStack;