考研笔记 | 数据结构 §3. 栈和队列

发表于 分类于 阅读次数： 本文字数： 2.2k 阅读时长 ≈ 2 分钟

§1. 栈

  1. 定义：只允许在一端进行插入或删除操作的线性表。

  2. 栈顶：线性表允许进行插入或删除的那一端。

  3. 栈底：固定的，不允许进行插入或删除的另一端。

  4. 栈的基本操作

    1
    2
    3
    4
    5
    6
    InitStack(&S)//初始化栈
    StackEmpty(S)//判定空
    Push(&S,x)//x入栈
    Pop(&S,&x)//x出栈
    GetTop(S,&x)//取栈顶x
    CleanStack(&S)//销毁栈

  5. 定义

    1
    2
    3
    4
    5
    #define MaxSize 50
    typedef struct{
    	Elemtype data[MaxSize];
    	int top;
    } SqStack; //顺序栈
    1
    2
    3
    4
    typedef struct Linknode{
    	Elemtype data;
    	struct Linknode *next;
    }*LiStack//链栈

  6. 进栈与出栈

    1
    2
    3
    4
    5
    bool Push(SqStack &S,Elemtype x){
     if(s.top==MaxSize-1)    return false;
     S.data[++S.top]=x;
     return true;
    }//入栈
    1
    2
    3
    4
    5
    bool Pop(SqStack &S,Elemtype &x){
    	if(S.top==-1)   return false;
    	x=S.data[S.top--];
    	return false;
    }//出栈

  7. 卡兰特数（出栈组合）:$\frac {1}{n+1} c^n_{2n}=\frac {1}{n+1}\frac {(2n)!}{n!n!}$

§2. 队列

  1. 定义：只允许在表的一端插入，另一端删除。

  2. 队头：允许删除的一端（出队端）

    队列

  3. 队尾：允许插入的一端（入队端）

  4. 队列常用操作：

    1
    2
    3
    4
    5
    InitQueue(%Q)//初始化队列
    QueueEmpty(Q)//判队空
    EnQueue(&Q,x)//入队
    DeQueue(&Q,&x)//出队
    GetHead(Q,&x)//读队头

  5. 队列定义

    1
    2
    3
    4
    5
    #define MaxSize 50
    typedef struct{
    	Elemtype data[MaxSize];
    	int front,rear;
    }SqQueue;

  6. 假上溢，出现 r==MaxSize

    假上溢示意

  7. 循环队列：

    队满：(Q.rear+1)%MaxSize=Q.front

    队空：Q.front==Q.rear

    元素个数:(Q.rear-Q.front+MaxSize)%MaxSize

  8. 初始化队列

    1
    2
    3
    void InitQueue(&Q){
        Q.rear=Q.front=0;
    }

  9. 判队空

    1
    2
    3
    4
    5
    bool IsEmpty(Q){
        if(Q.rear=Q.front)
          return true;
      	else return false;
    }

  10. 入队

    1
    2
    3
    4
    5
    6
    7
    bool EnQueue(SqQueneue &Q,ElemType x){
        if((Q.rear+1)%MaxSize==Q.front)
          return false;
      	Q.data[Q.rear]=x;
      	Q.rear=(Q.rear+1)%MaxSize;
      	return true;
    }

  11. 出队（删除节点）

    1
    2
    3
    4
    5
    6
    7
    bool DeQueue(SqQueneue &Q,ElemType &x){
    if(Q.rear==Q.front)
    	return false;
    x=Q.data[Q.front];
    Q.front=(Q.front+1)%MaxSize;
    return true;
    }

  12. 栈与队列的比较（简化）

简化栈简化队列
结构 S[ ]+topq[ ]+front+rear
初始化 top=0front=rear=0
入栈队列 S[top++]=xq[rear]=x,rear=(rear+1)%MaxSize
出栈队列 x=S[–top]q[front]
栈 / 队列顶 S[top-1]q[front]
栈 / 队列空 top==0front==rear

  1. 双端队列：两端均可进行入队操作的队列

    双端队列

  2. 输入输出受限的双端队列：

    输入输出受限的双端队列

  3. 栈的括号匹配

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    bool MatchBrackets(Char *str){
    	InitStack(S);
    	int i=0;
    	while(str[i]!='\0'){
    		switch(str[i]){
    			case'('=Push(S,'(');break;//左括号入栈
    			case'['=Push(S,'[');break;
    			case'{'=Push(S,'{');break;
    			case')':Pop(S,e);//右括号入栈，检测栈顶
    					if(e!='(') return false;break;
    			case']':Pop(S,e);if(e!=']') return false;break;
    			case'}':Pop(S,e);if(e!='}') return false;break;
    			default:break;
    		}
    		i++;
    	}
    	if(!IsEmpty(S)){
    		printf("括号不匹配\n");
    		return false
    	}else{
    		printf("括号匹配\n");
    		return true;
    	}
    }

  4. 其他：

1
2
3
ElemType stack[MaxSize];int top=-1;//栈的声明与初始化
Stack[++top]=x;//进栈，简化写法
x=stack[top--];//先运算，后使用