队列-链式描述（C++）

定义

使用链表描述队列时，通常包含以下几个基本要素：

1. 队头指针（Front Pointer）：指向队列中第一个（即最早进入队列的）元素的节点。
2. 队尾指针（Rear Pointer）：指向队列中最后一个（即最近进入队列的）元素的节点。
3. 节点（Node）：每个节点包含数据域和指向下一个节点的指针。

队列的基本操作包括：

• 入队：在队尾添加新元素。
• 出队：移除队头元素。
• 查看队头元素：获取队头元素但不移除它。
• 检查队列是否为空：判断队头指针是否为空或者判断size是否为0。

抽象类queue

template<typename T>
class queue
{
public:
    virtual   ~queue(){}
    virtual bool empty() const = 0;
    virtual int size() const = 0;
    virtual T& font() const = 0;
    virtual T& back() const = 0;
    virtual void push(const T& theElement) const = 0;
    virtual void pop() = 0;
};

派生类linkQueue

template<typename T>
class linkQueue : public queue<T>
{
public:
    linkQueue();
    ~linkQueue();
    bool empty() const;
    int size() const;
    T &font() const;
    T &back() const;
    void push(const T &theElement);
    void pop();

private:
    linkNode<T>* fontNode;
    linkNode<T>* backNode;
    int queueSize;
};

template<typename T>
linkQueue<T>::linkQueue()
{
    fontNode = nullptr;
    backNode = nullptr;
    queueSize = 0;
}

template<typename T>
linkQueue<T>::~linkQueue()
{
    while(!empty())
    {
        pop();
    }
}

template<typename T>
bool linkQueue<T>::empty() const
{
    return queueSize == 0;
}

template<typename T>
int linkQueue<T>::size() const
{
    return queueSize;
}

template<typename T>
T &linkQueue<T>::font() const
{
    assert(fontNode != nullptr);
    return *fontNode;
}

template<typename T>
T &linkQueue<T>::back() const
{
    assert(backNode != nullptr);
    return *backNode;
}

template<typename T>
void linkQueue<T>::push(const T &theElement)
{
    auto newNode = new linkNode<T>(theElement,nullptr);

    if(queueSize == 0)
    {
        fontNode = newNode;
    }
    else
    {
        backNode->next = newNode;
    }
    backNode = newNode;

    queueSize++;

}

template<typename T>
void linkQueue<T>::pop()
{
    assert(queueSize > 0);

    auto nextNode = fontNode->next;
    delete  fontNode;
    fontNode = nextNode;
    queueSize--;
}