哪种队列衍生数据类型可实现最快字符串回文校验？Deque性能是否更优？

适合做回文校验的队列衍生数据类型 #

由队列衍生的双端队列（Deque，全称为Double Ended Queue） 是实现回文校验的最优选择，它支持在队列的头尾两端进行O(1)时间复杂度的元素增删操作，刚好匹配回文校验逐次比对首尾对称字符的需求，实现逻辑简洁且效率上限最高。

ArrayDeque与普通数组/链表实现队列的性能对比 #

你现有的认知是正确的：不论是ArrayDeque、普通数组实现的队列还是链表实现的队列，完成回文校验的最坏时间复杂度都是O(n)（n为字符串长度），毕竟需要遍历完所有字符完成对称比对才能得出最终结论，时间复杂度层面不会有数量级的差异。

但在实际运行的常数时间损耗上，ArrayDeque的表现明显优于另外两种实现，核心原因如下：

• 对比链表实现的队列：ArrayDeque基于连续内存的循环数组实现，没有链表节点的额外对象开销和指针寻址消耗，CPU缓存命中率更高，首尾操作的常数级损耗更低
• 对比普通数组实现的队列：普通数组队列通常存在假溢出问题，要么需要额外做数据搬移，要么需要手动实现循环队列逻辑处理索引边界，而ArrayDeque本身就是官方做过大量优化的循环数组实现，自动处理扩容和索引计算，没有额外的逻辑开销

参考实现示例（Java） #

public static boolean checkPalindrome(String input) {
    Deque<Character> charDeque = new ArrayDeque<>();
    for (char c : input.toCharArray()) {
        charDeque.offerLast(c);
    }
    while (charDeque.size() > 1) {
        // 同时取出首尾字符比对
        if (charDeque.pollFirst() != charDeque.pollLast()) {
            return false;
        }
    }
    return true;
}

内容的提问来源于stack exchange，提问作者Happy_Coding