Question

USING C++ ONLY.

Please study the code posted below.

the goal is to rewrite the code implementing a template class using a linked list instead of an array. Note: The functionality should remain the same.

/**
* Queue implementation using linked list C style implementation ( no OOP).
*/

#include <cstdio>
#include <cstdlib>
#include <climits>
#include <iostream>

#define CAPACITY 100 // Queue max capacity

using namespace std;
/** Queue structure definition */
struct QueueType
{
int data;
struct QueueType * next;
};
/** Queue size */
unsigned int size = 0;

int enqueue(QueueType * &rear, QueueType * &front, int data);
int dequeue(QueueType * &front);
int getRear(QueueType * &rear);
int getFront(QueueType * &front);
void display(QueueType * front);
int isEmpty();
int isFull();
string prepMenu();

int main()
{
int option, data;

QueueType *rear, *front;

rear = NULL;
front = NULL;
string menu = prepMenu();
cout << menu << endl;
cin >> option;
while (option !=7)
{

switch (option)
{
case 1:
cout << "\nEnter data to enqueue (-99 to stop): ";
cin >> data;
while ( data != -99)
{
/// Enqueue function returns 1 on success
/// otherwise 0
if (enqueue(rear, front, data))
cout << "Element added to queue.";
else
cout << "Queue is full." << endl;
cout << "\nEnter data to enqueue (-99 to stop): ";
cin >> data;
}

break;

case 2:
data = dequeue(front);

/// on success dequeue returns element removed
/// otherwise returns INT_MIN
if (data == INT_MIN)
cout << "Queue is empty."<< endl;
else
cout << "Data => " << data << endl;

break;

case 3:

/// isEmpty() function returns 1 if queue is emtpy
/// otherwise returns 0
if (isEmpty())
cout << "Queue is empty."<< endl;
else
cout << "Queue size => "<< size << endl;

break;

case 4:
data = getRear(rear);

if (data == INT_MIN)
cout << "Queue is empty." << endl;
else
cout << "Rear => " << data << endl;

break;

case 5:

data = getFront(front);

if (data == INT_MIN)
cout <<"Queue is empty."<< endl;
else
cout <<"Front => " << data << endl;

break;

case 6:
display(front);
break;

default:
cout <<"Invalid choice, please input number between (0-5).\n";
break;
}

cout <<"\n\n";
cout << menu<< endl;
cin >> option;
}
}

/**
* Enqueues/Insert an element at the rear of a queue.
* Function returns 1 on success otherwise returns 0.
*/
int enqueue(QueueType * &rear, QueueType * &front, int data)
{
QueueType * newNode = NULL;

/// Check queue out of capacity error
if (isFull())
{
return 0;
}

/// Create a new node of queue type
newNode = new QueueType;

/// Assign data to new node
newNode->data = data;

/// Initially new node does not point anything
newNode->next = NULL;

/// Link new node with existing last node
if ( (rear) )
{
rear->next = newNode;
}

/// Make sure newly created node is at rear
rear = newNode;

/// Link first node to front if its NULL
if ( !( front) )
{
front = rear;
}

/// Increment quque size
size++;

return 1;
}

/**
* Dequeues/Removes an element from front of the queue.
* It returns the element on success otherwise returns
* INT_MIN as error code.
*/
int dequeue(QueueType * &front)
{
QueueType *toDequque = NULL;
int data = INT_MIN;

// Queue empty error
if (isEmpty())
{
return INT_MIN;
}

/// Get element and data to dequeue
toDequque = front;
data = toDequque->data;

/// Move front ahead
front = (front)->next;

/// Decrement size
size--;

/// Clear dequeued element from memory
free(toDequque);

return data;
}

/**
* Gets, element at rear of the queue. It returns the element
* at rear of the queue on success otherwise return INT_MIN as
* error code.
*/
int getRear(QueueType * & rear)
{
// Return INT_MIN if queue is empty otherwise rear.
return (isEmpty())
? INT_MIN
: rear->data;
}

/**
* Gets, element at front of the queue. It returns the element
* at front of the queue on success otherwise return INT_MIN as
* error code.
*/
int getFront(QueueType * &front)
{
// Return INT_MIN if queue is empty otherwise front.
return (isEmpty())
? INT_MIN
: front->data;
}

/**
* Checks, if queue is empty or not.
*/
int isEmpty()
{
return (size <= 0);
}

/**
* Checks, if queue is within the maximum queue capacity.
*/
int isFull()
{
return (size > CAPACITY);
}
string prepMenu()
{

string menu = "";

menu+= " \n-------------------------------------------------------------------\n";
menu+= "1.Enqueue 2.Dequeue 3.Size 4.Get Rear 5.Get Front 6.Display 7.Exit\n";
menu+= "----------------------------------------------------------------------\n";
menu+= "Select an option: ";
return menu;
}
void display(QueueType * front)
{
for ( QueueType *t = front; t !=NULL; t = t->next)
cout <<t->data << " ";
cout << endl << endl;
}

please provide comments in the code where appropriate, thank you!

Answer 1

// C++ program to implement a template queue class using a linked list
#include <iostream>

using namespace std;

// struct to represent the node of the queue
template <class T>
struct Node
{
T data;
Node* next;
};

// queue class
template <class T>
class QueueType
{
private:
Node<T>* front;
Node<T>* rear;
int numElements;
public:
QueueType();
~QueueType();
void enqueue(T value);
T dequeue();
T getRear();
T getFront();
void display();
bool isEmpty();
bool isFull();
int size();
};

// constructor to create an empty queue
template <class T>
QueueType<T>::QueueType()
{
front = NULL;
rear = NULL;
numElements = 0;
}

// destructor to delete the nodes of the queue
template <class T>
QueueType<T>::~QueueType()
{
Node<T>* temp;
while(front != NULL)
{
temp = front;
front = front->next;
temp->next = NULL;
delete temp;
temp = NULL;
}

rear = NULL;
numElements = 0;
}

// function to insert value at the end of the queue
template <class T>
void QueueType<T>::enqueue(T value)
{
Node<T>* node = new Node<T>;
node->data = value;
node->next = NULL;
if(isEmpty())
front = node;
else
rear->next = node;
rear = node;
numElements++;
}

// function to remove the front element of the queue
template <class T>
T QueueType<T>:: dequeue()
{
T data;
if(!isEmpty())
{
Node<T>* temp = front;
front = front->next;
temp->next = NULL;
data = temp->data;
delete(temp);
temp = NULL;
numElements--;
}

return data;
}

// function to return element at the back
template <class T>
T QueueType<T>:: getRear()
{
if(!isEmpty())
return rear->data;
return T();
}

// function to return element at the front
template <class T>
T QueueType<T>::getFront()
{
if(!isEmpty())
return front->data;
return T();
}

// function to display the queue
template <class T>
void QueueType<T>:: display()
{
if(isEmpty())
cout<<"Queue is empty"<<endl;
else{
Node<T>* curr = front;
while(curr != NULL)
{
cout<<curr->data<<" ";
curr = curr->next;
}
}
}

// function to return true if the queue is empty else return false
template <class T>
bool QueueType<T>:: isEmpty()
{
return front == NULL;
}

// function to return true if queue is full else return false
template <class T>
bool QueueType<T>:: isFull()
{
return false; // since the queue is implemented using linkedlist, there is no maximum size of the queue, hence never full
}

// function to return number of elements in the queue
template <class T>
int QueueType<T>::size()
{
return numElements;
}

string prepMenu();

int main()
{
int option, data;

QueueType<int> queue;
string menu = prepMenu();
cout << menu << endl;
cin >> option;

// loop that continues until the user exits
while (option !=7)
{
switch (option)
{
case 1:
cout << "\nEnter data to enqueue (-99 to stop): ";
cin >> data;
while ( data != -99)
{
queue.enqueue(data);
cout << "Element added to queue.";
cout << "\nEnter data to enqueue (-99 to stop): ";
cin >> data;
}

break;

case 2:
if(!queue.isEmpty()){
data = queue.dequeue();
cout << "Data => " << data << endl;
}else
cout << "Queue is empty."<< endl;
break;

case 3:
if (queue.isEmpty())
cout << "Queue is empty."<< endl;
else
cout << "Queue size => "<< queue.size() << endl;
break;

case 4:
if(!queue.isEmpty())
cout << "Rear => " << queue.getRear() << endl;
else
cout<<"Queue is empty." << endl;
break;

case 5:
if(!queue.isEmpty())
cout << "Front => " << queue.getFront() << endl;
else
cout<<"Queue is empty." << endl;
break;

case 6:
queue.display();
break;
case 7:
break;
default:
cout <<"Invalid choice, please input number between (1-7).\n";
}

cout <<"\n\n";
cout << menu<< endl;
cin >> option;
}

return 0;
}

string prepMenu()
{
string menu = "";

menu+= " \n-------------------------------------------------------------------\n";
menu+= "1.Enqueue 2.Dequeue 3.Size 4.Get Rear 5.Get Front 6.Display 7.Exit\n";
menu+= "----------------------------------------------------------------------\n";
menu+= "Select an option: ";
return menu;
}

//end of program

Output: