Now that you know the basics of templates and generics, you can start writing your own generic program. Now, let's implement our own Queue class template, implement some interfaces for the standard library queue class, and add some actions on our own.

1. Ideas

We implement Queue using a chain table. We define two classes: QueueItem and Queue. QueueItem stores the values of elements in Queue, and Queue stores two pointers to the head and end of the chain table.

2.QueueItem

Because QueueItem is just an auxiliary class for Queue, we don't want any code to use it except Queue, so QueueItem is a private class, all data members and excuses are private, so to make Queue available, we need to make Queue a friend of QueueItem.

template <typename Type> class QueueItem{
    template <typename T> friend class Queue;
    //Data Members
    Type item;
    QueueItem *next;
    //Constructor
    QueueItem(const Type &t): item(t), next(0) { }
};

Friend declaration note:

• The friend keyword follows the template and template parameter list
• The template parameter name after the typename in the friend declaration cannot be the template parameter name system after the typename in the QueueItem definition in the previous line, so one uses T and one uses Type here

If the Queue class has not been declared before, we can declare the friendship as above; if the Queue class has been declared before the QueueItem definition, we can also declare the friendship as follows:

friend class Queue<Type>;

Note that the Queue is followed by the need to specify that the template argument is the same Type as in the QueueItem definition.

2. Basic interface

First, we give the general framework of the Queue class template and several basic interfaces:

template <typename Type> class Queue{
    public:
        //Default constructor
        Queue(): head(0), tail(0), size_of_queue(0) { };
        //Replication Control Members
        Queue(const Queue &Q): head(0), tail(0), size_of_queue(0) { copy_elems(Q); }
        Queue &operator=(const Queue &);
        //Destructor
        ~Queue()；

         //Basic Operating Interface
         Type &front() { return head->item; }
        const Type &front() const { return head->item; }
        void push(const Type &);
        void pop();
        bool empty() { return head == 0; }
        int size() { return size_of_queue; }
    private:
        //Data members: chain head and end and chain size
        QueueItem *head;
        QueueItem *tail;
        int size_of_queue;
        //Two utility functions, one for destructors and one for replication control members
        void destroy() { while(!empty()) pop(); }
        void copy_elems(const Queue &);
};

3. Basic interface implementation

Below we implement some of the basic interfaces above outside the class definition:

template <typename Type> void Queue<Type>::pop()
{
    QueueItem *p = head;
    head = head->next;
    delete p;
    --size_of_queue;
}

template <typename Type> void Queue<Type>::push(const Type &it)
{
    QueueItem *p = new QueueItem(it);
    if(empty())
      head = tail = p;
    else{
        tail->next = p;
        tail = p;
    }
    ++size_of_queue;
}

template <typename Type> void Queue<Type>::copy_elems(const Queue &q)
{
    QueueItem *p = q.head;
    for( ; p; p = p->next)
      push(p->item);
    size_of_queue = q.size();
}

template <typename Type> Queue<Type> &Queue<Type>::operator=(const Queue &q)
{
    copy_elems(q);
    return *this;
}

4. Initialize Queue objects through iterators

To make our Queue more like a standard library queue, we then let the Queue class object be initialized by passing in a pair of iterators and define the assign function:

template <typename Type> class Queue{
    public:
        ...
         QueueItem<Type> *begin() { return head; }
        QueueItem<Type> *end() { return tail->next; }
        template <typename It> Queue(It beg, It end): head(beg), tail(end), size_of_queue(0) { copy_elems(beg, end); }
        //Assign values between two iterators to a Queue object
        template <typename Iter> void assign(Iter, Iter);

    private:
        ...
        template <typename Iter> void copy_elems(Iter, Iter);
};

We overloaded the copy_elems function to initialize the Queue object and assign function through an iterator:

template <typename Type> template <typename Iter> void Queue<Type>::copy_elems(Iter a, Iter b)
{   
    QueueItem<Type> *p = a;
    while(p != b){
        push(p->item);
        p = p->next;
    }
}

template <typename Type> template <typename Iter> void Queue<type>::assign(Iter a, Iter b)
{
    destroy();
    copy_elems(a, b);
}

5. Overload Output Operators

We also want to output the contents of Queue directly from the output operator, so we need to overload the output operator <<, which is also a function template. Since the left operand of the output operator is std::ostream, this overloaded function template can only be defined outside the class. In order for it to access the contents of Queue and QueueItem, we need to set this overloaded function template to QueueFriends of QueueItem:

template <typename Type> std::ostream &operator<<(std::ostream &os, const Queue<Type> &q)
{
    os << "<";
    QueueItem<Type> *p = q.head;
    for( ; p; p = p->next){
        os << p->item;
        if(p != q.tail)
            os << " ";
    }
    os << ">";
    return os;
}

template <typename Type> class QueueItem{
    friend std::ostream &operator<< <Type>(std::ostream &, const Queue<Type> &);
    ...
};

template <typename Type> class Queue{
    friend std::ostream &operator<< <Type>(std::ostream &, const Queue<Type> &);
    ...
}

6. Full code

queue.h:

#ifndef QUEUE_H_
#define QUEUE_H_
#include <iostream>

template <typename Type> class QueueItem;
template <typename Type> class Queue;
template <typename Type> std::ostream &operator<<(std::ostream &os, const Queue<Type> &q)
{
    os << "<";
    QueueItem<Type> *p = q.head;
    for( ; p; p = p->next){
        os << p->item;
        if(p != q.tail)
            os << " ";
    }
    os << ">";
    return os;
}

template <typename Type> class QueueItem{
    //template <typename T> friend class Queue;
    friend class Queue<Type>;
    friend std::ostream &operator<< <Type>(std::ostream &, const Queue<Type> &);
    //private class, no public section
    QueueItem(const Type &t): item(t), next(0) { }
    //value stored in this element
    Type item;
    //pointer to next element int the queue
    QueueItem *next;
};

template <typename Type> class Queue{
    friend std::ostream &operator<< <Type>(std::ostream &, const Queue<Type> &);
    public:
        //default constructor
        Queue(): head(0), tail(0), size_of_queue(0) { }
        //copy control
        Queue(const Queue &Q): head(0), tail(0), size_of_queue(0) { copy_elems(Q); }
        Queue &operator=(const Queue &);
        //destructor
        ~Queue() { destroy(); }

        //get the element at the front of the queue
        Type &front() { return head->item; }
        const Type &front() const { return head->item; }
        //push an element to the end of the queue
        void push(const Type &);
        //pop the element at the front of the queue
        void pop();
        //detect if the queue is empty
        bool empty() const { return head == 0; }
        //return the size of queue
        int size() const { return size_of_queue; }

        QueueItem<Type> *begin() { return head; }
        QueueItem<Type> *end() { return tail->next; }
        //construct a Queue from a pair of iterator on some sequence
        template <typename It> Queue(It beg, It end): head(0), tail(0), size_of_queue(0) { copy_elems(beg, end); }
        //replace current Queue by content delimited by a pair of iterator
        template <typename Iter> void assign(Iter, Iter);
    private:
        //pointer to first element in queue
        QueueItem<Type> *head;
        //pointer to last element in queue
        QueueItem<Type> *tail;
        //qize of queue
        int size_of_queue;
        //delete all elements
        void destroy() { while(!empty()) pop(); }
        //copy elements from parameter
        void copy_elems(const Queue &);
        //version of copy to be used by assign to copy element from iterator range
        template <typename Iter> void copy_elems(Iter, Iter);
};

template <typename Type> template <typename Iter> void Queue<Type>::assign(Iter a, Iter b)
{
    destroy();
    copy_elems(a, b);
}

template <typename Type> template <typename Iter> void Queue<Type>::copy_elems(Iter a, Iter b)
{
    QueueItem<Type> *p = a;
    while(p != b){
        push(p->item);
        p = p->next;
    }
}

template <typename Type> Queue<Type> &Queue<Type>::operator=(const Queue &q)
{
    std::cout << "HERE!" << std::endl;
    copy_elems(q);
    return *this;
}

template <typename Type> void Queue<Type>::copy_elems(const Queue &q)
{
    //copy element from q to Queue
    for(QueueItem<Type> *pt = q.head; pt ; pt = pt->next)
        push(pt->item);
    size_of_queue = q.size();
}

template <typename Type> void Queue<Type>::pop()
{
    QueueItem<Type> *p = head;
    head = head->next;
    delete p;
    --size_of_queue;
}

template <typename Type> void Queue<Type>::push(const Type &val)
{
    QueueItem<Type> *p = new QueueItem<Type>(val);
    if(empty())
        head = tail = p;
    else{
        tail->next = p;
        tail = p;
    }
    ++size_of_queue;
}

#endif