Lab 5 - Data structure in C++

Introduction

A data structure is a special way of organizing data contents into a particular shape. In order to access a particular data element quickly and easily without having to put much effort in, data should be arranged in a particular order. The data structure is a storage for storing, organizing, processing, and retrieving data. It is a way of arranging data on a computer to be accessed and updated efficiently. Data structures are used in almost every program or software system that has been developed, and there are several basic and advanced types of data structures. Consequently, C++ programmers must have considerable knowledge of data structure types. https://en.wikipedia.org/wiki/List_of_data_structures

Classification of Data Structure:

The data structure can be classified into two categories, namely - Linear data structure and Non-linear data structure, as follows:

Linear data structure:

Data structures consisting of sequential or linear elements attached to previous and next adjacent elements are referred to as linear data structures. Since the elements are stored linearly, the structure supports single-level data storage. Therefore, the traversal of the data is accomplished through a single run. Examples of linear data structures are array, stack, queue,linked list.

1- Static data structure

The static data structure has a fixed memory size. It is easier to access the elements in a static data structure. An example of this data structure is an array.

One-Dimensional array

This type of array stores elements in a single dimension.

#include<iostream>
using namespace std;

void main(){
	int arr[10] = { 10,11,12,13,14,15,16,17,18,19 };
	for (int i = 0; i < 5; i++)
		cout << arr[i] << " "; // print out 10 11 12 13 14 
}

Two-Dimensional array

In the two-dimensional array, two indexes should be used to traverse over the elements, the first index represents a row, and the second index represents a column.

#include <iostream>
using namespace std;

void main(){
	int row = 3, col = 3;
	int Arr[3][3] = { {10, 20, 30}, {40, 50 ,60 }, {70, 80 , 90} };
	for (int i = 0; i < row; ++i){
		for (int j = 0; j < col; ++j){
			cout << Arr[i][j] << "  ";   // print out   10 20 30 
		}                                //             40 50 60   
		cout << endl;                    //             70 80 90
	}
}

2- Dynamic data structure:

Unlike a static data structure, a dynamic data structure does not have a fixed size. It can be randomly updated during the runtime, which may be considered efficient concerning the code's memory (space) complexity.

The heap is the unused memory of the program and can be used to allocate the memory dynamically during the runtime. In c++, a programmer can allocate memory at run time within the heap for the variable of a given type using a special operator called new operator.

Examples of this data structure are queue, stack, etc.

Dynamic Array

We can create a pointer to an array in C++ as follows:

int row = 3;
int col = 3;

//C++ version                      //C version
int* A = new int[row*col];         //int* A = (int*)malloc(row*col * sizeof(int*));
int* B = new int[row*col];         //int* B = (int*)malloc(row*col * sizeof(int*));

// set initial values
for (int i = 0; i < row*col; i++) { A[i] = i; }
for (int i = 0; i < row*col; i++) { B[i] = i + 1; }

Read more about the dynamic array, https://www.guru99.com/cpp-dynamic-array.html

Stack

It is a linear data structure that follows a specific order in which the operations are performed. This structure follows the rule of LIFO (Last In-First Out), where the data's last added element is removed first, then one by one. Push operation is used for adding an element of data on the stack, and the Pop operation is used for deleting the data from the stack. The basic operations (function) we need to perform the ordinary work on the stack are: Push(), Pop(), Peek(), and isEmpty().

class Stack{
  private: 
	int head;
  public:
	int* Arr= new int[maxSize];
	Stack() { head = -1; }  // Constuctor, Stack has only one flag called head
    ~Stack();               // Destructor
	bool Push(int x);
	int Pop();
	int peek();
	bool isEmpty();
};

bool Stack::Push(int element)
{
	if (head >= (maxSize - 1)) {
		return false;
	}
	else {
        // Move the head to a location and push the element into the stack
		Arr[++head] = element; 
		return true;
	}
}

int Stack::pop()
{
	if (head < 0) {
		return 0;
	}
	else {
        // Pop the element from the stack, then the head moves to a location down
		int element = Arr[head--]; 
		return element;
	}
}

Read more about stack:

• https://cplusplus.com/reference/stack/stack/?kw=stack
• https://www.softwaretestinghelp.com/stack-in-cpp/

Queue

It is also a dynamic data structure but follows the rule of FIFO (First In-First Out). This structure is almost similar to the stack as the data is stored sequentially or linearly, where the first added element is to exit the queue first. It has two flags pointing to the elements' location, front and rear. Usually, the insertion operation is called Enqueue, while the deletion operation is called Dequeue. The basic operations (functions) on the Queue are: Enqueue(), Dequeue(), Printqueue(), and isEmpty().

class Queue{
private:
	int front;
	int rear;
	int Arr[MAX];
public:
	Queue();
	bool isFull();
    bool isEmpty();
	void Enqueue(int element);
	int  Dequeue();
    void PrintQueue();
};

void Queue::Enqueue(int element) {
	if (isFull()) {
		cout << endl << "Queue is full!!";
	}
	else {
		if (front == -1) 
			front = 0;
		rear++;
		Arr[rear] = element;
	}
}

int Queue::Dequeue() {
	int element;
	if (isEmpty()) 
	{
		cout << "Queue is empty!!" << endl; 
		return(-1);
	}
	else 
	{
		element = Arr[front]; 
		if (front >= rear) 
		{     
			front = -1;
			rear = -1;
		}
		else 
		{
			front++;
		}
		return element;
	}
}

Read more about queue:

• https://cplusplus.com/reference/queue/queue/?kw=Queue
• https://www.softwaretestinghelp.com/queue-in-cpp/

Link list

Link lists are also linear data structures where elements are not stored at contiguous locations in memory. The element can be stored in different locations in memory. The elements in a linked list are linked using pointers. In another word, linked lists consist of nodes with data fields and a reference to the next node. The nodes are linked using pointers. Each node in a list consists of at least two parts, its own data, and a pointer to store the address of the next node.

In C/C++, we can represent a node using structures as follows:

// A linked list node in C version
struct Node {
	int data;
	struct Node* next;
};

Or it can be

// A linked list node in C++ version
class Node {
public:
	int data;
	Node* next;
};

Note: We can represent a node using structures with constructors to assign the initial value as follows:

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

	Node() // Default constructor
	{
		data = 0;
		next = NULL;
	}
	Node(int data) // Parameterised Constructor
	{
		this->data = data;
		this->next = NULL;
	}
};

Below is an example of creating a linked list of nodes. It has integer data and the pointer of the next node's address. Allocating three 3 nodes in a heap using new operator. The sign '->' is used to sign the data and address to the struct pointer.

#include <iostream>
using namespace std;

struct Node {
	int data;
	Node* next;
};

void Display_LinkedList(Node *nNode)
{
	while (nNode != NULL) {
		cout << nNode->data << " ";
		nNode = nNode->next;
	}
}

void main()
{
	Node* Node1 = NULL;
	Node* Node2 = NULL;
	Node* Node3 = NULL;

	// allocate 3 nodes in the heap
	Node1 = new Node();
	Node2 = new Node();
	Node3 = new Node();

	Node1-> data = 10;   // assign data in first node
	Node1-> next = Node2; // Link first node with second

	Node2-> data = 20;
	Node2-> next = Node3;

	Node3-> data = 30;
	Node3-> next = NULL;

	Display_LinkedList(Node1);  // print out the nodes
}

Read more about Linked-list:

• https://www.softwaretestinghelp.com/linked-list/
• https://visualgo.net/en/list

Non-linear data structure:

A non-linear data structure is a type of data structure in which the elements are not arranged in a sequential or linear manner. Unlike linear data structures, which have a linear relationship between their elements, non-linear data structures have a hierarchical or tree-like relationship between their elements. Some common examples of non-linear data structures include trees and graphs.

Non-linear data structures are useful in a variety of applications, such as organizing hierarchical data, representing relationships between objects, and searching for elements with specific properties or values. They can also be used to optimize certain algorithms by providing efficient data access and manipulation operations.