Data Structure

 Data Structure

Stack

 

A stack is a linear data structure that follows the LIFO (Last In, First Out) principle.
That means the last element inserted is the first one to be removed.

 

Characteristics

1. Linear data structure
2. Follows LIFO order
3. Supports insertion and deletion from only one end called the top
4. Efficient for managing recursive function calls, undo operations, etc.

 

Basic Operations on Stack

Operation	Description
push(x)	Inserts an element x on top of the stack
pop()	Removes the top element of the stack
peek() / top()	Returns the top element
isEmpty()	Checks if the stack is empty
isFull()	Checks if the stack is full (for fixed size array implementation)

 

 

Stack Representation

Stacks can be implemented in two ways:

1. Using Arrays
2. Using Linked Lists

 

1. Stack using Array

 

Declaration

#define MAX 5

int stack[MAX];

int top = -1;

 

Push Operation

void push(int x) {

    if (top == MAX - 1)

        printf("Stack Overflow\n");

    else {

        top++;

        stack[top] = x;

    }

}

 

 Pop Operation

void pop() {

    if (top == -1)

        printf("Stack Underflow\n");

    else

        top--;

}

 

2. Stack using Linked List

 

 Node Structure

struct Node {

    int data;

    struct Node* next;

};

struct Node* top = NULL;

 

 Push Operation

void push(int x) {

    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

    newNode->data = x;

    newNode->next = top;

    top = newNode;

}

 

 Pop Operation

void pop() {

    if (top == NULL)

        printf("Stack Underflow\n");

    else {

        struct Node* temp = top;

        top = top->next;

        free(temp);

    }

}

 

Applications of Stack

1. Expression evaluation
• Infix, Prefix, Postfix conversions
2. Function calls
• Used by compilers for recursion tracking (Call Stack)
3. Undo/Redo operations
• Text editors, Photoshop, etc.
4. Parenthesis matching
• Checking balanced brackets ()[]{}
5. Backtracking
• Used in maze or puzzle solving
6. Browser history navigation
• Forward and backward operations

 

Complexity Analysis

Operation	Time Complexity	Space Complexity
Push	O(1)	O(n)
Pop	O(1)	O(n)
Peek	O(1)	O(n)

 

Real-World Examples

• Browser back button
• Undo feature in Word processors
• Reversal of a string
• Recursion call management in compilers

 

Queue

 

A Queue is a linear data structure that follows the FIFO (First In, First Out) principle.
That means the element inserted first is removed first — like a real-life queue (line) at a ticket counter.

 

Characteristics

1. Linear data structure
2. Follows FIFO order
3. Insertion happens at rear end
4. Deletion happens at front end
5. Maintains two pointers — front and rear

 

Basic Operations on Queue

Operation	Description
enqueue(x)	Insert an element x at the rear end
dequeue()	Remove an element from the front end
peek() / front()	Display the element at the front
isEmpty()	Checks if the queue is empty
isFull()	Checks if the queue is full

 

Algorithm for Queue Operations

 

 Queue Representation (Array Implementation)

 

 Declaration

#define MAX 50

int queue[MAX];

int front = -1;

int rear = -1;

 

1. ENQUEUE(x) (Insert Element)

1. If rear == MAX-1, report “Overflow”
2. Else if front == -1 && rear == -1
   → set front = rear = 0
3. Else
   → rear = rear + 1
4. Insert element: queue[rear] = x

 

2. DEQUEUE() (Remove Element)

1. If front == -1 || front > rear, report “Underflow”
2. Else, remove element: x = queue[front]
3. If front == rear → set front = rear = -1 (Queue becomes empty)
4. Else → front = front + 1

 

3. PEEK()

1. If front == -1, report “Queue Empty”
2. Else, return queue[front]

 

Example

Operation	Front	Rear	Queue Contents
enqueue(10)	0	0	10
enqueue(20)	0	1	10, 20
enqueue(30)	0	2	10, 20, 30
dequeue()	1	2	20, 30
enqueue(40)	1	3	20, 30, 40

 

 Types of Queues

Type	Description
Simple Queue	Normal queue using FIFO
Circular Queue	Last position connected back to first to form a circle
Priority Queue	Each element has a priority — high priority served first
Double Ended Queue (Deque)	Insertion and deletion from both ends

 

Applications of Queue

1. CPU scheduling (Round Robin)
2. Printer queue
3. Disk scheduling
4. Data buffer (IO devices, network packets)
5. Breadth-First Search (BFS) in graphs
6. Order processing systems

 

Complexity Analysis

Operation	Time Complexity	Space Complexity
Enqueue	O(1)	O(n)
Dequeue	O(1)	O(n)
Peek	O(1)	O(n)

 

Circular Queue

Definition

A Circular Queue is a linear data structure that follows the FIFO (First In, First Out) principle, but unlike a normal queue, the last position connects back to the first position to form a circle.

 

This structure efficiently utilizes memory and avoids the problem of wasted space in a simple queue.

 

 Characteristics

1. Follows FIFO principle
2. Uses circular indexing
3. Efficient use of memory (no wasted space)
4. Two pointers:
• front → points to the first element
• rear → points to the last element

 

Binary Tree

Definition

A Binary Tree is a non-linear data structure in which each node has at most two children —
called the left child and right child.

 

Structure of a Binary Tree Node

Each node in a binary tree consists of:

1. Data (value stored in node)
2. Left pointer (points to left child node)
3. Right pointer (points to right child node)

 

struct Node {

    int data;

    struct Node* left;

    struct Node* right;

};

 

 Important Terms

Term	Description
Root	The topmost node of a tree
Parent Node	A node that has child nodes
Child Node	A node that descends from a parent
Leaf Node	Node with no children
Siblings	Nodes having the same parent
Level	Distance from root (root is at level 0 or 1)
Height/Depth	Longest path from root to a leaf node
Degree	Number of children a node has

 

Properties of Binary Tree

1. Maximum number of nodes at level l = 2^(l - 1)
2. Maximum number of nodes in a binary tree of height h = 2^h – 1
3. Minimum height for n nodes = ⌈log₂(n + 1)⌉
4. A binary tree with n nodes has exactly n - 1 edges

 

Types of Binary Trees

Type	Description
Full Binary Tree	Every node has either 0 or 2 children
Complete Binary Tree	All levels filled except possibly last; filled from left to right
Perfect Binary Tree	All internal nodes have 2 children and all leaves are at the same level
Skewed Binary Tree	All nodes have only one child (Left-skewed or Right-skewed)
Balanced Binary Tree	Height difference between left and right subtrees ≤ 1

 

Representation of Binary Tree

1. Linked Representation
• Each node contains: data, left pointer, right pointer
• Efficient and dynamic memory usage
2. Array Representation
• Used when the tree is complete
• Root stored at index 0
• For any node at index i:
• Left child = 2*i + 1
• Right child = 2*i + 2

 

Applications of Binary Trees

1. Binary Search Trees (BST) – used for efficient searching and sorting
2. Expression Trees – for arithmetic expression evaluation
3. Syntax Trees – used by compilers
4. Heaps – used in priority queues
5. Huffman Encoding Trees – used in data compression
6. Routing Algorithms – used in networks

 

 

Complexity Analysis

Operation	Best / Average	Worst
Insertion	O(log n)	O(n)
Deletion	O(log n)	O(n)
Searching	O(log n)	O(n)
Traversal	O(n)	O(n)

 

Binary Search Tree (BST)

 

 Definition

A Binary Search Tree (BST) is a special type of binary tree in which:

1. Each node contains a key (data)
2. The left subtree of a node contains only nodes with keys less than the node’s key
3. The right subtree of a node contains only nodes with keys greater than the node’s key
4. Both left and right subtrees must also be binary search trees

 

Properties of BST

Property	Description
Ordering Property	Left child < Root < Right child
Traversal	Inorder traversal gives sorted order of elements
Uniqueness	Each node key is unique
Recursive Structure	Each subtree is itself a BST

 

 Example of BST / Traversals of BST

        50

       /  \

     30    70

    / \    / \

  20  40  60  80

 

Traversal	Order	Output (for above example)
Inorder	Left → Root → Right	20 30 40 50 60 70 80
Preorder	Root → Left → Right	50 30 20 40 70 60 80
Postorder	Left → Right → Root	20 40 30 60 80 70 50

(Inorder traversal always gives sorted order in BST)

 

 

Basic Operations on BST

Operation	Description
Insertion	Add a new node in the correct position
Deletion	Remove a node while maintaining BST property
Searching	Locate a value efficiently
Traversal	Visit nodes in different orders (Inorder, Preorder, Postorder)

 

Structure of a BST Node

struct Node {

    int data;

    struct Node *left;

    struct Node *right;

};

 

1. Insertion in BST

 

1. If tree is empty → create a new node as root.
2. If key < root->data → insert into left subtree.
3. If key > root->data → insert into right subtree.
4. Return root.

 

2. Searching in BST

1. If root is NULL, element not found.
2. If key == root->data, element found.
3. If key < root->data, search in left subtree.
4. Else search in right subtree.

 

Advantages of BST

 

1. Searching, insertion, and deletion are faster than linked lists and arrays
2. Maintains data in sorted order automatically
3. Useful for dynamic sets of data

 

Disadvantages of BST

1. Unbalanced BST may degrade performance to O(n) (like a linked list)
2. Requires additional memory for pointers
3. Must maintain balance for optimal speed (solved by AVL or Red-Black Trees)

 

Applications of BST

1. Searching and sorting large datasets
2. Symbol tables in compilers
3. Databases indexing
4. Auto-complete and spell checking
5. Implementing sets and maps

 

Complexity Analysis

Operation	Best / Average	Worst (Unbalanced)
Insertion	O(log n)	O(n)
Searching	O(log n)	O(n)
Deletion	O(log n)	O(n)
Traversal	O(n)	O(n)

 

Summary Table

 

Concept	Description
Type	Non-linear data structure
Principle	Left < Root < Right
Traversal	Inorder → Sorted order
Operations	Insert, Search, Delete
Applications	Indexing, Searching, Symbol Table