Alg.11.数据结构-线性结构

@todo: 数组、链表、栈、队列、双向队列

栈

栈的特点：

• 栈（stack）是插入和删除只能在一个位置上进行的线性表，该位置叫做栈顶（top），对栈的基本操作有 push(进栈)和 pop(出栈)
• 后进先出（LIFO）

栈的应用 ：中缀表达式转换为后缀表达式

中缀: 9 + ( 3 - 1 ) * 3 + 10 / 2

后缀: 9 3 1 - 3 * + 10 2 / +

规则

1.从左到右遍历中缀表达式的每个数字和符号，若是数字就输出（直接成为后缀表达式的一部分，不进入栈）

2.若是符号则判断其与栈顶符号的优先级，是右括号或低于栈顶元素，则栈顶元素依次出栈并输出，等出栈完毕，当前元素入栈。

3.遵循以上两条直到输出后缀表达式为止。

https://github.com/chefyuan/algorithm-base/blob/main/animation-simulation/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95/%E5%85%B3%E4%BA%8E%E6%A0%88%E5%92%8C%E9%98%9F%E5%88%97%E7%9A%84%E9%82%A3%E4%BA%9B%E4%BA%8B.md

队列

队列的特点：

• 队列也是线性表的一种
• 遵守先进先出的规则，FIFO
• 队列的基本操作：
  • 入队（enqueue）:队尾(rear)插入一个元素
  • 出队（dequeue）:队头(front)移出一个元素

使用数组实现循环队列

数组实现：

动图来自 https://github.com/chefyuan/algorithm-base/blob/main/animation-simulation/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95/%E5%85%B3%E4%BA%8E%E6%A0%88%E5%92%8C%E9%98%9F%E5%88%97%E7%9A%84%E9%82%A3%E4%BA%9B%E4%BA%8B.md