lalaman lalaman - 1 month ago 9
C++ Question

C++ Queue from Linked List

Good evening. I have been trying to implement a Queue class in C++, taking a previously created Linked List class as a base.
Linked Linked List:

#include <cstddef>
#include <iostream>
#include <cstdio>

using namespace std;

template <class T>
class LinkedList {

public:
LinkedList() {
head = NULL;
}
~LinkedList() {
MakeEmpty();
}

struct Node {
T value;
Node *next;
};

Node* getHead() {
return head;
}

void Print();
void Insert();
void MakeEmpty();

private:
Node *head; // Head of the linked list.
};


Queue class:

#include "LinkedList.h"

template <class T>
class Queue {

public:
Queue() {
LinkedList<T>::Node *tnode = Q.getHead();
}

~Queue() {
Q.MakeEmpty();
}

void Enqueue( T x ) {
LinkedList<T>::Node *cnode = Q.getHead();

//Find the last element of Q
while( cnode -> next != NULL ) {
cnode = cnode -> next;
}
//Add x to the end of the queue
Q.Insert( x );
}

void Dequeue() {
LinkedList<T>::Node *hnode = Q.getHead();
//Rest of function
}

void Print() {
Q.PrintList();
}

private:
LinkedList<T> Q;
};


As you probably noticed, I am making them template classes. When compiling, I am told that tnode (found in the constructor of the Queue class) has not been declared in the scope. Any suggestions on how to fix this?

EDIT 1: The error message that I am getting is:


RCQueue.h: In constructor ‘Queue::Queue()’:

RCQueue.h:8:28: error: ‘tnode’ was not declared in this scope
LinkedList::Node *tnode = Q.getHead();


The main purpose of my constructor is to initialize the "head" pointer from the LinkedList class as NULL. I was also curious as to how one could go about declaring a variable of a structure that was declared in another template class.

Answer

You need typename in front of every use of the Node type in LinkedList that you reference within Queue because its dependent on the template parameter T. In specific,

template <class T>
class Queue {

public:
    Queue() {
        typename LinkedList<T>::Node *tnode = Q.getHead();
    }

    ~Queue() {
        Q.MakeEmpty();
    }

    void Enqueue( T x ) {
        typename LinkedList<T>::Node *cnode = Q.getHead();

        //Find the last element of Q
        while( cnode -> next != NULL ) {
            cnode = cnode -> next;
        }
        //Add x to the end of the queue
        Q.Insert( x );
    }

    void Dequeue() {
        typename LinkedList<T>::Node *hnode = Q.getHead();
        //Rest of function
    }

    void Print() {
        Q.PrintList();
    }

private:
    LinkedList<T> Q;
};

Notice the addition of typename before the uses of LinkedList<T>::Node.

Of course you'll also hear complaints about the missing definition of MakeEmpty() within LinkedList that is called in your Queue class, so just add a definition for it.

For more information on why typename is needed, this post explains its pretty clearly.

Comments