栈和队列

这是一篇关于栈和队列的思维导图，包括栈和队列的定义、基本操作、存储结构、特点、案例分析与实现等内容。

栈和队列

• 定义
  • 栈是限定仅在表尾进行插入和删除操作的线性表
• 重要术语
  • 栈顶
    • 表尾端有其特殊含义，可以插入和删除
  • 栈底
    • 表头端，固定的不可以插入和删除
  • 空栈
    • 不含任何元素的空表
• 基本操作
  • InitStack(&S),初始化栈
    • 构造一个空栈
  • DestroyStack(&s),销毁栈
    • 销毁并释放S所占的内存
  • ClearStack(&S),
    • 将S清为空栈
  • StackEmpty(S）
    • 若栈S为空栈，则返回true,否则返回false
  • StackLength(S)
    • 返回S的元素个数，即栈的长度
  • GetTop(S),栈S存在且非空
    • 返回S的栈顶元素，不修改栈顶指针
  • Push(&S，e)
    • 插入元素e为新的栈顶元素
  • Pop(&S,&e),栈S以存在且非空
    • 删除S的栈顶元素，并用e为新的栈顶元素
  • StackTraverse(S)
    • 从栈底到栈顶依次对S的每个数据元素进行过访问
• 存储结构
  • 顺序存储
    • 采用顺序存储的栈叫做顺序栈
      • 利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素
    • 操作
      • 顺序栈的初始化
      • 入栈
      • 出栈
      • 取栈顶元素
  • 链式存储
    • 采用链式存储的栈称为链栈，通常用单链来表示
    • 优点：
      • 便于多个栈共享存储空间和提高其效率
      • 不存在栈满上溢的情况
      • 便于结点的插入和删除
    • 操作
      • 初始化
      • 链栈的入栈
      • 出栈
      • 取栈顶元素
• 特点
  • 后进先出
• 定义
  • 与栈不同的是删除实在表的头部进行
• 基本操作
  • InitQueue(&Q)
    • 构造一个空队列Q
  • DestroyQueue(&Q)
    • 销毁Q队列
  • ClearQueue(&Q)
    • 将Q清为空队列
  • QueueEmpty(Q)
    • 若Q为空队列，则返回true,否则返回false
  • QueueLength(Q)
    • 返回Q元素的个数即队列的长度
  • GetHead(Q)
    • Q为非空队列，返回Q的队头元素
  • EnQueue(&Q,,e)
    • 插入元素e为新的队尾元素
  • DeQueue(&Q,&e)
    • 删除Q的队头元素并用e返回其值
  • QueueTraverse(Q)
    • 从队头到队尾依次队Q的每个数据访问
• 存储结构
  • 顺序表示
    • 循环队列（队列顺序表示的实现）
      • 解决伪满问题
      • 操作
        • 初始化
        • 求队列的长度
        • 入队
        • 出队
        • 取队头元素
  • 链式表示
    • 链队（队列的链式表示和实现）
    • 操作
      • 初始化
      • 入队
      • 出队
      • 取队头元素
• 案例分析与实现
  • 数制的转换
  • 括号匹配的检验
  • 表达式求值
  • 舞伴问题
• 特点
  • 只允许在表的前端进行删除操作，在表的后端进行插入操作，先进先出