1.回文数定义与题目解读

回文数是指正读反读都能读通的句子。比如“我为人人，人人为我”、“1234321”、“abcba”是回文数，但“一杯茶一包烟，一行代码写一天”，“123456”，“abcdef”就不是回文数。
那么通过以上的几个例子可以发现以下几点：

1. 回文数是要求这串文字的左侧与右侧相同，即回文数左右对称，但是若字符个数为奇数的情况下，那么中间的字符并不会对整个判断其影响作用，所以由此可以推测出回文数需要考虑整个文字的奇偶性。
2. 由于是比较第i个字符与第n-i-1个字符（这里是以数组游标来计算的i，即i从0开始），那么用栈解决无疑是最合适的方式。

2.栈的构建

使用栈那么一共需要栈的init()， push()， pop()方法，笔者在这使用的是链式栈来解决问题，读者有兴趣也可以考虑使用顺序栈实现。
考虑到可能会有数据结构的初学者，所以这里简单讲解下链栈的工作模式：

1. 栈是只允许在一端进行插入或删除的线性表，栈的一个明显的操作特性是先进后出（first in last out， FILO）。
2. 链栈的push()方法就是在栈的顶部对该单链表进行前插操作，如图所示：
   
3. 链栈的pop()方法就是删除top所指向的结点，如图所示：
   
   相应链栈的构建代码如下所示：

typedef struct SNode {
    
    char data;  // 数据域
    struct SNode *next;  // 指针域
}SNode, *SLink;

typedef struct LinkStack {
    
    SLink top;  // 栈顶指针
    int count;  // 栈中结点个数
}LinkStack;

/**
 * 初始化链式栈
 * param: S(需要操作的链栈)
 */ 
void initStack(LinkStack *&S) {
    
    S = (LinkStack *)malloc(sizeof(LinkStack));
    S->top = (SNode *)malloc(sizeof(SNode));
    
    S->top->next = NULL;
    S->top = NULL;
    S->count = 0;
}

/**
 * 向栈中加入数据
 * param: *S(需要操作的栈), elem(向栈中添加的元素)
 * return: true(操作成功)
 *         false(操作失败)
 */ 
bool push(LinkStack *S, char elem) {
    
    SLink node = (SLink)malloc(sizeof(SNode));  // 创建新结点
    node->data = elem;
    node->next = S->top;
    S->top = node;
    S->count++;
    return true;
}

/**
 * 弹出栈顶元素
 * param: *S(需要操作的栈), &elem(弹出的第一个元素)
 * return: true(操作成功)
 *         false(栈为空)
 */ 
bool pop(LinkStack *S, char &elem) {
    
    
    //空栈
    if(S->top == NULL) {
    
        return false;
    }

    elem = S->top->data;
    SNode *node = S->top;  // 工作指针
    S->top = S->top->next;
    free(node);
    S->count--;
    return true;
}

3.判断回文数方法

3.1 数组的输入

之前在第一部分的时候提到了，回文数判断的核心在于判断该数组的奇偶性，那么对整个数组的长度的把握至关重要。由于C/C++不像python一样有内置的len()函数，所以在计算数组长度的时候有些许麻烦。笔者在编码过程中是手动键入数组每个数的，所以通过判断输入的次数来记录长度。若读者是采用直接ElemType arr[] = {}这种方式创建数组，则可以采用int len = sizeof(arr) / sizeof(arr[0]);这种方式计算。

/**
 * 键入数组, 键入*或者一共键入MaxSize个字符停止
 * param: &arr[](需要操作的数组)
 * return: length(数组长度)
 */ 
int enter_array(char arr[]) {
    
    char c;
    int length = 0;
    for (int i = 0; i < MaxSize; i++) {
    
        cin>>c;
        if (c == '*') {
    
            break;
        }
        arr[i] = c;
        length++;
    }
    return length;
}

3.2 回文数方法

前面已经完成了相应的铺垫工作，现在开始进入正题。
首先，最开始提到过，回文数是判断一个数组的左右是否对称，那么我们只需要考虑将数组前半段压入栈中，即从int i = 0循环到i < length / 2。
有的读者可能会有疑问，在C/C++中整型相除若产生浮点数，那么会省略结果的小数点之后的值，即向下取整，为什么这里还使用length / 2？因为之前也提到过，一串奇数个字符是否为回文数，与其正中间的字符毫无关系，所以这里可以大胆的使用i < length / 2。

// 将数组前半段入栈, 若length为奇数, 则向下取整
for (int i = 0; i < length / 2; i++) {
    
    push(S, arr[i]);
}

接着，就是我们要考虑数组的奇偶性的时候了，因为我们需要遍历整个数组的后半部分的数据，那么开始的起始位置就至关重要。
当字符数为奇数个时，起始位置为length / 2 + 1，当字符数为偶数个时，起始位置为length / 2。
至于为何为这两个值，笔者画了个图进行说明，红色表明的部分为数组应该开始遍历的起始位置。

// 判断数组奇偶性
int start;  // 用于记录数组中的字符与栈中字符比较的起始位置
    
// 若数组为偶数
if (length % 2 == 0) {
    
        start = length / 2;
}
// 若数组为奇数
else {
    
    start = length / 2 + 1;
}

最后就只剩下判断数组遍历的字符与出栈的字符是否相等，若不相等，则不是回文数，若整个程序活到了遍历结束，那么就是回文数。

for (int i = start; i < length; i++) {
    
    char c;
    pop(S, c);
        
    // 若出栈的字符与arr[i]不等
    if (c != arr[i]) {
    
       return false;
    }
}
    
return true;

4.算法分析

1. 时间复杂度：整个算法虽然使用了两个for循环，但是分别遍历了数组的左右两侧，所以时间复杂度为O(n)。
2. 空间复杂度：整个算法使用了栈这种数据结构与一个数组，而栈只存入了至多一半的数组长度，所以空间复杂度为O(n + n / 2) = O(3n / 2)

5.整体代码与结果截图

#include <iostream>
using namespace std;

#define MaxSize 20

typedef struct SNode {
    
    char data;  // 数据域
    struct SNode *next;  // 指针域
}SNode, *SLink;

typedef struct LinkStack {
    
    SLink top;  // 栈顶指针
    int count;  // 栈中结点个数
}LinkStack;

/**
 * 初始化链式栈
 * param: S(需要操作的链栈)
 */ 
void initStack(LinkStack *&S) {
    
    S = (LinkStack *)malloc(sizeof(LinkStack));
    S->top = (SNode *)malloc(sizeof(SNode));
    
    S->top->next = NULL;
    S->top = NULL;
    S->count = 0;
}

/**
 * 向栈中加入数据
 * param: *S(需要操作的栈), elem(向栈中添加的元素)
 * return: true(操作成功)
 *         false(操作失败)
 */ 
bool push(LinkStack *S, char elem) {
    
    SLink node = (SLink)malloc(sizeof(SNode));  // 创建新结点
    node->data = elem;
    node->next = S->top;
    S->top = node;
    S->count++;
    return true;
}

/**
 * 弹出栈顶元素
 * param: *S(需要操作的栈), &elem(弹出的第一个元素)
 * return: true(操作成功)
 *         false(栈为空)
 */ 
bool pop(LinkStack *S, char &elem) {
    
    
    //空栈
    if(S->top == NULL) {
    
        return false;
    }

    elem = S->top->data;
    SNode *node = S->top;  // 工作指针
    S->top = S->top->next;
    free(node);
    S->count--;
    return true;
}

/**
 * 查看栈中元素
 * param: *S(需要操作的栈)
 */ 
void visit(LinkStack *S) {
    
    SLink node = S->top;
    while (node != NULL) {
    
        cout<<node->data<<"  ";
        node = node->next;
    }
    cout<<endl;
}

/**
 * 键入数组, 键入*或者一共键入MaxSize个字符停止
 * param: &arr[](需要操作的数组)
 * return: length(数组长度)
 */ 
int enter_array(char arr[]) {
    
    char c;
    int length = 0;
    for (int i = 0; i < MaxSize; i++) {
    
        cin>>c;
        if (c == '*') {
    
            break;
        }
        arr[i] = c;
        length++;
    }
    return length;
}

/**
 * 回文数判断
 * param: &S(需要操作的栈), arr[](需要判断的数组), length(数组长度)
 * return: true(是回文数), false(不是回文数)
 */ 
bool is_palindrome_number(LinkStack *&S, char arr[], int length) {
    
    initStack(S);

    // 将数组前半段入栈, 若length为奇数, 则向下取整
    for (int i = 0; i < length / 2; i++) {
    
        push(S, arr[i]);
    }

    // 判断数组奇偶性
    int start;  // 用于记录数组中的字符与栈中字符比较的起始位置
    
    // 若数组为偶数
    if (length % 2 == 0) {
    
        start = length / 2;
    }
    // 若数组为奇数
    else {
    
        start = length / 2 + 1;
    }

    // 回文数判断
    for (int i = start; i < length; i++) {
    
        char c;
        pop(S, c);
        
        // 若出栈的字符与arr[i]不等
        if (c != arr[i]) {
    
            return false;
        }
    }
    
    return true;
}

int main() {
    
    LinkStack *S;
    char arr[MaxSize];
    int length = enter_array(arr);
    
    if(is_palindrome_number(S, arr, length)) {
    
        cout<<"this array is a palindrome number"<<endl;
    } else {
    
        cout<<"this array is not a palindrome number"<<endl;
    }

    system("pause");
    return 0;
}