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

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

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!

Quote:

---

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 :)

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

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>
{
    // ...
};

---

Hey that's a pretty cool idea, cheers Elysia :)