0

Hi all,

I've been working on making a bounded priority queue implemented as an array of queues and I believe I have it at last -- except of course for this error that I don't understand...

I am getting an error about the queue array being declared without a type and I am not seeing what is wrong, since I am passing in a class Item into it as its type.

header file:
The error occurs at line 17 and says "error: ISO C++ forbids declaration of 'queue' with no type".

#include <stdlib.h>
#include "queue.h"

template <class Item, int priCap>
class pq
{
    public:
    pq();
    pq(const pq& source);
    //member functions
    int size() const;
    bool isEmpty() const;
    void insert(const Item& it, int priority);
    Item extractMax();
    void operator=(const pq& source);
    private:
    queue<Item> qs[priCap];
    int count;//number of priority queues
    int highest;//holds the highest index
};

implementation file:

#include <assert.h>
#include <stdlib.h>
#include "arrayofqueues.h"

using namespace std;

template<class Item, int priCap>
pq<Item, priCap>::pq(const pq<Item, priCap>& source)
{
    for(int i = 0; i < priCap; i++)
    {
        qs[i]= source.qs[i];
        count = source.count;
        highest = source.highest;
    }
}//end copy constructor

template <class Item, int priCap>
int pq<Item, priCap>::size() const
{
    return(count);
}//end size

template<class Item, int priCap>
bool pq<Item, priCap>::isEmpty() const
{
    return (count == 0);
}//end isEmpty

templace<class item, int priCap>
void pq<Item, priCap>::insert(const Item& newItem, int priority)
{
    if(priority > priCap)
    {
        cout<<"Error. Priority is greater than max possible." << endl;
    }//end if

    qs[priority].enqueue(newItem);
    if(highest < priority)
    {
        highest = priority;
    }//end if
    cout++;
}//end insert

template<class Item, int priCap>
void pq<Item, priCap>::extractMax()
{
    if(isEmpty())
    {
        cout << "Unable to get max. Priority queue is empty." << endl;
    }//end if

    Item result = qs[highest].dequeue();
    count--;

    while(highest>0 && qs[highest].isEmpty())
    {
        highest--;
    }//end while
    return result;
}//end

template<class Item, int priCap>
void pq<Item, priCap>::operator=(const pq<Item,priCap>& source)
{
    for(int i = 0; i < priCap; i++)
    {
        qs[i]=source.qs[i];
    }
    count = source.count;
    max = source.max;
}//end operator overload

finally, here is the code for my queue class:

#include <cassert>
#include <new>
#include <cstddef>

using namespace std;

template <class T>
class CharQueue
{
   public:
       virtual bool isEmpty() const = 0;
       virtual void enqueue(const T & newItem) = 0;
       virtual void dequeue(void) = 0;  // dequeue an item and return its value
       virtual T getFront(void) const = 0;  // return the value of the first item in the queue (but do not dequeue it)
};

template <class T> class Queue : public CharQueue<T>
{
    private:
    struct qNode {
    T element;
    qNode *next;
    qNode *prev;
    };//end qNode
    qNode *front;
    qNode *back;
    qNode *head;


    public:

    Queue();//default constructor
    Queue(const Queue<T>& q);//copy constructor
    virtual ~Queue();//destructor

    virtual bool isEmpty() const;//checks to see if the queue is empty

    virtual void enqueue(const T & value);//places value at the back of the queue (prior to the head pointer in this case)

    virtual void dequeue();//removes the front value from the queue

    virtual T getFront() const;

    Queue operator = (const Queue & source);
    bool operator== (const Queue & source);

};//end Queue


template <class T> Queue<T>::Queue()
{
    head = NULL;

}//end default constructor


template <class T> Queue<T>::Queue(const Queue & aq)
{
    if(!aq.isEmpty())
    {
        qNode *oldHead = aq.head;
        qNode *oldCurrent = aq.head;
        qNode *newHead = new qNode;//points to the head of the list
        qNode *newCurrent = newHead;
        newCurrent->element = oldCurrent->element;
        while(oldCurrent->next != oldHead) {
            oldCurrent = oldCurrent->next;
            newCurrent->next = new qNode;
            newCurrent->next->prev = newCurrent;
            newCurrent=newCurrent->next;
            newCurrent->element = oldCurrent->element;
        }//end while
        newCurrent->next = newHead;
        newHead->prev=newCurrent;
        head=newHead;
    }//end if

}//end copy constructor

template <class T> Queue<T>::~Queue()
{
    while(!isEmpty())
    {
        dequeue();
    }
 }//end destructor

template <class T> bool Queue<T>::isEmpty() const
{
    return (head == NULL);
}//end isEmpty

template <class T> void Queue<T>::enqueue(const T& value)
{
    try
    {
        //make new node
        qNode *temp = new qNode;
        temp->element = value;

        //back = temp;
        if(isEmpty()) {
            //front = temp;
            head= temp;
            head->next=head;
            head->prev =head;
        }//end if

        else{
            head->prev->next=temp;
            temp->prev=head->prev;
            head->prev=temp;
            head->prev->next=head;
        }
    }//end try
    catch (bad_alloc e)
    {
        throw string("Memory cannot be allocated.");
    }//end catch

}//end enqueue

template <class T> void Queue<T>::dequeue()
{
    if(!isEmpty())
    {
        qNode *temp = head;
        if(head->next == head)
        {
            head=NULL;
        }
        else
        {
            head->prev->next = head->next;
            head->next->prev = head->prev;
            head=head->next;
            delete temp;
        }//end else
    }//end if
}//end dequeue

template <class T> T Queue<T>::getFront() const
{
    if(!isEmpty())
    {
        return head->element;
    }//end if
}//end getFront

template <class T> Queue<T> Queue<T>::operator = (const Queue & source)
{
    return Queue(source);
}//end operator overload

template <class T> bool Queue<T>::operator == (const Queue & source)
{
    if(head==NULL && source.head!=NULL)
    {
        return false;
    }//end if
    qNode * newone = head;
    qNode * oldone = source.head;
    while(newone->next != head && oldone->next != source.head)
    {
        if(newone->element != oldone->element)
        {
            return false;
        }//end if
        newone=newone->next;
        oldone=oldone->next;
    }//end while
    return true;
}//end operator overload

//end q.h

If anybody has any input on this error, I would greatly appreciate it, I feel like it is something simple that I am missing, but I have no idea what, since all the correct files appear to be included. I'm sorry about having to post all this code, but I feel that the actual error is something small and obvious that I'm not catching. Thanks!

2
Contributors
2
Replies
4
Views
6 Years
Discussion Span
Last Post by ace8957
0

As of right now, C++ does not allow you to separate template header and its definition.
You need to put the template definition in the same file as the header.

0

Thanks! Sorry for the late reply. This is something that I have run into before and completely forgot about, since I am used to being able to put the header and implementation in separate files.

This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.