Implementation of the Queue
ADT Using a Circular Linked List
queue.h
#include <stddef.h>
class Queue
{
public:
Queue();
~Queue();
Queue( /* in */ const Queue& srcQueue );
void Enqueue(
/* in */ int newItem );
int Front() const;
int Dequeue();
bool IsEmpty() const;
bool IsFull()
const;
private:
struct Node
{
int item;
Node*
next;
};
Node* rear;
};
queue.cpp
#include "queue.h"
Queue::Queue()
{
rear = NULL;
}
bool Queue::IsEmpty() const
{
return ( rear == NULL );
}
bool Queue::IsFull() const
{
return false;
}
int Queue::Front() const
{
return rear->next->item;
}
void Queue::Enqueue( /* in */ int
newItem )
{
Node* newPtr = new Node;
newPtr->item = newItem;
if ( rear == NULL )
newPtr->next = newPtr;
else
{
newPtr->next = rear->next;
rear->next = newPtr;
}
rear = newPtr;
}
int Queue::Dequeue()
{
Node* front
= rear->next;
int item = front->item;
if ( front == rear )
rear = NULL;
else
rear->next = front->next;
delete front;
return item;
}
Destructor
Queue::~Queue()
{
if ( rear != NULL )
{
Node*
front = rear->next;
while ( front != rear )
{
rear->next = front->next;
delete front;
front = rear->next;
}
delete rear;
}
}
Copy Constructor
Queue::Queue( /* in */ const Queue& srcQueue )
{
Node* newPtr;
if ( srcQueue.rear == NULL )
rear = NULL;
else
{
Node* srcPtr = srcQueue.rear->next;
Node*
front = new Node;
front->item = srcPtr->item;
rear = front;
while ( srcPtr != srcQueue.rear )
{
srcPtr = srcPtr->next;
newPtr = new Node;
newPtr->item = srcPtr->item;
rear->next = newPtr;
rear = newPtr;
}
rear->next = front;
}
}