队列-链式描述（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--;
}