栈

栈是只允许在一段进行插入或删除的线性表。

栈顶：线性表允许插入删除的那一侧

栈底：固定的，不允许进行插入和删除的那一侧。

栈是后进后出的

当n个不同元素进栈时，出栈元素不同排列的个数为：

$\Large \frac{1}{n+1}C_{2n}^{n}$

（卡特兰数）

顺序栈

#define MaxSize 50
typedef struct{
	Elemtype data[MaxSize];
	int top;
}Sqstack;

共享栈

两个栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。

只有当整个存储空间被占满的时候才会发生上溢。

链式存储

typedef struct LinkNode{
    ElemType data;
    struct Linknode* next;
}LiStack;

错点：

栈和队列有相同的逻辑结构（线性结构）
注意看是双向还是单向链表，是否为循环链表

队列

队列是一种操作受限的线性表，只允许在表的一段进行插入，在另一端删除。 先进先出

判断队列是否为空：

牺牲一个单位来区分：
1. 队列满：（Q.rear +1 ) % MaxSize == Q.front ;
2. 队列空： Q.rear==Q.front ;
3. 队列中的元素： (Q.rear - Q.front + MaxSize ) % MaxSize;
类型中增设size数据成员
1. Q.size==0为空
2. Q.size==MaxSize为满
类型中增设tag数据成员
1. 删除成功置tag为0，若导致Q.front==Q.rear则是队列空了
2. 添加成功置tag=1，若导致Q.front==Q.rear则是队列满了

队列的链式存储

链式队列特别适合数据元素编导那个比较大的清醒，而且不存在队列满且产生溢出的问题。

双端队列

两边都可以进行删除，插入操作

易错：

最适合用作队列的链表是：带队首指针和队尾指针的非循环单链表。
链式队列不能根据队首指针和队尾指针计算队列的长度。

栈和队列应用

栈的应用

算术表达式

中缀表达式转成后缀表达式：

按照运算符的运算顺序对所有运算单位加括号
讲运算符移动到对应括号的后面，按照“ 左操作数右操作数运算符” 重新组合
去除所有括号

$A+B*(C-D)-E/F==ABCD-*+EF/-$

中缀表达式传后缀表达式时需要借助一个栈，用来保存暂时还不能确定运算顺序的运算符。

遇到操作数。直接加入后缀表达式
遇到界限符。若为“（ ” ，则直接入栈，若为 “ ）” 则一次弹出栈中的运算符，并且加入后缀表达式，直到弹出 “（ ” ，这里 “（ ” 直接删除不加入后缀表达式
遇到运算符：若其优先级高于除了 “（ ”外的栈顶运算符，则直接入栈。（比如 * 大于 +）。否则，从栈顶开始一次弹出栈中优先级高于或等于当前运算符的所有运算符，并且加入后缀表达式，知道遇到一个优先级低于它的运算符或遇到“ （ ” 时停止，之后将当前运算符入栈。

队列在打印机中的应用

缓冲区，保证了打印数据正确，也提高了主机的效率。

CPU队列

将用户的请求加入队列，然后依次取出。

数组和特殊矩阵

数组

数组是由n个相同类型的数据元素构成的有限序列。数组只有存取元素和修改元素的操作。

$LOC(a_{i,j})=LOC(a_{0,0})+[i*(h_2+1)+j]*L$

对称矩阵

$\Large a_{i,j}=a_{j,i} (1<=j,j<=n)$ $\Large k=\left\{ \begin{array}{rcl} \Large\frac{i(i-1)}{2}+j-1 & &{(i>=j)}\\ \Large\frac{j(j-1)}{2}+i-1 & &{(i < j)} \end{array} \right.$