Mada za sehemu hiiDemonstrate mastery of basic principles of Algorithms and Data structuresMada 7
- Describe the concept of data structure and algorithms
- Explore and utilise basic data structure (linked lists, stacks, queues and trees.)
- Describe the design and performance of various classic searching and sorting algorithms
- Write a program that implements various sorting algorithms and create a report for performance
- Create a program that implements array and a linked list data structure using object-oriented programming language
- Implement stack and queue, binary search tree, balanced tree (such as an AVL tree), graph, hash table data structures in object-oriented programming language
- Describe the techniques of algorithm analysis
Implementing Data Structures in Object-Oriented Programming
When programming, the way we organise and store data directly affects how fast our programs run and how efficiently they use memory. Different problems require different data organisations—some need quick insertion and removal from one end (stack), others need to handle items in the order they arrive (queue), and more complex scenarios require hierarchical structures (trees), networks (graphs), or fast lookup tables (hash tables). This study note shows you how to implement each of these data structures using an object-oriented approach in C++.
A stack is a Last-In-First-Out (LIFO) data structure where elements are added and removed from only one end called the top. Think of a stack of plates in a cafeteria: you add plates on top and remove them from the top.
Stack Operations
- push(item): Add an element to the top of the stack
- pop(): Remove and return the top element
- peek(): View the top element without removing it
- isEmpty(): Check if the stack contains no elements
- isFull(): Check if the stack has reached its maximum capacity
- size(): Return the number of elements in the stack
C++ Implementation Using a Class
#include <iostream>
using namespace std;
class Stack {
private:
int *arr;
int top;
int capacity;
public:
Stack(int size) {
capacity = size;
arr = new int[capacity];
top = -1;
}
~Stack() {
delete[] arr;
}
void push(int item) {
if (top >= capacity - 1) {
cout << "Stack Overflow! Cannot push " << item << endl;
return;
}
arr[++top] = item;
}
int pop() {
if (isEmpty()) {
cout << "Stack Underflow!" << endl;
return -1;
}
return arr[top--];
}
int peek() {
if (isEmpty()) {
return -1;
}
return arr[top];
}
bool isEmpty() {
return top == -1;
}
bool isFull() {
return top == capacity - 1;
}
int size() {
return top + 1;
}
void display() {
if (isEmpty()) {
cout << "Stack is empty" << endl;
return;
}
cout << "Stack elements: ";
for (int i = 0; i <= top; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
};
int main() {
Stack s(5);
s.push(10);
s.push(20);
s.push(30);
s.display();
cout << "Popped: " << s.pop() << endl;
cout << "Top element: " << s.peek() << endl;
s.display();
return 0;
}
Output:
Stack elements: 10 20 30
Popped: 30
Top element: 20
Stack elements: 10 20
A queue is a First-In-First-Out (FIFO) data structure where elements are added at the rear and removed from the front. Think of people waiting at a bank teller—the first person in line is served first.
Queue Operations
- enqueue(item): Add an element to the rear of the queue
- dequeue(): Remove and return the front element
- front(): View the front element without removing it
- rear(): View the rear element without removing it
- isEmpty(): Check if the queue is empty
- isFull(): Check if the queue is full
- size(): Return the number of elements
C++ Implementation
#include <iostream>
using namespace std;
class Queue {
private:
int *arr;
int front, rear;
int capacity;
int count;
public:
Queue(int size) {
capacity = size;
arr = new int[capacity];
front = 0;
rear = -1;
count = 0;
}
~Queue() {
delete[] arr;
}
void enqueue(int item) {
if (isFull()) {
cout << "Queue is full! Cannot enqueue " << item << endl;
return;
}
rear = (rear + 1) % capacity;
arr[rear] = item;
count++;
}
int dequeue() {
if (isEmpty()) {
cout << "Queue is empty!" << endl;
return -1;
}
int item = arr[front];
front = (front + 1) % capacity;
count--;
return item;
}
int frontElement() {
if (isEmpty()) {
return -1;
}
return arr[front];
}
int rearElement() {
if (isEmpty()) {
return -1;
}
return arr[rear];
}
bool isEmpty() {
return count == 0;
}
bool isFull() {
return count == capacity;
}
int size() {
return count;
}
void display() {
if (isEmpty()) {
cout << "Queue is empty" << endl;
return;
}
cout << "Queue elements: ";
for (int i = 0; i < count; i++) {
cout << arr[(front + i) % capacity] << " ";
}
cout << endl;
}
};
int main() {
Queue q(5);
q.enqueue(10);
q.enqueue(20);
q.enqueue(30);
q.display();
cout << "Dequeued: " << q.dequeue() << endl;
cout << "Front: " << q.frontElement() << endl;
q.display();
return 0;
}
Output:
Queue elements: 10 20 30
Dequeued: 10
Front: 20
Queue elements: 20 30
A binary search tree is a hierarchical structure where each node has at most two children. The left child contains values less than the parent, and the right child contains values greater than the parent. This arrangement enables efficient searching, insertion, and deletion operations.
BST Operations
- insert(value): Add a new value to the tree
- search(value): Find a value in the tree
- delete(value): Remove a value from the tree
- traversals: Visit all nodes (preorder, inorder, postorder)
C++ Implementation
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node* left;
Node* right;
Node(int value) {
data = value;
left = nullptr;
right = nullptr;
}
};
class BST {
private:
Node* root;
Node* insertRecursive(Node* node, int value) {
if (node == nullptr) {
return new Node(value);
}
if (value < node->data) {
node->left = insertRecursive(node->left, value);
} else if (value > node->data) {
node->right = insertRecursive(node->right, value);
}
return node;
}
bool searchRecursive(Node* node, int value) {
if (node == nullptr) {
return false;
}
if (value == node->data) {
return true;
} else if (value < node->data) {
return searchRecursive(node->left, value);
} else {
return searchRecursive(node->right, value);
}
}
void inorderTraversal(Node* node) {
if (node != nullptr) {
inorderTraversal(node->left);
cout << node->data << " ";
inorderTraversal(node->right);
}
}
void preorderTraversal(Node* node) {
if (node != nullptr) {
cout << node->data << " ";
preorderTraversal(node->left);
preorderTraversal(node->right);
}
}
void postorderTraversal(Node* node) {
if (node != nullptr) {
postorderTraversal(node->left);
postorderTraversal(node->right);
cout << node->data << " ";
}
}
Node* findMin(Node* node) {
while (node->left != nullptr) {
node = node->left;
}
return node;
}
Node* deleteRecursive(Node* node, int value) {
if (node == nullptr) {
return nullptr;
}
if (value < node->data) {
node->left = deleteRecursive(node->left, value);
} else if (value > node->data) {
node->right = deleteRecursive(node->right, value);
} else {
// Node to delete found
if (node->left == nullptr && node->right == nullptr) {
delete node;
return nullptr;
}
if (node->left == nullptr) {
Node* temp = node->right;
delete node;
return temp;
}
if (node->right == nullptr) {
Node* temp = node->left;
delete node;
return temp;
}
Node* temp = findMin(node->right);
node->data = temp->data;
node->right = deleteRecursive(node->right, temp->data);
}
return node;
}
public:
BST() {
root = nullptr;
}
void insert(int value) {
root = insertRecursive(root, value);
}
bool search(int value) {
return searchRecursive(root, value);
}
void deleteNode(int value) {
root = deleteRecursive(root, value);
}
void inorder() {
cout << "Inorder: ";
inorderTraversal(root);
cout << endl;
}
void preorder() {
cout << "Preorder: ";
preorderTraversal(root);
cout << endl;
}
void postorder() {
cout << "Postorder: ";
postorderTraversal(root);
cout << endl;
}
};
int main() {
BST tree;
// Insert values: 50, 30, 70, 20, 40, 60, 80
tree.insert(50);
tree.insert(30);
tree.insert(70);
tree.insert(20);
tree.insert(40);
tree.insert(60);
tree.insert(80);
tree.inorder(); // Output: 20 30 40 50 60 70 80
tree.preorder(); // Output: 50 30 20 40 70 60 80
tree.postorder(); // Output: 20 40 30 60 80 70 50
cout << "Search 40: " << (tree.search(40) ? "Found" : "Not Found") << endl;
cout << "Search 100: " << (tree.search(100) ? "Found" : "Not Found") << endl;
tree.deleteNode(50);
cout << "After deleting 50:" << endl;
tree.inorder();
return 0;
}
An AVL tree is a self-balancing binary search tree where the difference in heights between left and right subtrees of any node is at most 1. This ensures O(log n) time complexity for operations.
Rotations for Balancing
When the balance factor becomes greater than 1 or less than -1, we perform rotations:
- Left Rotation (LL): When right subtree is taller
- Right Rotation (RR): When left subtree is taller
- Left-Right Rotation (LR): Double rotation
- Right-Left Rotation (RL): Double rotation
C++ Implementation
#include <iostream>
using namespace std;
class AVLNode {
public:
int key;
AVLNode* left;
AVLNode* right;
int height;
AVLNode(int k) {
key = k;
left = nullptr;
right = nullptr;
height = 1;
}
};
class AVLTree {
private:
AVLNode* root;
int height(AVLNode* node) {
if (node == nullptr) return 0;
return node->height;
}
int getBalance(AVLNode* node) {
if (node == nullptr) return 0;
return height(node->left) - height(node->right);
}
AVLNode* rightRotate(AVLNode* y) {
AVLNode* x = y->left;
AVLNode* T2 = x->right;
x->right = y;
y->left = T2;
y->height = max(height(y->left), height(y->right)) + 1;
x->height = max(height(x->left), height(x->right)) + 1;
return x;
}
AVLNode* leftRotate(AVLNode* x) {
AVLNode* y = x->right;
AVLNode* T2 = y->left;
y->left = x;
x->right = T2;
x->height = max(height(x->left), height(x->right)) + 1;
y->height = max(height(y->left), height(y->right)) + 1;
return y;
}
AVLNode* insertRecursive(AVLNode* node, int key) {
if (node == nullptr) {
return new AVLNode(key);
}
if (key < node->key) {
node->left = insertRecursive(node->left, key);
} else if (key > node->key) {
node->right = insertRecursive(node->right, key);
} else {
return node;
}
node->height = 1 + max(height(node->left), height(node->right));
int balance = getBalance(node);
// Left Left Case
if (balance > 1 && key < node->left->key) {
return rightRotate(node);
}
// Right Right Case
if (balance < -1 && key > node->right->key) {
return leftRotate(node);
}
// Left Right Case
if (balance > 1 && key > node->left->key) {
node->left = leftRotate(node->left);
return rightRotate(node);
}
// Right Left Case
if (balance < -1 && key < node->right->key) {
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
void inorder(AVLNode* node) {
if (node != nullptr) {
inorder(node->left);
cout << node->key << " ";
inorder(node->right);
}
}
public:
AVLTree() {
root = nullptr;
}
void insert(int key) {
root = insertRecursive(root, key);
}
void display() {
cout << "AVL Inorder: ";
inorder(root);
cout << endl;
}
};
int main() {
AVLTree avl;
avl.insert(10);
avl.insert(20);
avl.insert(30); // Triggers left rotation
avl.insert(40);
avl.insert(50);
avl.insert(25);
avl.display();
return 0;
}
In Tanzania, these data structures run quietly behind everyday services. A daladala smart-card system might use a queue to process boarding taps in the order they happen, a graph to represent the network of routes and stops across a city like Mwanza (so it can find a path between two stops), and a binary search tree or hash table to look up a passenger's card number among thousands in a fraction of a second — keeping the queue at a busy stand moving quickly.
Swali
In a stack implemented using a class in C++, what happens when the pop() operation is called on an empty stack?
Ingia ili kuwasilisha jibu lako na lihesabiwe katika umahiri wako.
Ingia ili kufanya mazoeziMwalimu
Umekwama? Niulize chochote kuhusu mada hii.
Ingia ili kumuuliza Mwalimu wa AI wa Sonza kuhusu swali hili.
Ingia ili kuuliza