Thread: Queue with templates

  1. #1
    Registered User
    Join Date
    May 2008
    Location
    Australia
    Posts
    230

    Queue with templates

    So I've been designing a queue. I finished the base of it and implemented templates. The reason I started this project was to learn about templates, and get some more practice in this area and others such as pointers and linked-lists. So I have no idea if I'm doing it correctly really. It seems to work, but theres a few problems. Firstly if I create a Queue object of type <char> like so:

    Code:
    Queue<char> q;
    I can't pass in a character in this format:

    Code:
    q.pop('a');
    It needs to be like this:

    Code:
    q.pop("a");
    Yes, ' ' is for characters, " " is for strings, so why won't it let me use ' '? I'm thinking that I maybe should change it so that pop only accepts a reference to something, so that would eliminate the risk of that (I'm just guessing to be honest).

    Another thing, if I specify a string like such:

    Code:
    q.pop("Hello");
    It only pops the first letter of that string. So the output would be H. But if I declare the type of the object <string>, and use the <string> library, then it will print a whole string . So those are the problems I have so far, but I also have a question. You see, the return type of pop is a pointer of type T, so, I obviously need to assign the returned pointer to my own pointer to get the values of the returned pointer. The thing is, I don't know of a way to match the type of my pointer to the type of the Queue object without doing it manually in the declaration of my pointer. I'll give an example because it's not a great explanation:

    Code:
    int main() {
    	Queue<float> q;
    	float * data = 0;
    	q.push(3.5);
    	q.push(2.7);
    	q.push(1.5);
    	q.push(6.5);
    	while (q.getCount() > 0) {
    	float * data = q.pop();
    	cout << *data << endl;
    	}
    }
    See how I've declared a pointer named data, that points to type float? Well, it would be a lot more convenient for me (I'm not sure if this is even possible yet) if I could have it as a pointer to return type of the same as Queue, which in this example is float. So instead of float * data = 0;, Is there a way to make it something like "Queues-template-type * data" so I don't have to specify what return type the data pointer holds? Anyways I'm not great at explaining this stuff :P So hopefully you know what I'm talking about. Here's the rest of the code.

    Code:
    #include <iostream>
    #include <string>
    
    using std::cin;
    using std::cout;
    using std::endl;
    using std::string;
    
    template <class T>
    class Node {
    public:
    	T * data;
    	Node<T> * next;
    	Node<T> * prev;
    	Node();
    };
    
    template <class T>
    class Queue {
    public:
    	Queue();
    	~Queue();
    	void push(T data);
    	void push(T * data);
    	T * pop();
    	inline int getCount() { return count; }
    
    private:
    	Node<T> * head;
    	Node<T> * tail;
    	Node<T> * forward;
    	Node<T> * backward;
    	int count;
    };
    
    template <class T>
    Node<T>::Node() {
    	next = NULL;
    	prev = NULL;
    	data = new T;
    }
    
    template <class T>
    Queue<T>::Queue() {
    	head = NULL;
    	tail = NULL;
    	forward = NULL;
    	backward = NULL;
    	count = 0;
    }
    
    template <class T>
    Queue<T>::~Queue() {
    	Node<T> * n = tail;
    	Node<T> * del;
    	while ( n ) {
    		del = n;
    		n = n->prev;
    		delete del;
    	}
    }
    
    template <class T>
    void Queue<T>::push(T data) {
    	push(&data);
    }
    
    template <class T>
    void Queue<T>::push(T * data) {
    	if (!head) {
    		head = new Node<T>;
    		*head->data = *data;
    		head->next = NULL;
    		head->prev = NULL;
    		tail = head;
    	}
    	else {
    	tail->prev = tail;
    	tail->next = new Node<T>;
    	tail = tail->next;
    	*tail->data = *data;
    	tail->next = NULL;
    	}
    	count++;
    }
    
    template <class T>
    T * Queue<T>::pop() {
    	if (head == NULL) {
    		return 0;
    	}
    	else if (head == tail->prev) {
    		T * data = head->data;
    		delete head;
    		count--;
    		return data;
    	}
    	else {
    		T * data = head->data;
    		head = head->next;
    		count--;
    		return data;
    	}
    };
    
    int main() {
    	Queue<float> q;
    	float * data = 0;
    	q.push(3.5);
    	q.push(2.7);
    	q.push(1.5);
    	q.push(6.5);
    	while (q.getCount() > 0) {
    	float * data = q.pop();
    	cout << *data << endl;
    	}
    }
    Any suggestions/advice is welcome, like I said, I'm not familiar with templating, so I'm not certain that I'm doing it correctly (although it does work which is promising).

    Thanks a lot!

    Edit: Oh and if you're around here Laserlight you'll see that I implemented a linked-list, not sure if you remember but you gave me that suggestion not long ago hehe
    Last edited by pobri19; 09-23-2008 at 03:42 AM.
    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Hmm. What compiler are you using? gcc-mingw 3.4.2 does it fine when I added:
    Code:
        Queue<char> qc;
        char c = 'b';
        qc.push('a');
        qc.push(c);
    
        
        while (qc.getCount() > 0) {
    	char * data = qc.pop();
    	cout << *data << endl;
        }
    However, I don't really see the point of:
    1. returning a pointer to the data - just return the data itself, and either throw an exception or issue an error message if you try to pop an empty queue.

    2. Storing the data as a pointer.

    3. Forward/Backwatrd node pointers - never used for anything.

    Further, your pop() function does not set head to NULL when it's taken the last element of the list. If you remove the "if (head == tail->prev)" code, you will automatically set head to NULL when the list becomes empty. A consequences of that would be that you can simplify your node to not have a prev pointer [assuming you also rewrite the Queue destructor, since that sues the prev pointer, but if you start at head instead of tail, and go forward instead of backwards, that would be fine - only two things to change (with the added advantage that it will work fine for an empty list if you implement the bit of "set head to NULL when last pop" without further changes - otherwise you would also have to set tail to NULL when you remove the last element) ].

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    Registered User
    Join Date
    May 2008
    Location
    Australia
    Posts
    230
    Hmmm you're right matsp, that seems to work for me now >< Not sure what happened before. Anyways I'll change those things you mentioned Anyways I'm still open for more suggestions by the way if anyone else wants to chime in!
    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Oh and if you're around here Laserlight you'll see that I implemented a linked-list, not sure if you remember but you gave me that suggestion not long ago hehe
    I forgot to mention that to implement a queue with a linked list, you only need a singly linked list that keeps track of its tail
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    What my comments suggest is that you need some more test-code as well, such as deleting all objects, then adding a new one, then deleting the queue. Destroying an empty queue as well as destroying one that has some content would also be good things to do.

    Pushing a number of elements and then popping all but the last, then pushing a few more onto the queue, etc.

    By the way, the suggestion to remove the pointer for pop simplifies things if want to calculate using the results, as you can then do [code]
    res = q.pop() + q.pop();
    [/quote]

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  6. #6
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    If you want more control, you can use policy classes/structs.
    Say:

    Code:
    template<typename T> struct ReturnPolicy
    { typedef ReturnType T*; };
    
    template<> struct ReturnPolicy<float>
    { typedef ReturnType float; };
    
    template<typename T> class Queue
    {
        typename ReturnPolicy<T>::ReturnType pop();
        // etc
    };
    Of course, you can also load some policy classes with functions and inherit from it:

    Code:
    template<typename T> class PushPolicy
    {
    public:
        void push(T value);
    };
    
    template<> class PushPolicy<char>
    {
    public:
        void push(T value);
        void push(T* value);
    };
    
    template<typename T> class Queue: public PushPolicy<T>
    {
        // ...
    };
    Last edited by Elysia; 09-23-2008 at 04:56 AM.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  7. #7
    Registered User
    Join Date
    May 2008
    Location
    Australia
    Posts
    230
    Hey that's a pretty cool idea, cheers Elysia
    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help with FIFO QUEUE
    By jackfraust in forum C++ Programming
    Replies: 23
    Last Post: 04-03-2009, 08:17 AM
  2. Questions about Templates
    By Shamino in forum C++ Programming
    Replies: 4
    Last Post: 12-18-2005, 12:22 AM
  3. help with queues
    By Unregistered in forum C Programming
    Replies: 3
    Last Post: 05-21-2002, 09:09 PM
  4. help with queues
    By Unregistered in forum C Programming
    Replies: 3
    Last Post: 05-21-2002, 11:39 AM