实现队列是否必须依赖带前驱（previous）指针的双向链表？

基础FIFO（先进先出）队列的合规实现完全不强制依赖双向链表，仅靠单链表结构就可以实现全部核心操作，且能保持所有操作的O(1)时间复杂度。

单链表实现队列的核心逻辑 #

你之前的认知误区来自一个默认假设：单链表只能维护一个指向链表头部的追踪指针。实际上我们完全可以在不修改节点结构（即不给每个节点添加指向前驱的previous指针）的前提下，额外给链表结构本身新增两个独立的状态指针，就能兼顾队列两端的操作效率：

• front（队头指针）：固定指向单链表的第一个节点，专门承载dequeue()出队逻辑。执行出队时，只需要把front指针移动到当前头节点的后继节点，完成原头节点的内存释放即可，全程无需遍历链表。
• rear（队尾指针）：固定指向单链表的最后一个节点，专门承载enqueue()入队逻辑。执行入队时，只需要把当前队尾节点的next指针指向新建的入队节点，再把rear指针移动到这个新节点上即可，同样无需遍历链表。
• 仅需要处理两个边界特殊场景就能保证实现正确性：队列从空状态执行第一次入队时，要同步把front和rear指针指向这个唯一的新节点；出队操作把队列清空时，要同步把front和rear指针置空，避免悬空的无效指针。

很多人误以为单链表无法实现高效队列，本质是实现时偷懒没有维护独立的队尾指针，每次入队都要从头遍历到链表尾部定位最后一个节点，把这种O(n)的低效设计错误归因为单链表本身的结构限制。

双向链表在队列场景的定位 #

双向链表从来不是队列实现的必选项，它只是适配了更多超出基础FIFO能力的扩展需求：

• 当需要实现双端队列（Deque），同时支持在队列的两端灵活执行入队、出队操作时，双向链表的结构会更有优势，能让两端的操作都保持稳定的O(1)复杂度。
• 当需要在队列的任意中间位置删除节点、反向遍历队列这类场景时，双向链表才能提供足够的遍历灵活性，但这类功能不属于基础合规队列的要求范畴。

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