0%

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

  • 英语:

§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[ ]+top q[ ]+front+rear
初始化 top=0 front=rear=0
入栈队列 S[top++]=x q[rear]=x,rear=(rear+1)%MaxSize
出栈队列 x=S[–top] q[front]
栈/队列顶 S[top-1] q[front]
栈/队列空 top==0 front==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--];//先运算,后使用
-------全文结束  感谢您的阅读-------
  • 本文作者: LuoV
  • 本文链接: https://xian6ge.cn/posts/cc277e0f/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!