回文是指正读反读均相同的字符序列，如“abb a”和“abdba”均是回文，但“good”不是回文。试写一个链栈算法判定给定的字符向量是否为回文。（提示：将一半字符入栈)

算法思路：

1. 先将字符向量的一半元素依次入栈；
2. 若字符向量长度为奇数，则将中间元素跳过；
3. 再将字符向量的另一半元素与栈中元素依次比较，若不相同则不是回文；
4. 若所有元素都比较相同，则是回文。

具体实现：

class Stack:
    def __init__(self):
        self.items = []

    def is_empty(self):
        return len(self.items) == 0

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()

    def peek(self):
        if not self.is_empty():
            return self.items[-1]


def is_palindrome(s):
    half = len(s) // 2
    stack = Stack()

    for i in range(half):
        stack.push(s[i])

    if len(s) % 2 == 1:
        half += 1

    for i in range(half, len(s)):
        if s[i] != stack.pop():
            return False

    return True


# 测试
print(is_palindrome("abdba"))  # True
print(is_palindrome("abb a"))  # True
print(is_palindrome("good"))  # False

时间复杂度：$O(n)$，其中 $n$ 为字符向量的长度。因为需要遍历一半字符入栈，再遍历一半字符与栈中元素比较，时间复杂度为 $n/2 + n/2 = O(n)$。