回文是指正读和反读均相同的字符序列，如”abba”和”abdba”均是回文，但”good”不是回文，试写一算法利用栈判定给定的字符序列是否为回文。（提示：将一半字符入栈）

1. 将字符序列的前一半依次入栈，直到栈顶为序列的中间字符。
2. 如果序列长度为奇数，忽略中间字符。
3. 依次取出栈中的字符与序列的后一半进行比较，如果相同则继续比较下一个字符，否则该序列不是回文。
4. 如果栈中的字符全部取出并比较完毕，且都与序列的后一半相同，则该序列为回文。

以下是 Python 代码实现：

def is_palindrome(s):
    stack = []
    length = len(s)
    mid = length // 2
    # 将前一半字符入栈
    for i in range(mid):
        stack.append(s[i])
    # 如果序列长度为奇数，忽略中间字符
    if length % 2 != 0:
        mid += 1
    # 依次取出栈中的字符与序列的后一半比较
    for i in range(mid, length):
        if stack.pop() != s[i]:
            return False
    return True

测试：

>>> is_palindrome('abba')
True
>>> is_palindrome('abdba')
True
>>> is_palindrome('good')
False

相关问题

回文是指正读、反读均相同的字符序列，如"abba"和“abdba”均是回文。“good”不是回文。试设计算法判定给定的字符序列是否是回文

一个简单的判断回文的算法如下：

1. 从字符串的两端分别开始遍历，判断每个字符是否相等。

2. 如果在遍历过程中发现任何不相等的字符，就说明这个字符串不是回文。

3. 当左右两端的遍历相遇时，就说明这个字符串是回文。

下面是算法的Python代码实现：

def isPalindrome(s):
    i, j = 0, len(s) - 1
    while i < j:
        if s[i] != s[j]:
            return False
        i += 1
        j -= 1
    return True

这个算法的时间复杂度是$O(n)$，其中$n$是字符串的长度。

回文是指正读、反读均相同的字符序列,如“abba”和“abdba”均是回文,但“good”不是回文。试设计算法判定给定的字符序列是否为回文。(提示:用顺序栈完成)

判断一个字符序列是否为回文的一种简单方法是使用顺序栈（也称为LIFO栈，Last In First Out）。以下是步骤：

1. 创建一个空的顺序栈。
2. 遍历输入序列的一半。将从前往后的字符依次压入栈中。
3. 再次遍历输入序列的另一半，但是从后往前，即从最后一个元素开始。
4. 每次从输入序列取出一个字符并与栈顶元素比较。如果两者相等，则继续；如果不等，说明序列不是回文，返回false。
5. 如果遍历完一半且所有字符都匹配，说明输入序列是回文，返回true。

伪代码示例：

def isPalindrome(s):
    stack = []
    for char in s[:len(s)//2]:  # 只取前半部分字符入栈
        stack.append(char)
    
    for i in range(len(s)//2):  # 对比后半部分与栈顶元素
        if s[-i - 1] != stack.pop():  # 当前字符与栈顶字符不符则返回False
            return False
    
    return True  # 所有字符匹配，序列是回文