【问题描述】
设一个顺序栈，进行出栈和入栈操作。
【输入形式】
输入若干个整数（不超过1000），依次入栈；（提示：scanf("%d",&e)==1来作为输入判断）
【输出形式】
依次出栈并输出元素值，以空格分隔。
【样例输入】
23 45 67 14 -9 20 100 89 45 30
【样例输出】
30 45 89 100 20 -9 14 67 45 23

一、顺序栈

顺序栈主要运用顺序表实现，我们需要一个指向栈底的指针和一个指向栈顶的指针。

1.1 初始化顺序栈

#include<stdio.h>
#include<malloc.h>
#define SIZE 10
#define INCREAM 10
typedef struct stack{
    int *base;         //栈底指针
    int *top;          //栈顶指针
    int size;          //初始空间大小
}stack,*Pstack;
void Init_stack(Pstack s){
    s->base=(int *)malloc(sizeof(int)*SIZE);
    s->top=s->base;    //初始化栈顶指针在栈底位置
    s->size=SIZE;
}

1.2 判断是否空栈

int Empty_stack(Pstack s){
    if(s->base==s->top)   //当栈顶指针在栈底时，栈空
    return 1;
    else
    return 0;
}

1.3 入栈

void Push_stack(Pstack s,int x){
    if(s->top-s->base>=s->size){    //首先要判断栈满，栈满要重新开辟空间
        s->base=(int *)realloc(s->base,(s->size+INCREAM)*sizeof(int));
        s->top=s->base+s->size; 
        s->size+=INCREAM;
    }
    *s->top=x;      //压栈
    s->top++;       //栈顶指针加一
}

1.4 出栈

void Pop_stack(Pstack s,int *x){
    if(s->base==s->top){     //出栈要先判断栈是否为空，空栈无法出栈
        return ;
    }
    s->top--;                //先让栈顶指针指向最后一个压进去的值
    *x=*s->top;              //然后再输出这个值
}

1.5 获取栈顶元素

void Get_top_stack(Pstack s,int *x){
    if(s->base==s->top){
        return ;
    }
    *x=*(s->top-1);
}

1.6 代码实现

1.6.1 完整代码

#include<stdio.h>
#include<malloc.h>
#define SIZE 10
#define INCREAM 10
typedef struct stack{
    int *base;
    int *top;
    int size;
}stack,*Pstack;
void Init_stack(Pstack s){
    s->base=(int *)malloc(sizeof(int)*SIZE);
    s->top=s->base;
    s->size=SIZE;
}
int Empty_stack(Pstack s){
    if(s->base==s->top)
    return 1;
    else
    return 0;
}
void Push_stack(Pstack s,int x){
    if(s->top-s->base>=s->size){
        s->base=(int *)realloc(s->base,(s->size+INCREAM)*sizeof(int));
        s->top=s->base+s->size;
        s->size+=INCREAM;
    }
    *s->top=x;
    s->top++;
}
void Pop_stack(Pstack s,int *x){
    if(s->base==s->top){
        return ;
    }
    s->top--;
    *x=*s->top;
}
void Get_top_stack(Pstack s,int *x){
    if(s->base==s->top){
        return ;
    }
    *x=*(s->top-1);
}
int main(){
    int x;
    stack s;
    Init_stack(&s);
    while(scanf("%d",&x)==1){
        Push_stack(&s,x);
    }
    while(!Empty_stack(&s)){
        Pop_stack(&s,&x);
        printf("%d ",x);
    }
    return 0;
}

1.6.2 运行结果

二、链栈

链栈就相当于带头结点单链表的头插法，入栈就是每次都在头结点后面插入一个新元素，出栈就是每次让头结点的指针域指向第一个有效结点后面一个结点。

2.1 初始化链栈

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<string.h>
typedef struct Stack{
    int data;
    struct Stack *next;
}Stack,*PStack;
PStack Init_Stack(){                 //就是初始化一个带头结点的单链表
    PStack S=(PStack)malloc(sizeof(Stack));
    S->next=NULL;  
    return S;
}

2.2 判断是否空栈

int Empty_Stack(PStack S){
    if(!S->next) return 1;
    else return 0; 
}

2.3 入栈

void Push_Stack(PStack S,int e){
    PStack Pnew;
    Pnew=(PStack)malloc(sizeof(Stack));
    Pnew->next=NULL;
    Pnew->data=e;   
    Pnew->next=S->next;     //入栈就是头插法
    S->next=Pnew;
}

2.4 出栈

void Pop_Stack(PStack S,int *e){
    if(S->next){               //先判断是否栈空
        *e=S->next->data;      //出栈就是头结点指针域指向第一个有效结点后面的结点
        S->next=S->next->next;        //相当于每次出栈都是删除掉第一个有效结点
    }else{
        return ;
    }
}

2.5 获取栈顶元素

void Get_Stack(PStack S,int *e){  //获取栈顶元素方法不用删除结点
    if(S->next){
        *e=S->next->data;
    }else{
        return ;
    }
}

2.6 代码实现

2.6.1 完整代码

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<string.h>
typedef struct Stack{
    int data;
    struct Stack *next;
}Stack,*PStack;
PStack Init_Stack(){
    PStack S=(PStack)malloc(sizeof(Stack));
    S->next=NULL;
    return S;
}
int Empty_Stack(PStack S){
    if(!S->next) return 1;
    else return 0; 
}
void Push_Stack(PStack S,int e){
    PStack Pnew;
    Pnew=(PStack)malloc(sizeof(Stack));
    Pnew->next=NULL;
    Pnew->data=e;
    Pnew->next=S->next;
    S->next=Pnew;
}
void Pop_Stack(PStack S,int *e){
    if(S->next){
        *e=S->next->data;
        S->next=S->next->next;        
    }else{
        return ;
    }
}
void Get_Stack(PStack S,int *e){
    if(S->next){
        *e=S->next->data;
    }else{
        return ;
    }
}
void Print_Stack(PStack S){
    PStack p=S->next;
    while(p){
        printf("%d ",S->data);
        p=p->next;
    }
    printf("\n");
}
int Match_Stack(PStack S,char ch[]){
    int i,e;
    for(i=0;i<strlen(ch);i++){
        if(ch[i]=='('||ch[i]=='['||ch[i]=='{'){
            Push_Stack(S,ch[i]);
        }
        if(ch[i]==')'||ch[i]==']'||ch[i]=='}'){
            if(Empty_Stack(S)==1) return 0;
            Get_Stack(S,&e);
            switch(ch[i]){
                case ')':
                    if(e!='(')
                    return 0;
                    break;
                case ']':
                    if(e!='[')
                    return 0;
                    break;
                case '}':
                    if(e!='{')
                    return 0;
                    break;
            }
            Pop_Stack(S,&e);
        }
    }
    if(!Empty_Stack(S)){
        return 0;
    }
    return 1;
}
int main(){
    char ch[1000];
    PStack S;
    while(scanf("%s",&ch)==1){
        S=Init_Stack();
        if(!Match_Stack(S,ch)){
            printf("not match\n");
        }else{
            printf("match\n");
        }
    }
    return 0;
}

2.6.2 运行结果