TASK 2

Basic Data Structures Overview

Assignment

You must implement 4 different data structures ADT:
- Binary Tree: create(), insertLeft(), insertRight(), getRoot(), setRoot(), getLeftChild(), getRigthChild(), destroy().
- Stack: create(), push(), pop(), isEmpty(), isFull(), destroy(), ect.
- 2 freely chosen data structures.
For your created data structures you should implement any type of algorithm and demonstrate how it works for e.g.:
- Stack ADT -> implement algorithm which is calculate simple expressions e.g. 9(((5+8)+(87))+3).
- Binary Tree -> implement Parse Tree algorithm here you will find more info.
- Your own picked ADT 1 -> Any type of algorithm.
- Your own picked ADT 2 -> Any type of algorithm.
Your app output also should visible in console or text file and display every step of your created algorithm how it works -> when you adding deleting, comparing, destroying or displaying data structure content.

Example of Stack ADT

/* 
 * File:   main.cpp
 * Author: Marius
 *
 * Created on January 27, 2019, 12:02 AM
 */

#include <cstdlib>
#include <iostream>
#define MAX_SIZE 10 // Max size of Stack container

using namespace std;

int container[MAX_SIZE]; // Container to store Stack ADT elements

class Stack{
    public: 
        int top;
        
        Stack(){ top = -1;}
        
        bool isFull(){
            if(MAX_SIZE - top == 1){
                return true;
            }else{
                return false;
            }
        }
        bool isEmpty(){
            if(top == -1){
                return true;
            }else{
                return false;
            }
        }
        void push(int x){
            if(!isFull()){
                top++;
                container[top] = x;
            }else{
               cout<< "\nStack is full\n";
            }
        }
        int pop(){
            int x;
            if(!isEmpty()){
                x = container[top];
                top--;
                return x;
            }else{
                return -1;
            }
        }
        void print(){
            cout << "------------------------------------"<< endl;
            for(int i=0; i <= top; i++){
                if(top == i){
                    cout << container[i] << ".";
                }else{
                    cout << container[i] << ",";
                } 
            }
            cout << "\n------------------------------------"<< endl;
        }
        
};

int main(int argc, char** argv) {
    Stack stack;
   
    for(int i=0; i < MAX_SIZE; i++){
        stack.push(i);
    }
    
    // Every step displaying Stack data structure container 
    stack.print();
    stack.pop();
    stack.print();
    stack.push(99);
    stack.print();

}

Example of LinkedList ADT

#include <cstdlib>
#include <iostream>

using namespace std;

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

class LinkedList{
  public:
    int length;
    Node *head;

    LinkedList(){
      this->length = 0;
      this->head = nullptr;
    }
    ~LinkedList(){
      cout << "LIST DELETED" << endl;
    }
    void add(int data){
      Node *node = new Node();
      node->data = data;
      node->next = this->head;
      this->head = node;
      this->length++;
    }
    void remove(int position){
      Node *temp1 = head;
      if(position == 1){
        head = temp1->next;
        delete temp1;
      }
      for(int i=0; i < position - 2; i++){
        temp1 = temp1->next;
      }
      Node *temp2 = temp1->next;
      temp1->next = temp2->next;
      delete temp2;
    }
    void display(){
      Node *head = this->head;
      int i = 1;
      while(head){
        cout << i<<": "<< head->data << endl;
        head = head->next;
        i++;
      }

    }
};

Example of Queue ADT

#include <string>
#include <iostream>
using namespace std;

class Queue {
private:
  int data[10]={};
  int size;
  int front;
  int rear;
  int numberOfItems = 0;
public:

  Queue(){
    front = rear = -1;
    size = sizeof(data) / sizeof(data[0]);
    for(int i=0; i < size; i++){
      data[i] = -1;
    }
  }

  void insert(int input){
    if(numberOfItems + 1 <= size){
      data[rear] = input;
      rear++;
      numberOfItems++;
      cout << "INSERT " << input << " was added to Queue!" <<endl;
      displayQueue();
    }else{
      cout << "Sorry but the Queue is Full!"<< endl;
    }
  }
  void remove(){
    if(numberOfItems > 0){
      cout << "REMOVE " << data[front] << " was removed from Queue!" <<endl;
      data[front] = -1;
      front++;
      numberOfItems--;
    }else{
      cout << "Sorry but the Queue is Empty!"<< endl;
    }
  }
  void peek(){
    if(data[front] != -1)
      cout << "The First Element is " << data[front] <<endl;
  }
  void displayQueue(){
    cout << "------------------------------" <<endl;
    cout<< "|" << data[front];
    for(int i=0; i < size; i++){
      if(data[i] != -1) {
        cout << "|" << data[i] << "|";
      } else{
        cout << "|" << " " << "|";
      }
    }
    cout << "\n------------------------------" <<endl;
  }

};

Example of Tree ADT

#include <cstdlib>
#include <iostream>
class Tree{
public:
  int data;
  Tree *left;
  Tree *right;

  Tree * node(int data){
    Tree * node = new Tree();
    node->data = data;
    node->left = nullptr;
    node->right = nullptr;
    return node;
  }
  void printPostOrder(Tree * node){
    if(node == nullptr) {return;}
    // first recur on left subtree
    printPostOrder(node->left);
    // then recur on right subtree
    printPostOrder(node->right);
    // now deal with the node
    cout << (char)node->data << " ";
  }
  /* Given a binary tree, print its nodes in inorder*/
  void printInOrder(Tree * node)
  {
    if (node == nullptr) {return;}
    /* first recur on left child */
    printInOrder(node->left);
    /* then print the data of node */
    cout << (char)node->data << " ";
    /* now recur on right child */
    printInOrder(node->right);
  }
  /* Given a binary tree, print its nodes in preorder*/
  void printPreorder(Tree *node)
  {
    if (node == nullptr)
      return;

    /* first print data of node */
    cout << (char)node->data << " ";

    /* then recur on left sutree */
    printPreorder(node->left);

    /* now recur on right subtree */
    printPreorder(node->right);
  }


};

int main(int argc, char** argv) {

  Tree * tree = tree->node('F');

  tree->left = tree->node('B');
  tree->right = tree->node('G');
  tree->left->left = tree->node('A');
  tree->left->right = tree->node('D');
  tree->left->right->left = tree->node('C');
  tree->left->right->right = tree->node('E');

  tree->right->right = tree->node('I');
  tree->right->right->left = tree->node('H');

  cout<< "POSTORDER\n";
  tree->printPostOrder(tree);
  cout<< "\nINORDER"<< endl;
  tree->printInOrder(tree);
  cout<<"\nPREORDER"<< endl;
  tree->printPreorder(tree);
  }

Algorithms & Data Structures

GENERAL

TASK 2