带有一个外部指针的链接节点的循环链

Question

我被要求编写一个基于链接的队列实现，该队列使用一个循环链接的节点链来表示队列中的元素。

也只使用一个尾指针，像这样:图14

我所面临的问题是，我不能将后节点指针连接到第一个，因为我只允许使用单个尾指针。

我正在使用的类:

#include "Queue.h"
#include "Node.h"
template<class T>
class CircularLinkedQueue : public Queue<T> {
private:
    Node<T>* back;
    int length;
public:
    CircularLinkedQueue();
    virtual ~CircularLinkedQueue();
    bool isEmpty() const;
    bool enqueue(T* element);
    T* dequeue();
    T* peek() const;
};

我遇到问题的代码行:

back->setNext(??);     // How do I connect it to the front?

请帮我指出正确的方向，我一直在寻找类似的东西，但我找不到任何东西。谢谢你！

Answer 1

当你在列表末尾添加一个节点时，只需将其指向第一个节点本身，例如

T* enqueue(T* element){
if(Queue == NULL){
element.setNext(element);
return element;}
T* cur=queue;
while(cur->next != queue)cur=cur->next;
cur->next=element;
element->next=queue;
return queue;}

这段代码的作用就是当输入一个新元素时它会改变刚刚添加的元素的指针指向队列的起点也就是根元素注意我是从后面插入元素的

Answer 2

在有一个指向队列尾部的外部指针的循环链接队列中，队列中的每个节点都应该有一个data组件和一个next组件。

使用一个指向队列尾部的外部指针的好处是，您可以立即访问队列的尾部和前部。

要访问队列的前端，使用外部指针访问后节点的"next"组件。如下:nodePtr front = back->next;

现在您有一个指向队列前面的外部指针(nodePtr)。