#ifndef H_linkedQueue #define H_linkedQueue #include <iostream> #include <casser

Question

#ifndef H_linkedQueue
#define H_linkedQueue

#include <iostream>
#include <cassert>

using namespace std;

//Definition of the node
template <class Type>
struct nodeType
{
Type info;
nodeType<Type> *link;
nodeType<Type> *blink;
};

template<class Type>
class linkedQueueType
{
public:
const linkedQueueType<Type>& operator=
(const linkedQueueType<Type>&);
//Overload the assignment operator.

bool isEmptyQueue() const;
//Function to determine whether the queue is empty.
//Postcondition: Returns true if the queue is empty,
// otherwise returns false.
bool isFullQueue() const;
//Function to determine whether the queue is full.
//Postcondition: Returns true if the queue is full,
// otherwise returns false.

void destroyQueue();
//Function to delete all the elements from the queue.
//Postcondition: queueFront = NULL; queueRear = NULL
void initializeQueue();
//Function to initialize the queue to an empty state.
//Postcondition: queueFront = NULL; queueRear = NULL

Type front() const;
//Function to return the first element of the queue.
//Precondition: The queue exists and is not empty.
//Postcondition: If the queue is empty, the program
// terminates; otherwise, the first
// element of the queue is returned.
Type back() const;
//Function to return the last element of the queue.
//Precondition: The queue exists and is not empty.
//Postcondition: If the queue is empty, the program
// terminates; otherwise, the last
// element of the queue is returned.

void insertQueue(const Type& queueElement);
//Function to insert queueElement in the queue in ascending order.
//Precondition: The queue exists and is not full.
//Postcondition: The queue is changed and queueElement
// is inserted in the queue maintaining ascending order.

void deleteQueue();
//Function to remove the first element of the queue.
//Precondition: The queue exists and is not empty.
//Postcondition: The queue is changed and the first
// element is removed from the queue.

linkedQueueType();
//default constructor
linkedQueueType(const linkedQueueType<Type>& otherQueue);
//copy constructor
~linkedQueueType(); //destructor

void listQueue();
//Function to print elements of queue

void blistQueue();
//Function to print elements of queue backwards

nodeType<Type>* place(Type newElement);
//Function used by insertQueue()
private:
nodeType<Type> *queueFront; //pointer to the front of
//the queue
nodeType<Type> *queueRear; //pointer to the rear of
//the queue
};

template<class Type>
linkedQueueType<Type>::linkedQueueType() //default constructor
{
queueFront = NULL; // set front to null
queueRear = NULL; // set rear to null
}


template<class Type>
bool linkedQueueType<Type>::isEmptyQueue() const
{
return(queueFront == NULL);
}

template<class Type>
bool linkedQueueType<Type>::isFullQueue() const
{
return false;
}

template<class Type>
void linkedQueueType<Type>::destroyQueue()
{
nodeType<Type> *temp;

while(queueFront != NULL && queueFront!= queueRear ) //while there are elements left
//in the queue
{
temp = queueFront; //set temp to point to the current node
queueFront = queueFront->link; //advance first to the
//next node
delete temp; //deallocate memory occupied by temp
}
queueRear = NULL; //set rear to NULL
}


template<class Type>
void linkedQueueType<Type>::initializeQueue()
{
destroyQueue();
}

template<class Type>
nodeType<Type>* linkedQueueType<Type>::place( Type newElement)
{
nodeType<Type> *p;
p = queueFront;
while(p != queueRear && p->info < newElement)
p = p->link;
if(p->info > newElement)
return p;
else
return NULL;
}
template<class Type>
void linkedQueueType<Type>::insertQueue(const Type& newElement)
{

nodeType<Type> *newNode, *ptr, *t;

newNode = new nodeType<Type>; //create the node
assert(newNode != NULL);

newNode->info = newElement; //store the info

if(queueFront == NULL) //if initially the queue is empty
{
queueFront = newNode;
queueRear = newNode;
newNode->link=newNode;
newNode->blink = newNode;
}
else
{
ptr = place(newElement);
if(ptr == NULL)
{
//insert new Rear Node
queueRear->link = newNode;
newNode->link = queueFront;
newNode->blink = queueRear;
queueRear = newNode;
queueFront->blink = newNode;

}
else if(ptr == queueFront)
{
//new Front node
newNode->link = queueFront;
newNode->blink = queueRear;
queueFront->blink = newNode;
queueRear->link = newNode;
queueFront = newNode;
}
else
{
//new middle node
t = ptr->blink;
newNode->link = ptr;
ptr->blink = newNode;
t->link = newNode;
newNode->blink = t;

}
}
}//end insertQueue

template<class Type>
Type linkedQueueType<Type>::front() const
{
assert(queueFront != NULL);
return queueFront->info;
}

template<class Type>
Type linkedQueueType<Type>::back() const
{
assert(queueRear!= NULL);
return queueRear->info;
}

template<class Type>
void linkedQueueType<Type>::deleteQueue()
{
nodeType<Type> *temp;

if(!isEmptyQueue())
{
temp = queueFront; //make temp point to the first node
queueFront = queueFront->link; //advance queueFront
delete temp; //delete the first node
queueFront->blink=queueRear;

if(queueFront == queueRear)//if after deletion the queue is empty
{
queueRear = NULL; //set queueRear to NULL
queueFront = NULL;
}
}
else
cerr<<"Cannot remove from an empty queue"<<endl;
}//end deleteQueue


template<class Type>
linkedQueueType<Type>::~linkedQueueType() //destructor
{
nodeType<Type> *temp;

while(queueFront != NULL && queueFront != queueRear) //while there are elements left in the queue
{
temp = queueFront; //set temp to point to the current node
queueFront = queueFront->link; //advance first to the next node
delete temp; //deallocate memory occupied by temp
}

queueRear = NULL; // set rear to null
}

template<class Type>
const linkedQueueType<Type>& linkedQueueType<Type>::operator=
(const linkedQueueType<Type>& otherQueue)
{
//Write the definition of to overload the assignment operator

}

//copy constructor
template<class Type>
linkedQueueType<Type>::linkedQueueType(const linkedQueueType<Type>& otherQueue)
{
//Write the definition of the copy constructor
}//end copy constructor

template<class Type>
void linkedQueueType<Type>::listQueue()
{
nodeType<Type> *ptr;
ptr=queueFront;
while(ptr!=NULL && ptr != queueRear)
{
cout<<ptr->info<<endl;
ptr = ptr->link;
}
if(ptr!=NULL) cout<<ptr->info<<endl;
}

template<class Type>
void linkedQueueType<Type>::blistQueue()
{
nodeType<Type> *ptr;
ptr=queueRear;
while(ptr!=NULL && ptr != queueFront)
{
cout<<ptr->info<<endl;
ptr = ptr->blink;
}
if(ptr!=NULL) cout<<ptr->info<<endl;
}

#endif

Explanation / Answer

//Header file QueueAsArray #ifndef H_QueueAsArray #define H_QueueAsArray #include #include using namespace std; template class queueType { public: const queueType& operator=(const queueType&); // overload the assignment operator bool isEmptyQueue(); //Function to determine if the queue is empty. //Postcondition: returns true if the queue is empty; // otherwise, it returns false. bool isFullQueue(); //Function to determine if the queue is full. //Postcondition: returns true if the queue is full; // otherwise, it returns false. void initializeQueue(); //Function to initialize the queue to an empty state. //Postcondition: count = 0, queueFront = 0; // queueRear = maxQueueSize - 1; void destroyQueue(); //Function to remove all the elements from the queue. //Postcondition: count = 0, queueFront = 0; // queueRear = maxQueueSize - 1; Type front(); //Function to returns the first element of the queue. //Precondition: The queue exists and is not empty //Postcondition: If queue is empty, program terminates; // otherwise the first element of the queue // is returned Type back(); //Function to returns the last element of the queue. //Precondition: The queue exists and is not empty //Postcondition: If the queue is empty, program terminates; // otherwise the last element of the queue // is returned void addQueue(const Type& queueElement); //Function to add queueElement to the queue. //Precondition: The queue exists and is not full. //Postcondition: The queue is changed and queueElement // is added to the queue. void deleteQueue(); //Function to remove the first element of the queue. //Precondition: The queue exists and is not empty. //Postcondition: The queue is changed and the first // element is removed from the queue. queueType(int queueSize = 100); //constructor queueType(const queueType& otherQueue); // copy constructor ~queueType(); //destructor private: int maxQueueSize; int count; int queueFront; int queueRear; Type *list; //pointer to the array that holds //the queue elements }; template void queueType::initializeQueue() { queueFront = 0; queueRear = maxQueueSize - 1; count = 0; } template void queueType::destroyQueue() { queueFront = 0; queueRear = maxQueueSize - 1; count = 0; } template bool queueType::isEmptyQueue() { return(count == 0); } template bool queueType::isFullQueue() { return(count == maxQueueSize); } template void queueType::addQueue(const Type& newElement) { if(!isFullQueue()) { queueRear = (queueRear + 1) % maxQueueSize; //use mod operator //to advance queueRear because //the array is circular count++; list[queueRear] = newElement; } else cerr

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.