判定给定的字符序列是否为回文(提示:将一半字符入栈)。
时间: 2024-10-14 09:11:07 浏览: 6
判断一个字符串是否是回文可以通过比较字符串的正序和反序来实现。一种简单的方法是使用双指针,一个从字符串开始,另一个从结尾开始,同时向前和后移动并检查对应位置的字符是否相同。另一种方法是使用栈,将字符串的一半字符依次压入栈中,然后逐个弹出并与另一半字符进行比较。
这里是使用栈的C++代码示例:
```cpp
#include <iostream>
#include <stack>
#include <string>
bool isPalindrome(const std::string& str) {
std::stack<char> stack;
// 将前一半字符推入栈中
for (size_t i = 0; i < str.length() / 2; ++i) {
stack.push(str[i]);
}
// 双指针,一个从开头,一个从末尾
size_t start = 0, end = str.length() - 1;
while (start < end) {
if (stack.empty() || stack.top() != str[end]) { // 如果栈为空或栈顶元素与末尾不同
return false;
}
stack.pop(); // 弹出栈顶元素
start++;
end--;
}
// 如果所有字符都匹配,返回true
return true;
}
int main() {
std::string test_str = "madam";
if (isPalindrome(test_str)) {
std::cout << test_str << " is a palindrome." << std::endl;
} else {
std::cout << test_str << " is not a palindrome." << std::endl;
}
return 0;
}
```