栈和队列

文章目录

• 栈和队列
• 栈（Stack）
• • 栈的顺序存储结构（SqStack——Sequence Stack）
  • • 表示方法
    • 基本操作
    • • 初始化 `InitStack(SqStack &S)`
      • 判栈空 `StackEmpty(SqStack S)`
      • 进栈 `Push(SqStack &S, ElemType x)`
      • 出栈 `Pop(SqStack &S, ElemType &x)`
      • 读栈顶元素 `GetTop(SqStack &S, ElemType &x)`
    • 共享栈
  • 栈的链式存储结构（LiStack——LinkStack）
  • • 表示方法
    • 基本操作
    • • 初始化：`InitStack(LiStack &S)`
      • 判栈空：`StackEmpty(LiStack S)`
      • 进栈：`Push(LiStack &S, Linknode *p)`
      • 出栈：`Pop(LiStack &S, ElemType e)`
      • 读栈顶元素：`GetTop(LiStack S)`
  • 栈的应用
  • • 括号匹配
    • • 主要流程如图所示
      • 程序实现
    • 表达式求值
    • • 后缀型：
      • 中缀表达式转后缀表达式（手算）
      • 💯中缀表达式转后缀表达式（机算）
      • 后缀表达式转中缀表达式计算（手算）
      • 后缀表达式转中缀表达式（机算）
      • 💯计算机计算中缀表达式（非常重要的算法，无处不在）
      • 前缀型：
      • 中缀表达式转前缀表达式（手算）
      • 前缀表达式转中缀表达式计算（手算）
      • 前缀表达式转中缀表达式计算（机算）
    • 迷宫求解
    • 进制转换
• 队列（Queue）
• • 队列的顺序存储结构（SqQueue——Sequence Queue）
  • • 表示方法
    • 循环队列基本操作
    • • 初始化： `InitQueue(SqQueue &Q)`
      • 判队空： `StackEmpty(SqQueue Q)`
      • 入队： `EnQueue(SqQueue &Q, Elemtype x)` （使用方式 1 判断队满情况下）
      • 出队： `DeQueue(SqQueue &Q, ElemType &x)`
      • 读队头元素： `GetHead(SqQueue &Q, ElemType &x)`
    • 队尾指针指向队尾元素情况
    • • 初始化： `InitQueue(SqQueue &Q)`
      • 判队空： `StackEmpty(SqQueue Q)`
      • 入队： `EnQueue(SqQueue &Q, Elemtype x)` （使用方式 1 判断队满情况下）
      • 出队： `DeQueue(SqQueue &Q, ElemType &x)`
      • 读队头元素： `GetHead(SqQueue &Q, ElemType &x)`
  • 队列的链式存储结构（LinkQueue）
  • • 表示方法
    • 基本操作（带头结点更加方便）
    • • 初始化： `InitQueue(LinkQueue &Q)`
      • 判队空： `StackEmpty(LinkQueue Q)`
      • 入队： `EnQueue(LinkQueue &Q, ElemType *x)`
      • 出队： `DeQueue(LinkQueue &Q, ElemType &x)` ? 队尾元素出队列需要先将 rear 指向 front，否则丢失
      • 读队头元素： `GetHead(LinkQueue &Q, LinkNode *x)`
  • 队列的应用
  • • 树的层次遍历
    • 图的广度优先遍历
    • 缓冲区
    • CPU 资源分配、竞争
• Conclusion