Lab 5: Data Structure in c++

General conditions

Important! Read the conditions for completing the assignments on the module website! Tasks are submitted via the form on the module website. Solutions will not be accepted via email. Please contact the subject list or the lab supervisor if you have any questions.

There are 14 days to solve the exercise.

Deadline: 21.04.2022 23:59:59

Task - A simple Data structure library

This homework aims to create a simple data structure library with three structures, Stack, Queue, and Linked list.

The goal is to compile a library called libdatastructure.a. Library headers must be created so that the test program datastructuretest that accompanies the base files is compiled. At make test, compiles the test program with the three structures' heard and .cpp files. Place headers in the folder include, including library source code in folder src, the finished library goes in folder lib, test application in folder tests

Hints

• The instructions of the Makefile are given in the base program.
• Don't delete any file in the base program.
• It is allowed to use source codes, but you have to state the references in the source files.
• If you have questions about what your output (for datastructuretest.cpp) should look like, I have placed a sample of the output in a .txt file (called "The output of datastructuretest.txt" ). To get a full mark, your output must be as the output in .txt.
• It is highly recommended that each class be built using multiple files (.h, .cpp). However, you can also build them in a single file (.h).

1. Stack (3 points)

Write a class called "Stack" with its header and source file.

Method	Purpose
Stack()	initializes the head = -1
bool push (int x)	Push a data to the stack
int pop()	Pop an element from the stack and return it
int peek()	Read an element from the stack and return it
bool isEmpty()	To check that the stack is empty
bool isFull()	To check that the stack is full
bool isPrim(int x)	To check if the number is Prime
int Gen_Random_Number()	To generate a random number
Stack Sort_Prim_Numbers(Stack &input)	To sort the elements of the stack using another stack

Write the stack test in the given datastrecturetest.cpp. The output must be as follows:

//============================== Stack Test =======================
//|=====> Push elements to s1 <=====|
//937 pushed
//787 pushed
//271 pushed
//547 pushed
//607 pushed
//|=====> Sorting s1 elements into s2 <=====|
//607 pushed
//607 pushed
//547 pushed
//607 pushed
//607 pushed
//547 pushed
//271 pushed
//547 pushed
//607 pushed
//787 pushed
//937 pushed
//|=====> Pop sorted elements from s2 <=====|
//937 787 607 547 271
//================================= End ===============================

In details:

• Generate a random number using Gen_Random_Number().
• Check if this number is prime using isPrim(int x).
• If the number is prime, add it to the stack.
• If the number is not prime, generate new numbers until you have added 5 prime numbers to the stack.
• Later on, sort the 5 prime numbers using another stack (s2).
• Finally, pop the sorted numbers from s2 and print out the numbers.

2. Queue (3 points)

Write a class called "Queue" with its header and source file. The class must be implemented as a template class.

Method	Purpose
Queue()	Initializes the front = -1, rear = -1
bool isFull()	To check that the queue is full
bool isEmpty()	To check that the queue is empty
void EnQueue(T x)	To add an element (x) to the queue
T DeQueue()	To remove an element from the queue
void PrintQueue()	To print out the elements of the queue
void Search(T x)	To find (x) in queue

What is the output printed by the following Queue test code? Do not change anything of the following code!

	cout << "============================== Queue Test ===========================" << endl;
	Queue<int> q1;
	cout << "|=====> Check Queue is empty <=====|" << endl;
	q1.DeQueue();  
	cout <<  "Done!! " << endl;
	cout << "|=====> Push elements to Queue <=====| " << endl;
	srand(time(0));
	q1.EnQueue(rand()%10);
	q1.EnQueue(rand()%10);
	q1.EnQueue(rand()%10);
	q1.EnQueue(rand()%10);
	q1.EnQueue(rand()%10);
	cout <<endl<< "Done!! " << endl;
	cout << "|=====> Check Queue is full <=====|" << endl;
	q1.EnQueue(60);
	cout << "Done!! " << endl;
	cout << "|=====> Display Queue elements <=====|" << endl;
	q1.PrintQueue();
	cout << "Done!! " << endl;
	cout << "|=====> Delete element <=====|" << endl;
	q1.DeQueue();
	cout << "Done!! " << endl;
	cout << "|=====> Display Queue elements <=====|" << endl;
	q1.PrintQueue();
	cout << "Done!! " << endl;
	cout << "|=====> Search in Queue <=====|" << endl;
	Queue<int> q2;
	for (int i = 0; i < MAX; i++)
		q2.EnQueue(rand()%10);

	q2.PrintQueue();
	cout << "Enter a number to search: ";
	int num;
	cin >> num;
	q2.Search(num);
	cout << endl << "================================= End ===============================" << endl;

3. Linked list (4 points)

Write a class called "Linkedlist" with its header and source file.

Method	Purpose
Linkedlist()	Initializes head = NULL
void addNode(int x)	Add a node to the linked list
void printList()	To print out the content of nodes in the linked list
void deleteNode_Index(int i)	Delete a node by a given location index (i)
bool isListEmpty()	To check that the list is empty
int lengthList()	To return the length of the list (how many nodes are in the list)
bool isRange(int)	Ensure the position (i) to be deleted is greater than the linked list's length
void deleteNode_Data(int x)	Delete a node by a given location content (x)
void searchNode(int)	To search for a given data

What is the output printed by the following Linked list test code? Do not change anything of the following code!

cout << "========================== Linked list Test =====================" << endl;
Linkedlist l;
l.addNode(10);
l.addNode(20);
l.addNode(30);
l.addNode(40);
l.addNode(50);
l.addNode(60);
l.addNode(70);
l.addNode(80);
l.addNode(90);
cout << "Elements of the list are: ";
l.printList();
cout << "Length list is : " << l.lengthList() << endl;
l.deleteNode_Index(2);
cout << "Elements of the list are: ";
l.printList();
cout << "Length list is : " << l.lengthList() << endl;
l.deleteNode_Index(2);
cout << "Elements of the list are: ";
l.printList();
cout << "Length list is : " << l.lengthList() << endl;
l.deleteNode_Data(40);
cout << "Elements of the list are: ";
l.printList();
cout << "-----------------------------------------" << endl;
l.isRange(200);
l.searchNode(200);
l.searchNode(10);
cout << endl << "================================= End ===============================" << endl;

Note: You have to define the node class you will use in the linked list class into header and source files. This class (node) should be called in linked list files. The header file of Node as follows:

#ifndef NODE_H
#define NODE_H

#include<iostream>

class Node {
public:
	int data;
	Node* next;

    Node();
    Node(int data);
};
#endif

Additional task (1 extra point)

To get 1 extra point, you have the following options:

Option 1: Convert the Stack class you created to a stack class using Linked List in C++

or

Option 2: Converts the Queue class you created (with all its functions) to a Circular Queue with the template.