栈与队列

1.栈

线性表的一种，插入与删除只允许在一端进行操作
术语：栈顶，桟低，空栈
特点：后进先出（LIFO，Last in First Out）
进栈顺序：a->b->c->d->e
出栈顺序：后进先出
（1）所有元素都近栈后出栈：e->d->c->b->a;
（2）进栈出栈穿插：b->e->d->c->a；
总结：有N个元素入栈，则有卡特兰数

3-栈与队列 - 图1

1.1顺序栈-栈的大小不可变

定义+初始化

  1. #define MaxSize 10
  2. //定义
  3. typedef struct{
  4.     ElemType data[MaxSize];
  5.     int top0;
  6.     int top1;//共享栈指针
  7. }SqStack;
  8. //初始化
  9. void InitStack(SqStack &S){
  10.     S.top0=-1;
  11.     S.top1=MaxSize;//共享栈指针在最上方，从最上方插入元素
  12. }

判空操作

  1. bool Elmpy(SqStack S){
  2.     if(S.top0==-1 && S.top1==MaxSize)
  3.         return true;
  4.     else
  5.         return false;
  6. }//栈满的条件：S.top0+1==S.top1

进栈操作

  1. bool Push(SqStack &S,ELempType i){
  2.     if(S.top==MaxSize-1)
  3.         return false;
  4.     S.top0=S.top0+1;
  5.     S.data[S.top0]=i;
  6. //以上两步等价与S.data[++S.top0]=i;//注意++S.to0p与S.top0++不一样，前者是先加一后调用，后者先调用后top0加1
  7.     return true;
  8. }

出栈操作

  1. bool Pop(SqStack &S,int &x){
  2.     if (S.top0==-1)
  3.         return false;
  4.     x=S.data[S.top0];
  5.     S.top0=S.top0-1;//x=S.data[S.top0--];
  6. }

读取栈顶元素

  1. bool ReadTop(SqStack S,int &x){
  2.     if(S.top0==-1)
  3.         return false;
  4.     x=S.data[S.top0];
  5.     return true;
  6. }

1.2 链栈(链式存储结构)

  1. //定义
  2. typedef struct LinkNode{
  3.     ElemType data;
  4.     struct LinkNode *next;
  5. }*LiStack;
  6. //其余详见单(双)链表

2.队列

只允许在一端插入，另一端进行删除操作。
特点：先进先出（FIFO:First In First Out）
术语：队头、队尾、空队列
计算元素个数：(rear+MaxSize-front)%MaxSize

2.1顺序存储

定义和初始化静态队列

  1. #define MaxSize 10
  2. typedef struct{
  3.     ElemType data[MaxSize];
  4.     int front,rear;//声明队头和队尾指针
  5. }SqQueue;
  6. void InitQueue(SqQueue &Q){
  7.     Q.rear=Q.front=0;//初始都指向0，Q为在main函数下声明的队列
  8. }

入队操作

  1. bool EnQueue(SqQueue &Q ,int e){
  2.     if ((Q.rear+1)%MaxSize==Q.front)//队尾指针的下个指针
  3.         return false;
  4.     Q.data[Q.rear]=x;
  5.     Q.rear=(Q.rear+1)%MaxSize;//亦可称为循环队列
  6.     return true;
  7. }

出队操作

  1. bool DeQueue(SqQueue &Q,int &x){
  2.     if (Q.rear==Q.front)//判断是否为空
  3.         return false;
  4.     x=Q.data[Q.front];
  5.     Q.front=(Q.front+1)%MaxSize;
  6.     return true;
  7. }

　获取元素

  1. bool GetQueue(SqQueue &Q,int &x){
  2.     if (Q.rear==Q.front)//判断是否为空
  3.         return false;
  4.     x=Q.data[Q.front];
  5.     return true;
  6. }

2.2队列的链式存储

定义和初始化

  1. //带头结点
  2. typedef struct LinkNode{
  3.     int data;
  4.     struct LinkNode *next;
  5. }LinkNode;
  6. typedef struct{
  7.     LinkNode *front,*rear;
  8. }LinkQueue;
  9. void InitQueue(LinkQueue &Q){
  10.     Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));
  11.     Q.front->next=NULL;
  12. }
  13. //判空
  14. bool IsEmpty(LinkQueue Q){
  15.     if (Q.front==Q.rear)
  16.         return true;
  17.     else
  18.         return false;
  19. }
  1. //不带头结点
  2. void InitQueue(LinkQueue &Q){
  3.     Q.front=NULL;
  4.     Q.rear=NULL;
  5. }
  6. //判空
  7. bool IsEmpty(LinkQueue Q){
  8.     if (Q.front==NULL)
  9.         return true;
  10.     else
  11.         return false;
  12. }

入队操作

  1. //带头结点
  2. void EnQueue(LinkQueue &Q,int x){
  3.     LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode));
  4.     s->data=x;
  5.     s->next=NULL;
  6.     Q.rear->next=s;
  7.     Q.rear=s;
  8. }
  9. //不带头结点
  10. void EnQueue(LinkQueue &Q,int x){
  11.     LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode));
  12.     s->data=x;
  13.     s->next=NULL;
  14.     if(Q.front==NULL){
  15.         Q.front=s;
  16.         Q.rear=s;
  17.     }
  18.     else{
  19.         Q.rear->next=s;
  20.         Q.rear=s;
  21.     }
  22. }

出队操作

  1. //带头结点
  2. bool DeQueue(LinkQueue &Q ,int &x){
  3.     if (Q.front==Q.rear)
  4.         return false;
  5.     LinkNode *p=Q.front->next;
  6.     x=p->data;
  7.     Q.front->next=p->next;
  8.     if (Q.rear==p)
  9.         Q.rear=Q.front;
  10.     free(p);
  11.     return true;
  12. }
  13. //不带头结点
  14. bool DeQueue(LinkQueue &Q ,int &x){
  15.     if (Q.front==NULL)
  16.         return false;
  17.     LinkNode *p=Q.front;
  18.     x=p->data;
  19.     Q.front->next=p->next;
  20.     if (Q.rear==p)
  21.         Q.rear=NULL;
  22.         Q.front=NULL;
  23.     free(p);
  24.     return true;
  25. }

2.3双端队列

输入受限与输出受限的双端队列

3.栈与队列的应用

3.1栈在括号匹配中的应用

  1. bool bracketCheck(char str[] ,int length){
  2.     SqStack S;
  3.     InitStack(S);//初始化栈
  4.     for(int i=0;i<length;i++){
  5.         if(str[i]=='('||str[i]=='['||str[i]=='{'){
  6.             Push(S,str[i]);}//左括号入栈
  7.         else{
  8.             if (StackEmpty(S))return false;//判断栈空
  9.             char topElem;
  10.             Pop(S,topElem);//栈顶元素出栈
  11.             if (str[i]==')'&&topElem!='(')return false;
  12.             if (str[i]==']'&&topElem!='[')return false;
  13.             if (str[i]=='}'&&topElem!='{')return false;
  14.         }
  15.         }
  16.         return StackEmpty(S);
  17. }

3.2栈的表达式求值

1.三种算术表达式：中缀表达式、前缀表达式（波兰表达式）、后缀表达式（逆波兰表达式）（√）
中缀表达式：a+b,运算符在操作数中间;a+b-c;a+b-cd
后缀表达式：ab+,运算符在操作数后面;ab+c-/abc-+;ab+cd-
前缀表达式：+ab,运算符在操作数之前;-+abc/+-bca;-+abcd
中缀转后缀【左优先原则：只要左边的运算符能先计算，就优先算左面的 】
中缀转前缀【右优先原则：只要右边的运算符能先计算，就优先算右面的】
中缀表达式求值：
（1）初始化两个栈。操作数栈，运算符栈
（2）扫描，按次序压入栈中，并按照左优先原则进行算数

3.3 栈在递归的调用

函数调用栈

3.4队列的应用

  1. （1）树的层次遍历
  2. （2）图的广度优先遍历
  3. （3）在操作系统中进行FCFS(先来先服务)

3.5特殊矩阵的压缩存储

  1. //一维数组
  2. ElemType a[10];//各数组元素大小相同，物理上连续存放
  3. //a[i]存放地址=loc+i*sizeof(ElemType);i从0开始
  4. //二维数组
  5. ElemType a[2][4];//两行四列；行优先与列优先
  6. //b[i][j]存储地址=Loc+(i*N+j)*sizeof(ElemType)行优先(N为列)
  7. //b[i][j]存储地址=Loc+(j*M+i)*sizeof(ElemType)列优先(M为行)

特殊矩阵：
（1）对称矩阵：若n阶方阵中对任意一个元素恒有Ai,j=Aj,i，则该矩阵为对称矩阵
主对角线i=j;上三角区；ij
（2）三角矩阵：
（3）三对角矩阵：带状矩阵；当|i-j|>1，有Ai,j=0
（4）稀疏矩阵：非零元素远远小于矩阵元素个数：顺序存储（<行，列，值>）
十字链表法