数据结构（二）——堆栈

栈（stack）又名堆栈，它是一种运算受限的线性表。

栈分为两种——线性栈和链表栈，下面分别用两个算法题实现这两种栈

线性栈例题：

回文指正反读均相同的字符序列，例如“abba”和“abdba”均是回文，但“good”不是回文。利用栈或者队列，判定给定字符串是否是回文。

代码实现：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MIX 99
    typedef struct{
        char c[MIX];
        int top;    
    }Stack;                                      //栈结构体定义
    Stack * Init_Stack(){                 //初始化栈
        Stack * s;
        s = (Stack *)malloc(sizeof(Stack));
        s->top = -1;
        return s;
    }
    
    int Judge_Stack(Stack * s){                                 //判空
        if(s->top == -1){
            return 0;
        }
        else{
            return 1;
        }
    }
    
    int Push_Stack(Stack * s , char x){                    //入栈
        if(s->top == MIX-1){
            return 0;
        }
        else{
            s->top++;
            s->c[s->top] = x;
            return 1;
        }       
    }
    
    char Pop_Stack(Stack * s){                         //出栈
        char cTemp;
        if(!Judge_Stack(s)){
            return '@';
        }
        else{
            cTemp = s->c[s->top];
            s->top--;
            return cTemp;
        }
    }

int main(){
    int i = 0;
    char cOri[MIX];
    char cChg[MIX];
    Stack * s = Init_Stack();
    scanf("%s",cOri);
    
    while(cOri[i]!='\0'){                       //将每个字符入栈
        Push_Stack(s,cOri[i]);
        i++;
    }
    for(i=0;i<MIX;i++){                          //将每个字符出栈
        cChg[i] = Pop_Stack(s);
        if(cChg[i] == '@') break;
    }
    cChg[i] = '\0';
    if(strcmp(cChg,cOri)==0){                     //判断出栈和入栈后是否相等
        printf("回文");
    }
    else{
        printf("不是回文");
    }
    return 0;
}

链式栈例题：

假定运算符集合为{ +、-、*、/、（、）}，利用栈将输入的中缀表达式转换成等价的后缀表达式，并输出。(中缀转后缀)

思路：遍历字符串，遇见字符直接输出，遇见运算符入栈，再遇运算符时与栈中已有运算符比较，如果栈中运算符优先级较高或相等则出栈，否则入栈，遇见左括号出栈，遇见右括号则出栈直到左括号，遍历完后将栈中的字符全部出栈。

  #include<stdio.h>
#include<stdlib.h>
typedef struct stack{
    char a;
    struct stack * pNext;
}Stack;                                                //链式栈结构体

int Push_Stack(Stack * Top,char a){                //入栈
    Stack * s;
    s = (Stack *)malloc(sizeof(Stack));
    if(s==NULL) return 0;
    else{
        s->pNext = NULL;
        s->a = a;
        s->pNext = Top->pNext;
        Top->pNext = s;
        return 1;
    }
}

char Pop_Stack(Stack * Top){                  //出栈
    if(Top->pNext==NULL) return NULL;
    else{
        Stack * s;
        char a;
        s = Top->pNext;
        Top->pNext = s->pNext;
        a = s->a;
        free(s);
        return a;
    }
}

int main(){
    int i=0;
    char temp;
    char a[50];
    Stack *Top = (Stack *)malloc(sizeof(Stack));
    Top->a='0';
    Top->pNext=NULL;
    //char a[]="a+b-a*((c+d)/e-f)+g";
    while(scanf("%s",a)!=EOF){
    do{
        if(a[i]=='+'||a[i]=='-'||a[i]=='*'||a[i]=='/'||a[i]=='('||a[i]==')'){         //判断符号   
            if(Top->pNext!=NULL){
                switch(a[i]){
                    case '+':
                        while(Top->pNext->a=='-'||Top->pNext->a=='+'||Top->pNext->a=='*'||Top->pNext->a=='/'){
                            printf("%c",Top->pNext->a);
                            Pop_Stack(Top);
                            if(Top->pNext==NULL) break; 
                        }
                        break;
                    case '-':
                        while(Top->pNext->a=='-'||Top->pNext->a=='+'||Top->pNext->a=='*'||Top->pNext->a=='/'){
                            printf("%c",Top->pNext->a);
                            Pop_Stack(Top);
                            if(Top->pNext==NULL) break;
                        }
                        break;
                    case '*': while(Top->pNext->a=='*'||Top->pNext->a=='/'){
                            printf("%c",Top->pNext->a);
                            Pop_Stack(Top); 
                            if(Top->pNext==NULL) break;
                        }
                        break;
                    case '/': while(Top->pNext->a=='*'||Top->pNext->a=='/'){
                            printf("%c",Top->pNext->a);
                            Pop_Stack(Top); 
                            if(Top->pNext==NULL) break;
                        }
                        break;
                    case '(':break;
                    case ')':temp = Pop_Stack(Top);
                            while(temp!='(') {
                                printf("%c",temp);
                                temp =Pop_Stack(Top);
                            }
                    }
                    if(a[i]==')') ;
                    else Push_Stack(Top,a[i]);
                }
                else{
                    Push_Stack(Top,a[i]);
                }
            }
            else{
                printf("%c",a[i]);
            }
            i++;
        }while(a[i]!='\0');
        while(Top->pNext!=NULL){
            printf("%c",Pop_Stack(Top));
        }
    }
    return 0;
}