数据结构

数据结构笔记之——栈

概念

  • 限定插入和删除只能在表的端点进行的线性表

  • 越靠后进入的越先出来

  • 表尾（an端）称之为栈顶Top，表头（a1端）称之为栈底Base

  • 插入元素到栈顶为入栈Push，从栈顶删除最后一个元素称之为出栈Pop

typedef struct { //顺序栈
    ElemType *base;
    ElemType *top;
    int stacksize;
}SqStack;
typedef struct StackNode{ //链栈
    ElemType data;
    struct StackNode *next;
}StackNode, *LinkStack;

栈空时出栈，则下溢。栈满时入栈，则上溢。

基本操作

顺序栈的初始化

Status InitStack(SqStack *s){
    s->base=(ElemType *)malloc(sizeof(ElemType)*STACK_INIT_SIZE);
    if(s->base==NULL){
        return OVERFLOW;
    }
    s->base=s->top;
    s->stacksize=STACK_INIT_SIZE;
    return OK;
}

顺序栈的出栈

Status Pop(SqStack *s,ElemType *e){
    if(s->base==s->top){
        return ERROR; //栈空
    }
    e=*(--s->top);
    return OK;
}

顺序栈的入栈

Status Push(SqStack *s,ElemType e){
    if(s->top-s->base==s->stacksize){ //栈满
        return ERROR;
    }
    *(s->top++)=e;
    return OK;

}

顺序栈获取栈顶元素

Status GetTop(SqStack S, ElemType e){ 
    //若栈不空，则用e返回S的栈顶元素，并返回OK
    if (S.top == S.base){ // 空栈
        return ERROR;
    }
    e = *(S.top-1); //返回非空栈中栈顶元素
    return OK;
} //GetTop

链栈的出栈

Status push_L(LinkStack *S,ElemType e){
    LinkStack p;
    p=(LinkStack *)malloc(sizeof(StackNode));
    p->data=e;
    p->next=*S;
    *S=p; //修改栈顶元素

}

链栈的入栈

Status pop_l(LinkStack *S,ElemType *e){
    LinkStack p=*S;
    *e=(*S)->data;
    *S=(*S)->next;
    free(p);
    return OK;
}

Comment