基于栈（stack）的回文判断程序：

代码实现

#include <iostream>
#include <stack>
#include <cctype>   // 用于 std::tolower
#include <algorithm> // 用于 std::remove_if

using namespace std;

bool isPalindrome(const string &s) {
    stack<char> charStack;
    string cleanedStr;

    // 预处理字符串：去除空格并转换为小写
    for (char c : s) {
        if (isalnum(c)) { // 只保留字母和数字
            cleanedStr += tolower(c);
        }
    }

    // 将字符串的前半部分压入栈
    int length = cleanedStr.length();
    for (int i = 0; i < length; i++) {
        charStack.push(cleanedStr[i]);
    }

    // 依次弹出栈顶字符并与原始字符串比较
    for (int i = 0; i < length; i++) {
        if (charStack.top() != cleanedStr[i]) {
            return false; // 若不匹配，则不是回文
        }
        charStack.pop();
    }

    return true; // 所有字符匹配，则是回文
}

int main() {
    // 测试用例
    cout << boolalpha;  // 让 `true` 和 `false` 以文字形式输出
    cout << isPalindrome("racecar") << endl;          // true
    cout << isPalindrome("hello") << endl;            // false
    cout << isPalindrome("madam") << endl;            // true
    cout << isPalindrome("A man a plan a canal Panama") << endl;  // true
    return 0;
}

代码解析

预处理字符串：
- 通过 isalnum(c) 过滤掉非字母数字字符（如空格、标点符号）。
- 统一转换为小写，避免大小写影响判断。
使用栈存储字符串：
- 依次将字符压入栈中。
依次比较栈顶元素和原字符串：
- 由于栈是 LIFO（后进先出） 结构，弹出时的顺序刚好是原字符串的反向顺序。
- 逐个比较栈顶字符和原字符串对应位置的字符，如果有不匹配的情况，则返回 false。
boolalpha 输出：
- 让 true/false 以 true 或 false 形式输出，而不是 1 或 0。

示例运行结果

true
false
true
true

在 C++ 中，使用 栈（stack） 虽然可以实现回文判断，但并不是最优的方法。
因为栈需要 额外的 O(n) 空间，而实际上我们可以 只使用双指针，节省空间，将 时间复杂度降到 O(n)，空间复杂度降到 O(1)。

最优解：双指针（O(n) 时间, O(1) 空间）

思路：

使用 两个指针，分别指向字符串的 起始和末尾。
依次比较

左指针和右指针

所指向的字符：
- 如果相同，则继续向中间移动。
- 如果不同，则直接返回 false。
如果所有字符都匹配，则返回 true。

实现

#include <iostream>
#include <cctype>  // 用于 std::tolower 和 std::isalnum

using namespace std;

bool isPalindrome(const string &s) {
    int left = 0, right = s.length() - 1;

    while (left < right) {
        // 跳过非字母数字字符
        while (left < right && !isalnum(s[left])) left++;
        while (left < right && !isalnum(s[right])) right--;

        // 转换为小写后进行比较
        if (tolower(s[left]) != tolower(s[right])) return false;

        left++;
        right--;
    }
    return true;
}

int main() {
    cout << boolalpha;  // 让 true 和 false 以文字形式输出
    cout << isPalindrome("racecar") << endl;          // true
    cout << isPalindrome("hello") << endl;            // false
    cout << isPalindrome("madam") << endl;            // true
    cout << isPalindrome("A man, a plan, a canal: Panama") << endl; // true
    cout << isPalindrome("No lemon, no melon") << endl; // true
    return 0;
}

代码解析

跳过无关字符：
- isalnum(s[left]) 和 isalnum(s[right]) 过滤掉 空格、标点符号等非字母数字字符。
- tolower(s[left]) 和 tolower(s[right]) 统一转换为小写，避免大小写影响。
双指针优化：
- 直接在原字符串上进行比较，不需要额外存储字符，节省 O(n) 空间。
- 只需 遍历一半 的字符串，时间复杂度仍然是 O(n)，但更高效。