数据结构-栈

2017-06-27

单向栈

栈的存储

栈的顺序存储-数据结构

#define MaxSize 50	//定义栈中元素的最大个数
typedef struct{
    ElemType data[MaxSize]; //存放栈中元素
    int top,size;    //栈顶指针与最大数量，数组下标
}SqStack;

栈的链式存储-数据结构

typedef struct LinkStackNode{
    Elemtype data;
    struct LinkStackNode *ptr;
}LiStackNode,*LinStackNode;
typedef struct LinkStack{
    LiStackNode *top;   //只能取得top,即逆向插入链表，top时刻为链表头，先插入的在链表尾部,top也是链表头
    int count;
}LiStack;

栈的初始化

栈-顺序存储-初始化

//初始化栈
SqStack *InitStack(){
    SqStack *stack = (SqStack *)malloc(sizeof(SqStack));
    stack->top = -1;    //初始化栈顶指针
    stack->size = MaxSize;
    return stack;
}

栈-链式存储-初始化

//初始化栈
LiStack *InitLiStack(){
    LiStack *stack = (LiStack *)malloc(sizeof(LiStack));
    LinkStackNode *p = (LinkStackNode *)malloc(sizeof(LinkStackNode));
    p->ptr = NULL;
    stack->top = p; //栈顶占用一个空元素
    stack->count = 0;
    return stack;
}

判断栈空

栈-顺序存储-栈空判断

//判断栈空
bool StackEmpty(SqStack s){
    if(s.top == -1){
        return true;
    }else{
        return false;
    }
}

栈-链式存储-栈空判断

//判断栈空
bool LiStackEmpty(LiStack *s){
    if(s->count == 0){
        return true;
    }else{
        return false;
    }
}

栈的插入

栈-顺序存储-入栈

// 进栈
void PushStack(SqStack &S,Elemtype e){
    if(S.top == S.size - 1){
        printf("堆栈已满");
    }else{
        S.data[++S.top] = e;    //先自增，再入栈
    }
}

栈-链式存储-入栈

// 进栈
void PushLiStack(LiStack *S,Elemtype e){
    LiStackNode *p = (LiStackNode *)malloc(sizeof(LiStackNode));
    p->data = e;
    p->ptr = S->top;
    S->top = p;
    S->count ++;
}

栈的删除

栈-顺序存储-出栈

// 出栈,并返回出栈元素
Elemtype PopStack(SqStack &S){
    Elemtype e = 0;
    if(S.top == - 1){
        printf("堆栈空");
    }else{
        e =S.data[S.top--]; //先出栈，再自减
    }
    return e;
}

栈-链式存储-出栈

// 出栈,并返回出栈元素
Elemtype PopLiStack(LiStack *S){
    Elemtype e = 0;
    LiStackNode *top = S->top;
    if(S->count == 0){
        printf("堆栈空");
    }else{
        e = top->data;
        S->count --;
        S->top = top->ptr;
        free(top);
    }
    return e;
}

栈的读取

栈-顺序存储-读取栈顶

//读取栈顶元素
Elemtype GetStackTop(SqStack &S){
    Elemtype e = 0;
    if(S.top == - 1){
        printf("堆栈空");
    }else{
        e = S.data[S.top];
    }
    return e;
}

栈-链式存储-读取栈顶

//读取栈顶元素
Elemtype GetStackTop(LiStack *S){
    Elemtype e = 0;
    if(S->count == 0){
        printf("堆栈空");
    }else{
        e = S->top->data;
    }
    return e;
}

共享栈

栈的存储-数据结构

//共享栈A，B，总容量为MaxSize，A,B栈共同共享总空间为MaxSize大小的栈
#define MaxSize 50  //定义栈中的元素的最大个数
typedef struct{
    Elemtype data[MaxSize]; //存放栈中元素
    int topA,topB;    //A,B栈顶指针数组下标
}ShareStack;

栈的初始化

//初始化栈
ShareStack *InitShareStack(){
    ShareStack *stack = (ShareStack *)malloc(sizeof(ShareStack));
    stack->topA = -1;    //A栈栈顶为-1，从小往大存
    stack->topB = MaxSize;    //B栈栈顶为MaxSize，从大往小存
    return stack;
}

判断栈空

//判断栈空
bool ShareStackEmpty(ShareStack *s){
    if(s->topB - s->topA == MaxSize+1){
        return true;
    }else{
        return false;
    }
}

栈的插入-入栈

// 进栈
void PushShareStack(ShareStack *s,Elemtype e,int stack){
    if(s->topB + 1 == s->topA){
        printf("堆栈已满");
    }else{
        if(stack <= 0){ //stack参数小于等于0，则从A栈插入，否则从B栈插入
            s->data[++s->topA] = e; //先加再赋值
        }else{
            s->data[--s->topB] = e;
        }
    }
}

栈的删除-出栈

// 出栈,并返回出栈元素
Elemtype PopShareStack(ShareStack *s,int stack){
    Elemtype e = 0;
    if(stack <= 0){ //stack参数小于等于0，则从A栈插入，否则从B栈插入
        if(s->topA == -1){ //判断栈空
            printf("堆栈空");
        }else{
            e = s->data[s->topA--]; //先赋值再减
        }
    }else{
        if(s->topB == 50){ //判断栈空
            printf("堆栈空");
        }else{
            e = s->data[s->topB++];
        }
    }
    return e;
}

栈的读取-读取栈顶

//读取栈顶元素
Elemtype GetShareStackTop(ShareStack *s,int stack){
    Elemtype e = 0;
    if(stack <= 0){ //stack参数小于等于0，则从A栈插入，否则从B栈插入
        if(s->topA == -1){ //判断栈空
            printf("堆栈空");
        }else{
            e = s->data[s->topA];
        }
    }else{
        if(s->topB == 50){ //判断栈空
            printf("堆栈空");
        }else{
            e = s->data[s->topB];
        }
    }
    return e;
}