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

Why do you have a Queue_head pointer (initialized to and compared against zero instead of NULL) when the comments in your header say there are just the two pointers frontPtr and backPtr? Just use those. Also, if you're going to track Size separately, then you should initialize it in your constructors and update it in enqueue and dequeue.

Thanks alot.I was trying to keep track of size but I forgot I already have size() and can make use of it.I deleted the Queue_head pointer and made use of size and frontPtr ,backPtr pointers. But how can I update size in enqueue and dequeue?

When you enqueue, increase size by one, and when you dequeue decrease size by one. But make sure your adding and removing valid data. So only increase size if you add valid data and decrease size if removing valid size.

do I just add 1 to the variable Size right? you mean like Size=Size+1; ?
because I have to return number of elements in size().

template <class QueueItemType>
int Queue<QueueItemType>::size() const
{
	if (Size !=0)
   return Size;
	else 
		return 0;
}

And my last question,how do i return element in peek and dequeue?

Thanks

For you size()const function just return size, no need to check if its equal to 0 or not.

For your peek you should return a constant reference like so :

template<typename Type>
const Type& peek()const{
 return head;
}

and for your dequeue you have a choice, either not return nothing or return the popped element. If you wan to return the popped element then make a copy for the popped element remove the element, and return the copy.

Oh Great,Thanks alot man.
Just one thing in the code you wrote return head; you mean return frontPtr?

This article has been dead for over six months. Start a new discussion instead.