数据结构之用堆栈判断回文

回文判断

回文是指正读反读均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。编写一个程序，使用栈判定给定的字符序列是否为回文。

输入格式:
输入待判断的字符序列，按回车键结束，字符序列长度<20。

输出格式:
若字符序列是回文，输出“YES”；否则，输出“NO”。

输入样例:
abdba

解题思路

首先，我们要明白堆栈是具有一定操作约束的线性表，它的特点是只能在一端（栈顶）做插入或者删除操作，即里面的元素遵循后入先出的规则。
这样，这道题的解题思路就有了。给我们一段回文数字，我们先按顺序把它们压入栈中，由于它取元素的顺序是后入先出的，我们再一个个把它们取出来，这时候取出的元素顺序刚好是原始数据的反序。我们只需要把从栈中取出的元素依次与原始序列对比，判断其是否一致，就能判断该字符序列是否是回文了。（提示：比较时我们只需要比较序列的一半就可以啦，相信爱观察的你已经发现了）

源代码

#include<stdio.h>
#define SIZE 20 /*定义回文字符的最大长度*/
typedef struct SNode *Stack;
typedef char ElemenType;
struct SNode{
    ElemenType data;
    Stack next;
};
/*创建一个空栈*/
Stack createStack(){
    Stack s;
    s=(Stack)malloc(sizeof(struct SNode));
    s->next=NULL;
    return s;
}
/*判断栈是否为空*/
int isEmpty(Stack s){
    return (s->next==NULL);
}
/*向栈中放入元素*/
void Push(ElemenType item,Stack s){
    Stack p;
    p=(Stack)malloc(sizeof(struct SNode));
    p->next=s->next;
    s->next=p;
    p->data=item;
}
/*取出栈中元素*/
ElemenType Pop(Stack s){
    Stack p;
    ElemenType top;
    if(isEmpty(s)){
        printf("栈为空！");
        return NULL;
    }else{
    p=s->next;
    s->next=p->next;
    top=p->data;
    free(p);
    return top;
    }
}
int main(){
    Stack s;
    int i,j;
    ElemenType a[SIZE];
    gets(a);               //输入回文字符
    s=createStack();       //初始化栈
    for(i=0;a[i]!='\0';i++){
        Push(a[i],s);      //将元素一个个压入栈中
    }
    for(j=0;j<=i/2;j++){   //只需要比较一半长度即可
        if(a[j]!=Pop(s)){  //将原序列的每个元素与取出的元素相比较
            printf("NO");
            return 0;
        }
    }
    printf("YES");
    return 0;
}