回文指的是一个字符串从前面读和从后面读都一样,如"abcba"、"123454321"都是回文。设计一个算法利用顺序栈的基本运算判断一个字符串是否为回文,并用相关数据进行测试。
时间: 2024-10-09 10:15:48 浏览: 20
为了判断一个字符串是否是回文,我们可以使用两个指针,一个从字符串的开始位置(头部),另一个从结束位置(尾部)向中间移动。同时,我们还需要一个顺序栈来辅助这个过程。
以下是算法步骤:
1. 创建一个空栈(Stack)用于存储字符。
2. 将第一个字符压入栈中。
3. 比较头部和尾部的字符。如果它们相等,将头部字符移至尾部继续比较;如果不相等,则该字符串不是回文,直接返回false。同时,头部右移一位,尾部左移一位。
4. 如果所有字符都进行了正确的头尾对比且相等,说明字符串是回文,返回true。
以下是Python版本的代码示例:
```python
def is_palindrome(s):
stack = []
for char in s:
stack.append(char)
# 双指针法
left, right = 0, len(s) - 1
while left < right:
if stack.pop() != s[right]:
return False
right -= 1
return True
# 测试数据
test_cases = ["abcba", "123454321", "hello", "madam"]
for case in test_cases:
print(f"{case} 是回文吗?{is_palindrome(case)}")
```
在这个代码里,`is_palindrome`函数会打印出每个测试字符串是否是回文的结果。
阅读全文