基于链表实现无STL的Deque：首尾元素交换函数故障排查

问题分析 #

你的swap函数逻辑完全偏离目标，没有正确处理首尾节点的指针关系，反而做了无意义的遍历和指针赋值，直接破坏了队列的结构。比如原函数中tmp_head和tmp_rear只是指向原首尾节点的指针，修改它们的属性等同于直接修改原节点，后续的循环和指针赋值更是彻底打乱了队列的前后连接关系。

正确实现思路 #

交换首尾元素需要覆盖三种场景：

• 队列为空：已处理
• 队列只有1个元素：无需交换（首尾是同一个节点）
• 队列有2个及以上元素：需要调整首尾节点与相邻节点的指针，交换首尾节点自身的前后指针，最后更新队列的首尾标识

修正后的swap函数代码 #

void swap() 
{
    if (isEmpty())
    {
        cout << "Deque is empty";
        return;
    }
    // 只有一个元素时无需交换
    if (pFront == pRear)
    {
        return;
    }

    Node* frontNode = pFront;
    Node* rearNode = pRear;

    // 获取首尾节点的相邻节点
    Node* frontNext = frontNode->pNext;
    Node* rearPrev = rearNode->pPrev;

    // 处理首节点下一个节点的prev指针
    if (frontNext != nullptr)
    {
        frontNext->pPrev = rearNode;
    }
    // 处理尾节点上一个节点的next指针
    if (rearPrev != nullptr)
    {
        rearPrev->pNext = frontNode;
    }

    // 手动交换首尾节点的prev指针（不依赖STL）
    Node* tempPrev = frontNode->pPrev;
    frontNode->pPrev = rearNode->pPrev;
    rearNode->pPrev = tempPrev;
    // 手动交换首尾节点的next指针（不依赖STL）
    Node* tempNext = frontNode->pNext;
    frontNode->pNext = rearNode->pNext;
    rearNode->pNext = tempNext;

    // 更新队列的首尾指针
    pFront = rearNode;
    pRear = frontNode;
}

代码解释 #

1. 特殊情况处理：先判断空队列和单元素队列，直接返回避免无效操作。
2. 保存关键节点：提前获取首节点的下一个节点、尾节点的上一个节点，避免指针修改后丢失引用。
3. 调整中间节点连接：让首节点的下一个节点指向尾节点，尾节点的上一个节点指向首节点，确保链表中间部分的连接不中断。
4. 交换首尾节点自身指针：手动交换两个节点的pPrev和pNext，确保它们各自的前后指向正确。
5. 更新队列首尾标识：将pFront改为原尾节点，pRear改为原首节点，完成首尾位置的交换。

测试验证 #

你的main函数中，依次执行pushFront(1)、pushFront(2)、pushFront(3)后，初始队列输出为3 2 1；调用修正后的swap函数后，输出变为1 2 3，完全符合交换首尾元素的预期。

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