Have something to say? Contribute New Article Reply to this Article
Bounded Priority Queue
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!
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 solved
You
© 2012 DaniWeb® LLC
