C++ 数据结构：用链表实现队列

概述

此前我们已用数组实现了队列。本文将使用链表来实现队列。使用链表的优点是：动态增长，扩容时更加平滑。缺点是：略微复杂，需要额外管理所有节点。队列相关的操作，仍然是下面 6 个接口。

• Enqueue：向队尾添加一个元素。
• Dequeue：从队首移除顶部元素，并返回该元素。
• Front：查看队首元素，但不移除它。
• Rear：查看队尾元素，但不移除它。
• IsEmpty：检查队列是否为空。
• Size：获取队列中元素的数量。

实现原理

我们使用一个带头指针和尾指针的单链表来实现队列。其中，头指针对应链表的头部，尾指针对应链表的尾部。入队操作在尾部插入新节点，出队操作从头部删除节点。所有操作均维护头指针和尾指针的正确性，确保队列行为符合 FIFO 规则。

在下面队列 CLinkedListQueue 的实现中，我们声明了两个成员变量 m_pFront 和 m_pRear。m_pFront 代表队首，m_pRear 代表队尾。

class CLinkedListQueue {
public:
    CLinkedListQueue();
    ~CLinkedListQueue();
    void Enqueue(int nValue);
    int Dequeue();
    int Front();
    int Rear();
    bool IsEmpty();
    int Size();
private:
    struct Node {
        int nData;
        Node* pNext;
    };
    Node* m_pFront;
    Node* m_pRear;
};

Enqueue 操作

入队就是在链表的尾部插入一个新节点，详细步骤如下。

1. 创建一个新节点。
2. 如果队列为空，将 m_pFront 和 m_pRear 都指向新节点。
3. 如果队列非空，将当前尾节点 m_pRear 的 pNext 指向新节点 pNode，并更新尾指针为 pNode。

具体如何实现，可参考下面的示例代码。

  {
    Node* pNode =  ();
    pNode->nData = nValue;
    pNode->pNext = ;
     (()) {
        m_pFront = m_pRear = pNode;
    }  {
        m_pRear->pNext = pNode;
        m_pRear = pNode;
    }
}