Template Queue File using link list

reliops14 · #1 02-May-2005, 21:41

well here is my whole header file this is the only part im having trouble with.
Also the header file is from a C++ book called "Problem Solving with C++: The Object of Programming" by Walter Savitch;

heres the header file..

CPP / C++ / C Code:

#ifndef QUEUE_H
#define QUEUE_H
namespace queuesavitch
{
	template<class T>
    class QueueNode
	{	
		T data;
        QueueNode *link;
    };
[b]	template<typename T>
	typedef QueueNode* QueueNodePtr;[/b]

	template<class T>
    class Queue
    {
    public:
        Queue();
        //Initializes the object to an empty Queue

        Queue(const Queue& aQueue);

        ~Queue();

        void add(T item);
        //Postcondition: item has been added to the back of the queue

        T remove();
        // Precondition: queue is not empty
        // Returns the item at the front of the queue and removes that
        // item from the queue.

        bool empty() const;
        // Returns true if the queue is empty. Returns false otherwise.

    private:
		QueueNodePtr front; // Points to the head of a linked list.
			                 // Items are removed from the head.
		QueueNodePtr back;  // Points to the node at the other end of
                            // linked list. Items are added at this end.
    };

} //queuesavitch

#endif //QUEUE_H

the problem is with the typedef QueueNode* QueueNodePtr;

dont know how to get around that since template typedefs arnt allowed.
thank you.

LuciWiz · #2 03-May-2005, 04:20

Well, let's just look at how they do this in the STL:

CPP / C++ / C Code:

//Taken from xutility
		// TEMPLATE CLASS iterator
template<class _Category,
	class _Ty,
	class _Diff = ptrdiff_t,
	class _Pointer = _Ty *,
	class _Reference = _Ty&>
		struct iterator
	{	// base type for all iterator classes
	typedef _Category iterator_category;
	typedef _Ty value_type;
	typedef _Diff difference_type;
	typedef _Diff distance_type;	// retained
	typedef _Pointer pointer;
	typedef _Reference reference;
	};

So, we can achieve this by encapsulating the typedef in a struct or class.
Which leads us to:

CPP / C++ / C Code:

	template<class T>
	class QueueNode
	{  
		T data;
		QueueNode *link;
	};

	template<typename T> 
	struct QueueNodePtr
	{
		typedef QueueNode<T> * Ptr;
	};

Of course, we could consider a flaw the fact that now we need to access the defined type trough the struct. But that's how they do it in the STL too:

CPP / C++ / C Code:

int main()
{
	Queue <int> queueNode;
	QueueNodePtr<int>::Ptr pt;
// STL version	
	std::vector<int> stl_vector;
	std::vector<int>::iterator stl_iter;
}

Best regards,
Lucian

reliops14 · #3 03-May-2005, 11:07

Well its not just the typedef thats the problem... its getting around where at the bottom under the private of class Queue

CPP / C++ / C Code:

	template<class T>
    class Queue
    {
    public:
        Queue();
        //Initializes the object to an empty Queue

        Queue(const Queue& aQueue);

        ~Queue();

        void add(T item);
        //Postcondition: item has been added to the back of the queue

        T remove();
        // Precondition: queue is not empty
        // Returns the item at the front of the queue and removes that
        // item from the queue.

        bool empty() const;
        // Returns true if the queue is empty. Returns false otherwise.

    private:
		QueueNodePtr front;
		QueueNodePtr back;
		
	};

Those are used to make new nodes and add to the list and have no clue how to work around it.

reliops14 · #4 03-May-2005, 19:39

Ok thank you for your help I solved the problem instead of using two classes one holding the link list and one the queue functions I just combined them all into one class. Works flawlessly now.

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Airport Log program using 3D linked List : problem reading from file	batrsau	C Programming Language	11	29-Feb-2008 07:44
[Include] Doubly-linked List	dsmith	C Programming Language	6	14-Apr-2006 13:12
search linked list	itsmecathys	CPP / C++ Forum	20	18-Apr-2005 01:34
Yet another CD burner problem: Lite-On LSC-24082K	Erwin	Computer Hardware Forum	1	22-May-2004 11:28