c语言实现栈，共享栈，链式栈

ゝ一世哀愁。 2022-06-09 00:54 220阅读 0赞

**栈的数据结构**

typedef struct{
        Elemtype data[MaxSize];
        int top;  //栈为空的时候top=-1,入栈的时候top+1，然后在入栈。元素个数top+1
    }SqStack;

**共享栈**

/*共享栈的结构*/
    typedef struct{
        Elemtype data[MaxSize];
        int top0, top1;
    }SharingStack;

当top0 = -1的时候，0号栈为空，top1 = MaxSize的时候，1号栈为空，插入1号栈的时候，top1先减一，然后才能插入。当top1 - top0 = 1的时候，表示栈满。  
存取的时间复杂度仍然是O(1)

**链式栈**  
只不过使用单链表实现后进先出而已

/*链式栈的结构*/
    typedef struct LinkStack{
        Elemtype data;
        struct LinkStack * next;
    }LinkStack;

栈的基本操作也很简单

void InitStack(SqStack * S){
        S->top = -1;
    }//栈满的时候，top+1 == MaxSize
    
    int StackEmpty(SqStack S){
        if(S.top == -1) return 1;
        else return 0;
    }
    
    int Push(SqStack * S, Elemtype e){
        if(S->top == MaxSize-1) return 0;
        S->data[++S->top] = e;
        return 1;
    }
    
    int Pop(SqStack * S, Elemtype *e){
        if(S->top == -1) return 0;
        *e = S->data[S->top--];
        return 1;
    }
    
    int GetTop(SqStack S, Elemtype *e){
        if(S.top == -1) return -1;
        *e = S.data[S.top];
        return 1;
    }

简单的测试主程序

int main(int argc, const char * argv[]) {
        SqStack S;
        InitStack(&S);
        printf("empty:%d\n", StackEmpty(S));
        Push(&S, 1);
        Push(&S, 2);
        Push(&S, 3);
        printf("1 Stack has %d elems\n", S.top+1);
        int e;
        Pop(&S, &e);
        printf("Pop : %d\n" ,e);
        printf("2 Stack has %d elems\n", S.top+1);
        GetTop(S, &e);
        printf("top Elem is : %d\n", e);
    }