数据结构 栈与队列
栈
给定n个元素，出栈的顺序的情形满足卡特兰数，计算公式为Cn\2n/(n+1)
b=t=-1
- 出栈前先判断栈是否为空，空栈出栈报错
- 进栈，先top++
- 栈顶指针top指向栈顶元素
- 出栈，先弹出元素，然后top--
- 栈底指针固定不变，指向初始位置
- 栈满t==n-1、栈中元素个数t-b
b=t=0
- 出栈前先判断栈是否为空，空栈出栈报错
- 进栈，先弹入元素，后top++
- 栈顶指针top指向栈顶元素
- 出栈，先top--，后弹出元素，
- 栈底指针固定不变，指向初始位置
- 栈满t==n、栈中元素个数t-b
对顶栈（共享栈） |t1-t2|==1 共享栈满
共享栈优点：节省存储空间，降低上溢出的概率
顺序栈的插入和删除不会出现元素移动的情况：因为操作都在队尾进行
顺序栈 有空栈、满栈
链栈： “头出头插”单链表 入栈头插法 top指向头结点
空栈 top->next == NULL
链栈 有空栈，无满栈
栈的应用
- 括号匹配
- 进制转换 转换法则：除留余数法
- 函数和递归调用 基本准则：先调用后执行
- 表达式求值
表达式类型：中缀表达式、前缀表达式（波兰式）、后缀表达式（逆波兰式）
中缀表达式转后缀表达式 操作数栈+符号栈
队列
先进先出
- 队首front
- 队尾rear
基本操作
- 进队 在队尾插入元素
- 出队 在队首删除元素
循环队列
循环队列，解决队满后假溢出
循环队列判断队列空或满
- length(队列长度) 互斥
- flag 互斥
- 循环意义下尾指针加一是否等于头指针，相等则队列满
性质（浪费一个空间）
- front指针指向队首元素
- rear所指的单元始终为空（浪费一个空间）
- 循环队列为空：front==rear
- 循环队列满：(rear+1)%MAX_QUEUE_SIZE == front
- 入队操作：rear=(rear+1)%MAX_QUEUE_SIZE
- 出队操作：front=(front+1)%MAX_QUEUE_SIZE
- 队列中元素个数：len=(rear - front + MAX_QUEUE_SIZE)%MAX_QUEUE_SIZE
操作：
- 入队，需要先判断队列是否已满
- 出队，需要先判断队列是否已空
链队列
头出尾插的单链表
- 若是单链表，一般给定带尾指针的循环单链表
- 若是双链表，一般给定带头指针或尾指针的循环双链表
双端队列
- 输入受限
- 输出受限
队列的典型应用
- 排队、打印服务
- 树的层次遍历
- 图的广度优先遍历
- 优先队列