Data Structures - Unit III & IV Notes
UNIT III: Stacks and Queues (11 Hours)
STACKS
Definition:
A stack is a linear data structure that follows the LIFO (Last In, First Out) principle.
Operations:
- push(x): Insert an element x
- pop(): Remove top element
- peek(): View top element
- isEmpty(): Check if stack is empty
Array Representation:
#define MAX 100
int stack[MAX];
int top = -1;
void push(int val) {
if (top == MAX - 1)
printf("Overflow");
else
stack[++top] = val;
int pop() {
if (top == -1)
printf("Underflow");
else
return stack[top--];
}
Data Structures - Unit III & IV Notes
Linked List Representation:
struct Node {
int data;
struct Node* next;
};
struct Node* top = NULL;
void push(int val) {
struct Node* newNode = malloc(sizeof(struct Node));
newNode->data = val;
newNode->next = top;
top = newNode;
Applications:
- Expression Evaluation
- Backtracking (Maze, Recursion)
- Function Call Management
Arithmetic Expressions:
Infix: A + B | Prefix: +AB | Postfix: AB+
Postfix Evaluation Code:
int evaluatePostfix(char* exp) {
int stack[100], top = -1;
for (int i = 0; exp[i]; i++) {
if (isdigit(exp[i]))
stack[++top] = exp[i] - '0';
else {
Data Structures - Unit III & IV Notes
int val2 = stack[top--];
int val1 = stack[top--];
switch (exp[i]) {
case '+': stack[++top] = val1 + val2; break;
case '-': stack[++top] = val1 - val2; break;
case '*': stack[++top] = val1 * val2; break;
case '/': stack[++top] = val1 / val2; break;
return stack[top];
QUEUES
Definition:
A queue is a linear data structure following FIFO (First In First Out).
Operations:
- enqueue(x): Insert at rear
- dequeue(): Delete from front
Array Representation:
#define SIZE 100
int queue[SIZE];
int front = -1, rear = -1;
void enqueue(int val) {
if (rear == SIZE - 1) printf("Overflow");
else {
if (front == -1) front = 0;
queue[++rear] = val;
Data Structures - Unit III & IV Notes
int dequeue() {
if (front == -1 || front > rear) printf("Underflow");
else return queue[front++];
Types of Queues:
- Simple Queue
- Circular Queue
- Double-Ended Queue (Deque)
- Priority Queue
UNIT IV: Trees, Graphs, Hashing (12 Hours)
BINARY TREES
Definition:
A binary tree has <= 2 children per node.
Traversals:
- Inorder: Left -> Root -> Right
- Preorder: Root -> Left -> Right
- Postorder: Left -> Right -> Root
Inorder Traversal Code:
void inorder(struct Node* root) {
if (root != NULL) {
inorder(root->left);
printf("%d ", root->data);
Data Structures - Unit III & IV Notes
inorder(root->right);
Binary Search Tree (BST):
- Left < root < Right
AVL Tree:
Self-balancing BST, balance factor between -1 to 1.
Tree Sort:
- Insert into BST
- Do Inorder Traversal
HEAPS
Definition:
Complete Binary Tree; Min-Heap (Parent <= Children), Max-Heap (Parent >= Children)
Array Representation:
- Left = 2i + 1 | Right = 2i + 2 | Parent = (i - 1)/2
GRAPHS
Definition:
Graph G = (V, E); V: vertices, E: edges
Representations:
- Adjacency Matrix
- Adjacency List
DFS Traversal Code:
void DFS(int v) {
Data Structures - Unit III & IV Notes
visited[v] = 1;
printf("%d ", v);
for (int i = 0; i < n; i++) {
if (graph[v][i] && !visited[i]) DFS(i);
HASHING
Hash Table:
Stores data at an index from a hash function.
Hash Function:
int hash(int key) {
return key % SIZE;
Collisions:
Two keys hash to same index.
Collision Resolution:
- Linear Probing
- Quadratic Probing
- Chaining
Insert with Linear Probing:
#define SIZE 10
int hashTable[SIZE];
void insert(int key) {
int index = hash(key);
while (hashTable[index] != -1)
Data Structures - Unit III & IV Notes
index = (index + 1) % SIZE;
hashTable[index] = key;
