数据结构与算法第三章栈与队列

栈

栈顶/栈底/后进先出（LIFO）（Last In First Out）/上溢/下溢

计算后缀表达式，中缀表达式转后缀表达式

如何合理进行栈空间分配，以避免栈溢出或空间的浪费？

双栈共享一个栈空间（多栈共享栈空间）

两个栈共享一个数组空间\(V[maxSize]\)

\(t[i]\)和\(b[i]\)分别指示第\(i\)个栈的栈顶与栈底，初始\(t[0]=b[0]=-1\),\(t[1]=b[1]=maxSize\)

栈满条件：\(t[0]+1=t[1]\)（栈顶指针相遇）

栈空条件：\(t[0] = b[0]||t[1] = b[1]\)

栈的链接存储方式—— 链式栈

无栈满问题，空间可扩充
栈顶在链头
适合多栈操作（一个链中可准备多个栈顶标记）

后缀表达式求解

中缀表达式转后缀表达式

有关出栈、入栈序列种类计数

卡特兰数：\(C_n\)可以表示：

给定\(n\)个结点，构成不同二叉搜索树的数量；

\(n\)对括号匹配种数；

给定长度为\(n\)的前序序列，可能构成的不同二叉树的数量

对\(n*n\)方格，从\((0,0)\)走到\((n,n)\)，且不允许越过\(y=x\)，满足条件的路径种数；

将凸\((n+2)\)边形分割成\(n\)个三角形的分割方法数。

\(\displaystyle C_n=C^n_{2n}-C^{n+1}_{2n}=\frac{C_{2n}^n}{n+1}\)

\(C_n=C_{n-1}C_1+C_{n-2}C_2+\cdots+C_1C_{n-1}\)

绘制递归调用树

队列

front，rear指示队首，队尾（当前队尾元素后一个空位）位置，队列元素存放数组首尾相接，形成循环队列。

入队时将元素存入队尾指针，移动rear；出队时清空队首，移动front

队头指针进1:  front = (front+1) % maxSize;
队尾指针进1:  rear = (rear+1) % maxSize;
队列初始化：front = rear = 0;
队空条件：front == rear;
队满条件：(rear+1) % maxSize == front;
队列所存元素个数:(rear + k - front) % k;

链式队列队头在链头，队尾在链尾。链式队列在进队时无队满问题，但有队空问题。

队空条件为 front == NULL （还是front == rear）

数据结构与算法第三章 栈与队列

数据结构与算法第三章栈与队列