Stack（栈）是一种线性的数据结构，因此它既可以用数组实现，也可以用链表实现。栈的特征是只允许在一端进行插入或删除操作。

栈的基本操作
1） void InitStack(Stack* s)：初始化空栈S
2） int StackEmpty(const Stack* s)：判断一个栈是否为空
3） void Push(Stack* s,const int x)：进栈，将x加入使之成为新栈顶
4） int Pop(Stack* s)：出栈，若栈非空，则将栈顶元素返回
5） void DestroyStack(Stack* s)：销毁栈，并释放栈S占用的存储空间

链表实现

首先我们只需要记录一个栈顶节点即可，因此定义如下

typedef struct StackList{
    NODE_PTR head;
}StackList;

void InitStack(StackList* s){//初始化栈 
    s->head=NULL;
}
int StackEmpty(const StackList* s){//判断栈是否为空 
    if(s->head==NULL){
        return 1;
    }else{
        return 0;
    }
}
void Push(StackList* s,const int x){//入栈一个元素 
    s->head=ListAdd(s->head,x);
}
int Pop(StackList* s){//出栈一个元素 
    assert(s->head);
    int t=s->head->customerData;
    s->head=ListRemove(s->head);
    return t;
}
void DestroyStack(StackList* s){//释放栈 
    ListRemove(s->head);
}

int main(){
    int i;
    StackList s;
    InitStack(&s);
    for(i=0;i<5;i++){
        printf("Push:%d\n",i); 
        Push(&s,i);
    }
    for(int i=0;i<5;i++){
        printf("Pop:%d\n",Pop(&s));
    }
    DestroyStack(&s);
}

数组实现

通过数组我们也可以实现栈，由于数组是固定大小的，因此需要记录当前栈元素数量，以避免溢出。

typedef struct StackArray{
    int* data;
    int cnt;//记录目前栈内有多少元素 
    size_t max_size;//记录栈最多可以容纳多少元素 
}StackArray;

void InitStack(StackArray* s,size_t size){//初始化栈 
    s->data=(int*)malloc(size*sizeof(int));
    s->max_size=size;
    s->cnt=0;
}
int StackEmpty(const StackArray* s){//判断栈是否为空 
    if(s->cnt==0){
        return 1;
    }else{
        return 0;
    }
}
void Push(StackArray* s,const int x){//入栈一个元素 
    assert(s->cnt<s->max_size);
    s->data[s->cnt]=x;
    s->cnt+=1;
}
int Pop(StackArray* s){//出栈一个元素 
    assert(s->cnt);
    int t=s->data[s->cnt-1];
    s->cnt-=1;
    return t;
}
void DestroyStack(StackArray* s){//释放栈 
    free(s->data);
}

int main(){
    int i;
    StackArray s;
    InitStack(&s,10);
    for(i=0;i<9;i++){
        printf("Push:%d\n",i); 
        Push(&s,i);
    }
    for(int i=0;i<5;i++){
        printf("Pop:%d\n",Pop(&s));
    }
    DestroyStack(&s);
}