栈和队列

对于栈和队列，可以理解为操作受限的线性表，只可以在线性表的表头或者表尾进行操作

栈

定义

• 栈(stack)是限定仅在表尾进行插入或删除操作的线性表。
• 因此，对栈来说，表尾端有其特殊含义，称为栈顶(top)
• 相应地，表头端称为栈底(bottom)。
• 不含元素的空表称为空栈。
• 栈的修改是按后进先出的原则进行的，因此，栈又称为后进先出(LastIn First Out, LIFO)的线性表，

应用

• 进制转换：假设十进制转换为K进制：

  • 创建一个栈Stack
  • 不断除以K取余数。后生成的余数先输出，先生成的余数后输出，正好符合栈的后进先出性质。

• 括号匹配：

  • 从左向右扫描字符串
  • 若遇到左括号：压栈
  • 若遇到右括号：弹出栈顶的左括号与之匹配。
  • 最后判断栈空

• n对括号共有多少种可能的合法匹配序列：第n个卡特兰数

  Cn=(2n)!/(n!*n!)/(n+1)

• 表达式求值：（中缀表达式转变为后缀表达式）

  • 从左到右依次读入后缀表达式的每一个操作数/运算符/结束符
  • 若读到的是操作数，将它压入栈。
  • 若读到的是运算符，就从操作数栈中连续弹出两个元素（操作数），进行相应的运算，并将结果压入栈中。
  • 读入结束符时，栈顶元素就是计算结果。

• 调度场算法：中缀表达式转后缀表达式

  • 设置一个栈，存放运算符从左到右依次读入中缀表达式的每一个元素
  • 操作数规则：直接放入后缀表达式,注意对多位数的处理
  • 运算符规则：
    • 栈空或栈顶是左括号：压栈
    • 当前运算符优先级>栈顶运算符：压栈
    • 当前运算符优先级<=栈顶运算符：弹栈直至当前运算符 优先级>栈顶或栈空或栈顶为左括号（期间弹出的运算符顺序依次放入后缀表达式），再把当前运算符压栈
  • 括号规则： (1) 遇到左括号：压栈 (2) 遇到右括号：弹栈直至左括号
  • 结束符规则：弹栈至栈空

• 栈混洗：给定入栈序列，模拟出栈序列

  • n个元素的栈混洗总数，即n对括号的匹配序列，卡特兰数*(n+1)

  • n个元素的栈混洗合法出栈序列，即n对括号的合法匹配序列，卡特兰数*(n+1)

• 利用栈模拟队列:

  利用两个栈模拟队列

• 共享栈

队列

定义

• 队列(queue)是一种先进先出(First In First Out, FIFO)的线性表
• 允许插入的一端称为队尾(rear), 允许删除的一端则称为队头(front)。

应用

• BFS广度优先搜索

• 栈和队列都需要注意的一点是top和rear指针是指向元素还是下一个空位置，判满和判空条件不同，

• 双端队列

• 利用队列模拟栈