Hi everyone,
I want to implement an ADT Queue class (pointer base) use Template with following public interfaces: enqueue,dequeue,dequeueAll,peek,and size.
I have 2 problems:
1.not sure how to dequeueAll which is removes all elements from the queue with Postcondition: size( ) returns 0
2.for dequeue and peek I need to make sure the Queue is not empty and not sure if i am doing it right. if (Queue_head == 0) EmptyQueueExceptionDequeue("empty queue");
Here is my code:
///////////////Queue.h
#include "EmptyQueueExceptionDequeue.h"
#include "EmptyQueueExceptionPeek.h"
template <class QueueItemType>
class Queue{
public:
Queue(); // default constructor
Queue(const Queue& Q); // copy constructor
~Queue(); // destructor
// Queue operations:
void enqueue(const QueueItemType newItem);
// Adds an element to the back of the queue.
void dequeue(const QueueItemType& queueFront) throw(EmptyQueueExceptionDequeue);
// Retrieves and removes an element from the front of the queue. It also returns it.
// Precondition: Queue is not empty.
// Throws an exception if queue is empty.
void dequeueAll( );
// Removes all elements from the queue.
// Postcondition: size( ) returns 0.
void peek(const QueueItemType& queueFront)const throw(EmptyQueueExceptionPeek);
// Retrieves an element from the front of the queue and returns it.
// Precondition: Queue is not empty.
// Postcondition: the queue is unchanged.
// Throws an exception if queue is empty.
int size() const;
//Returns the number of elements currently stored in the queue.
//Postcondition: Returns 0 if empty otherwise returns the number of elements.
private:
// The queue is implemented as a linked list with one external
// pointer to the front of the queue and a second external
// pointer to the back of the queue.
int Size;
struct QueueNode{
QueueItemType item;
QueueNode *next;
};
QueueNode *backPtr;
QueueNode *frontPtr;
QueueNode* Queue_head;
};///////////////Queue.cpp
#include "Queue.h"
#include <cstddef>
#include <cassert>
#include <iostream>
#include <string>
using namespace std;
using std::cout;
using std::cin;
template <class QueueItemType>
// default constructor
Queue<QueueItemType>::Queue() : backPtr(NULL), frontPtr(NULL) , Queue_head(0) {
}
template <class QueueItemType>
// copy constructor
Queue<QueueItemType>::Queue(const Queue& Q){
}
template <class QueueItemType>
// destructor
Queue<QueueItemType>::~Queue(){
while (Queue_head != 0)
dequeue();
}
template <class QueueItemType>
void Queue<QueueItemType>::enqueue(QueueItemType newItem){
// create a new node
QueueNode *newPtr = new QueueNode;
// set data portion of new node
newPtr->item = newItem;
newPtr->next = NULL;
// insert the new node
if (Queue_head == 0) // insertion into empty queue
frontPtr = newPtr;
else // insertion into nonempty queue
backPtr->next = newPtr;
backPtr = newPtr; // new node is at back
}
template <class QueueItemType>
void Queue<QueueItemType>::dequeue(const QueueItemType& queueFront){
// throw(QueueException)
if (Queue_head == 0)
EmptyQueueExceptionDequeue("empty queue");
else{
// queue is not empty; retrieve front
queueFront = frontPtr->item;
QueueNode *tempPtr = frontPtr;
if (frontPtr == backPtr){ // special case
frontPtr = NULL;
backPtr = NULL;
}
else
frontPtr = frontPtr->next;
tempPtr->next = NULL; // defensive strategy
delete tempPtr; // delete front
}
}
template <class QueueItemType>
void Queue<QueueItemType>::peek(const QueueItemType& queueFront)const {
// throw(QueueException)
if (Queue_head == 0)
EmptyQueueExceptionPeek("empty queue");
//throw QueueException("empty queue");
else{
// queue is not empty; retrieve front
queueFront = frontPtr->item;
}
}
template <class QueueItemType>
int Queue<QueueItemType>::size() const
{
return Size;
}Thanks