数据结构之栈的兑现

数据结构之栈的实现

1、顺序结构的栈

#define MaxSize 10
typedef char ElementType;
typedef struct{
    ElementType elem[MaxSize];
    int top;
}SqStack;

#include "MyStackSeq.h"
void InitStack(SqStack *&s)
{
    s=(SqStack*)malloc(sizeof(SqStack));
    s->top=-1;
}
void ClearStack(SqStack *&s){
    free(s);
}
int StackLength(SqStack *s){
    return s->top+1;
}
int StackEmpty(SqStack *s){
    return s->top==-1;
}
int Push(SqStack *&s,ElementType e){
    if(s->top+1==MaxSize){
        return 0;
    }   
    
    s->top++;
    s->elem[s->top]=e;
    return 1;
}

int Pop(SqStack *&s,ElementType &e){
    if(s->top==-1){
        return 0;
    }
    e=s->elem[s->top];
    s->top--;
    return 1;
}
int GetTop(SqStack *s,ElementType &e){
    if(s->top==-1){
        return 0;
    }
    e=s->elem[s->top];
    
    return 1;
}
void DisplayStack(SqStack *s){
    for (int i=s->top; i>=0; i--) {
        printf("%c",s->elem[i]);
    }
    printf("\n");
}

2、链式结构的栈

 

typedef char ElementType;
typedef struct linknode{
    ElementType data;
    struct linknode *next;
}LiStack;



void InitStack(LiStack *&s){
    s=(LiStack *)malloc(sizeof(LiStack));
    s->next=NULL;
    
}
void ClearStack(LiStack *&s){
    LiStack *p=s->next;
    while(p!=NULL){
        
        free(s);
        s=p;
        p=p->next;
    }
    free(s);
    
}
int StackLength(LiStack *s){

    LiStack *p=s->next;
    int i=0;
    while (p!=NULL) {
        i++;
        p=p->next;
    }
    
    return i;
}
int StackEmpty(LiStack *s){

    return s->next==NULL;
}
int Push(LiStack *&s,ElementType e){
    LiStack *p=(LiStack*)malloc(sizeof(LiStack));
    p->data=e;
    p->next=s->next;
    s->next=p;

    return 1;
    
}
int Pop(LiStack *&s,ElementType &e){

    if(s->next==NULL){
        return 0;
    }
    LiStack *p=s->next;
    e=p->data;
    s->next=p->next;
    free(p);
    return 1;
}


int GetTop(LiStack *s,ElementType &e){
    
    if(s->next==NULL){
        return 0;
    }
    
    LiStack *p=s->next;
    e=p->data;
    free(p);
    return 1;
    
}
void DisplayStack(LiStack *s){
    LiStack *p=s->next;
    while (p!=NULL) {
        printf("%c",p->data);
        p=p->next;
    }
    printf("\n");
}