数据结构系列(三)-栈

本篇介绍数据结构-栈

思维导图

数据结构系列(三)-栈

  • 定义

      是限制仅在表的一端进行插入和删除运算的线性表。
    
  • 属性

    • 通常称插入、删除的这一端为 栈顶(Top),另一端称为 栈底(Bottom)。

    • 当表中没有元素时称为 空栈

    • 栈为 后进先出(Last In First Out)的线性表,简称为 LIFO 表。

  • 顺序栈-基本运算

    • 置空栈
    void InitStack (SeqStack *s){
        s-top=-1;
    // 置空顺序栈,由于c语言数组下标是从0开始,所以栈中元素亦从0开始
    // 存储,因此空栈时栈顶指针不能是0,而只能是-1
    }
    
    • 判栈空
    int StackEmpty (SeqStack *S){
        return S->top===-1;
    }
    
    • 判栈满
    int StackFull(SeqStack *S){
        return S->top==StackSize-1;
    }
    
    • 进栈
    void Push(SeqStack *S,DataType x){
        if(StackFull(s)){
            printf("stack overflow");
        }else{
            S->top=S->top+1;
            S->data[S->top]=x;
        }
    }
    
    • 退栈
    DataType Pop(SeqStack *S){
        if(StackEmpty(S)){
            printf("stack underflow");
            exit(0);
        }else{
            return S->data[S->top-1]
        }
    }
    
    • 取栈顶元素
    DataType GetTop(SeqStack *S){
        if(StackEmpty(S)){
            printf("stack empty");
            exit(0);
        }else{
            return S->data[S->data];
        }
    }
    
  • 链栈-基本运算
    数据结构系列(三)-栈

    • 判栈空
    int StackEmpty(LinkStack top){
        return top==null;
    }
    
    • 进栈
    LinkStack Push(LinkStack top,DataType x){
        StacKNode *p;
        p=(StackNode *)malloc(sizeof (StacKNode));
        p->data=x;
        p-next=top;
        top=p;
        return top;
    }
    
    • 退栈
    LinkStack Pop(LinkStack top, DataType *x){
        SrackNode *p=top;
        if(StackEmpty(top)){
            printf("stack empty");
            exit(0);
        }else{
            *x=p->data;
            top=p->next;
            free(p);
            return top;
        }
    }
    
    • 取栈顶元素
    DataType GetTop(LinkStack top){
        if(StackEmpty(top)){
            printf("stack empty");
            exit(0);
        }else{
            return top->data;
        }
    }
    
上一篇:ajax跨域问题解决方案(jsonp的使用)


下一篇:在ajax请求中,contentType 和 dataType 的区别?