考研笔记 | 数据结构 §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;
}//出栈
  1. 卡兰特数(出栈组合):$\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;
    }
    }
  1. 其他:

    1
    2
    3
    ElemType stack[MaxSize];int top=-1;//栈的声明与初始化
    Stack[++top]=x;//进栈,简化写法
    x=stack[top--];//先运算,后使用
-------文章到此结束  感谢您的阅读-------