Question

PART A - STACKS

To complete this assignment:

Please study the code posted below.

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

***************************************************************************************************************

/**
* Stack implementation using array in C/procedural language.
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
//#include <climits> // For INT_MIN

#define SIZE 100

using namespace std;

/// Create a stack with capacity of 100 elements
int stack[SIZE];

/// Initially stack is empty
int top = -1;

/** Function declaration to perform push and pop on stack */
void push(int element);
int pop();
void display();

int main()
{
int choice, data;

while(1)
{
/* Menu */
cout <<"------------------------------------\n";
cout <<" STACK IMPLEMENTATION PROGRAM \n";
cout <<"------------------------------------\n";
cout <<"1. Push\n";
cout <<"2. Pop\n";
cout <<"3. Size\n";
cout <<"4. Print Stack\n";
cout <<"5. Exit\n";
cout <<"------------------------------------\n";
cout <<"Enter your choice: ";

cin >>choice;

switch(choice)
{
case 1:
cout <<"Enter data to push into stack: ";
cin >> data;

// Push element to stack
push(data);
break;

case 2:
data = pop();

/// If stack is not empty
if (data != INT_MIN)
cout <<"Data => " << data << endl;
break;

case 3:
cout <<"Stack size: " << top + 1 << endl;
break;
case 4:
display();
break;

case 5:
cout <<"Exiting from app.\n";
exit(0);
break;

default:
cout <<"Invalid choice, please try again.\n";
}

cout <<"\n\n";
}

return 0;
}

/**
* Function to push a new element in stack.
*/
void push(int element)
{
/// Check stack overflow
if (top >= SIZE)
{
cout <<"Stack Overflow, can't add more element element to stack.\n";
return;
}

/// Increase element count in stack
top++;

/// Push element in stack
stack[top] = element;

cout <<"Data pushed to stack.\n";
}

/**
* Function to pop element from top of stack.
*/
int pop()
{
/// Check stack underflow
if (top < 0)
{
cout <<"Stack is empty.\n";

/// Throw empty stack error/exception
/// Since C does not have concept of exception
/// Hence return minimum integer value as error value
/// Later in code check if return value is INT_MIN, then
/// stack is empty
return INT_MIN;
}

/// Return stack top and decrease element count in stack
return stack[top--];
}
void display()
{
if ( top >=0)
{
for(int i = 0; i <= top ; i++ )
cout << stack[i] << " ";
cout << endl;
}

else
cout << "stack is empty\n\n";
}

****************************************************

PART B - QUEUES

Please study the code posted below.

Please 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;
}

Answer 1

Stack implementation using Linked List

Source Code:

#include <iostream>

using namespace std;
struct Node
{
int data;
struct Node *next;
  
};

struct Node* top = NULL;
struct Node* head;
//struct Node* display;

void pushOperation(int x){
struct Node* newnode = (struct Node*)malloc(sizeof(struct Node));
newnode->data = x;
newnode->next = top;
top = newnode;
}

void popOperation(){
if(top == NULL)cout<<"Stack UnderFlow"<<endl;
else{
cout<<"Element "<<top->data<<" is popped"<<endl;
top = top->next;
}
}

void display() {
struct Node* ptr;
if(top==NULL)
cout<<"stack is empty";
else {
ptr = top;
cout<<"Stack elements are: ";
while (ptr != NULL) {
cout<< ptr->data <<" ";
ptr = ptr->next;
}
}
cout<<endl;
}

int main(){
int choice,value;
cout<<"1. Push Operation\n2.Pop Operation\n";
cout<<"3.Display\n4.Exit\n";
do{
cout<<"Enter Your Choice:";
cin>>choice;
switch(choice){
case 1:
cout<<"\nEnter value to be pushed:";
cin>>value;
pushOperation(value);
break;
case 2:
popOperation();
break;
case 3:
display();
break;
case 4:
cout<<"\nEXIT"<<endl;
default:
cout<<"Invalid Choice";
}
}while(choice!=4);
return 0;
}

OUTPUT:

We try our best But in given time limit we will able to solve one part.

If you have any error or doubt then please explain in comment section

Click on Thumbs up if you are satisfy.

Thankyou