初始栈——解密回文

栈是一种后进先出的数据结构，它只限定为只能在一端进行插入和删除操作。

比如说有一个小桶，它的直径只能放一个小球，我们现在小桶依次放入2、1、3号小球。假如你现在需要拿出2号球，那就必须先将3号小球拿出，再拿出1号小球，最后才能将2号小球拿出来。

栈的实现只需要一个以为数组和一个指向栈顶的变量就可以了，我们通过这个变量来对栈进行插入和删除操作。我们先来看看一个例子，了解一下栈究竟有什么作用，回文字符串，就是正读反读均相同的字符序列，如“xyzyx”。

首先我们需要读取这行字符串，并求出这个字符串的长度。

    char aInput[101]    
    gets(aInput);
    long len = strlen(aInput);

我们还需要获得这行字符串的中点位置，即；

    mid = (len * 0.5) - 1;

接下来就是栈出场了。
我们先将mid之前的字符全部入栈。因为这里的栈是用来存储字符的，所以这里用来实现栈的数组类型是char。

    int top = 0;
    for (i = 0 ; i <= mid; i++) {
        aTemp[++top] = aInput[i];
    }

接下来进入判断回文的关键步骤。将当前栈中的字符依次出栈，看看能否与mid之后的字符一一匹配，如果都能匹配则说明这个字符是回文字符串，否则这个字符串就不是回文字符串。

    for (i = next; i<= len -1; i++) {
        if (aInput[i] != aTemp[top]) {
            break;
        }
        top--;
    }
    
    if (top == 0) {
        printf("YES"); // 说明栈内所有的字符都被一一匹配
    }else{
        printf("NO");
    }

到这里就完成判断输入的字符串是否为回文字符串了，还有一些问题需要考虑，这里就是一种判断方式而已。全部代码如下；

#include <stdio.h>
#include <string.h>

int main(int argc, const char * argv[]) {
    
    char aInput[101],aTemp[101];
    int i, mid, next, top;
    
    gets(aInput);
    long len = strlen(aInput);
    // 求字符串的中点
    mid = (len * 0.5) - 1;
    
    // 栈顶初始化
    top = 0;
    for (i = 0 ; i <= mid; i++) {
        aTemp[++top] = aInput[i];
    }
    
    // 找出需要进行字符匹配的起始下标
    if(len % 2 == 0){
        next = mid +1;
    }else{
        next = mid +2;
    }
    
    // 开始匹配
    for (i = next; i<= len -1; i++) {
        if (aInput[i] != aTemp[top]) {
            break;
        }
        top--;
    }
    
    if (top == 0) {
        printf("YES"); // 说明栈内所有的字符都被一一匹配
    }else{
        printf("NO");
    }
    getchar();getchar();
    
    return 0;
}