3.1 栈 Stack

[!info] 基础概念 相关提炼内容见 stack。

栈的基本概念

• 栈的定义
  • 栈是只允许在一端进行插入或删除操作的线性表
  • 特性：后进先出 Last In First Out, LIFO
  • 栈的数学性质：卡特兰数 Catalan Number
    • $\frac 1{n+1}C^n_{2n}$

|     |  <-- 栈顶（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;

参考资料

• cpp::std::stack::size #todo
• cpp::std::stack::top #todo
• cpp::std::stack::empty #todo
• cpp::std::stack::push #todo