编写一个算法函数，使用链栈或队列，判定给定的字符序列是否为回文，并验证。 提示：回文是指正读和反读均相同的字符序列。要有输入。

编写一个算法函数判断字符序列是否为回文，可以使用链栈或双端队列（deque）来辅助操作。这里提供一个使用Python实现的例子，使用队列（deque）因为它的`append()`和`popleft()`操作在两端都能快速插入和删除元素，非常适合处理回文。

from collections import deque

def is_palindrome(s):
    # 将字符串转换为小写并移除非字母数字字符
    s = ''.join(c for c in s.lower() if c.isalnum())
    
    # 使用双端队列存储字符，同时比较两端字符
    queue = deque(s)
    while len(queue) > 1:
        if queue.popleft() != queue.pop():
            return False
    
    return True

# 测试示例
input_str = "A man, a plan, a canal: Panama"
print(is_palindrome(input_str))  # 输出: True

# 相关问题--
1. 这个算法的时间复杂度是多少？
2. 如果不使用队列，如何使用链栈实现同样的功能？
3. 输入为空字符串时，这个函数会返回什么结果？