Stacks

Introduction, Stack Operations, Stack Implementation using Arrays, Applications of

Stacks.
Introduction
• A stack is a linear data structure that follows the LIFO (Last In, First
Out) principle.
• The last element added to the stack is the first one to be removed.
Analogy: Think of a stack of plates – you can only add or remove plates
from the top.
Key Concepts:
• Top: The topmost element of the stack.
• Push: Adding an element to the top of the stack.
• Pop: Removing an element from the top of the stack.
Stack Operations

1. Push: Adds an element to the top of the stack. If the stack is full, it
results in an overflow.

2. Pop: Removes the top element from the stack. If the stack is empty,
it results in an underflow.
3. Peek/Top: View the top element without removing it.

4. isEmpty: Check if the stack is empty.

Stack implementation using array
 // Peek operation
#include <stdio.h> void peek() {
#define SIZE 5 if (top == -1)
printf("Stack is empty\n");
int stack[SIZE], top = -1; else
printf("Top element is %d\n", stack[top]);
// Push operation }// Display stack elements
void push(int value) { void display() {
if (top == SIZE - 1) if (top == -1)
printf("Stack Overflow\n"); printf("Stack is empty\n");
else { else {
stack[++top] = value; printf("Stack elements: ");
printf("%d pushed to stack\n", value); for (int i = top; i >= 0; i--)
} printf("%d ", stack[i]);
} printf("\n");
}
// Pop operation } void main() {
void pop() { push(10);
if (top == -1) push(20);
printf("Stack Underflow\n"); push(30);
else display();
printf("%d popped from stack\n", stack[top--]); peek();
} pop();
display(); }
 Explanation of push Function with Sample Values
• Stack Size (SIZE) = 5
• Initial top = -1 (stack is empty)
We will insert (push) the values: 10, 20, 30, 40, 50, 60 one by one.
 Step-by-Step Execution of pop Operation
If we call the function, pop() five times all the 5 elements will be removed. If we
try to call the 6th time, it will display as Stack underflow.
Applications of Stacks
• A stack is a Last In, First Out (LIFO) data structure, meaning the last
element added is the first to be removed.
• Stacks are widely used in programming for expression evaluation,
memory management, backtracking, recursion handling and string
reverse etc .
Expression Evaluation Using Stacks

Stack operations are used in evaluating arithmetic expressions that follow operator
precedence rules.
Example: Evaluating a + b * c
Multiplication (*) is evaluated before addition (+).
The stack stores operators and operands to evaluate correctly.
Stacks Converts expressions without ambiguity ie Infix to Prefix/Postfix
Conversion of Infix to Prefix and Postfix Using
Stack
• A stack is useful for converting infix expressions (which we naturally write, like A
+ B * C) into prefix (Polish notation) and postfix (Reverse Polish notation).

Infix Notation → Operators appear between operands (e.g., A + B).

1. Prefix Notation (Polish Notation) → Operators appear before operands (e.g.,
+AB).
2. Postfix Notation (Reverse Polish Notation, RPN) → Operators appear after
operands (e.g., AB+).

• The stack helps handle operator precedence and associativity systematically.

In mathematical expressions, infix notation is the standard way we
write expressions (e.g., A + B * C). However, computers find prefix
(Polish notation) and postfix (Reverse Polish notation) easier to
evaluate. We use a stack to handle operator precedence and
associativity while converting from infix to prefix or postfix.
1. Infix to Postfix Conversion (Using Stack)
Rules for conversion:

1. Operands (A-Z, 0-9) → Directly added to the result.

2. *Operators (+, -, , /, ^) → Use a stack:

o If the stack is empty, push the operator.

o If the operator has higher precedence than the top of the stack, push it.

o If the operator has lower or equal precedence, pop from the stack and add to the result
until the stack is empty or a lower precedence operator is found.

3. Parentheses Handling:

o Push ( onto the stack.

o When ) is encountered, pop everything until ‘(‘ is found.

4. After scanning, pop all remaining operators from the stack and add to the result.
Example: Infix to Postfix
Infix to Prefix Conversion
Steps to Convert Infix to Prefix:
1.Reverse the given infix expression.
2.Convert it to postfix using the same method as above.
3.Reverse the postfix expression to get prefix.
Example 2: Convert A + B * C to Prefix
Step 1: Reverse the Expression
Original Infix: A + B * C
Reversed Infix: C * B + A
Infix to Postfix Conversion :
Example with Parentheses
Convert (A + B) * (C - D) to Postfix 1. Infix Expression: ( A + B ) * ( C - D )
2. Step-by-Step Conversion:

Final Postfix Expression:

AB+CD−∗
Infix to Prefix Conversion :
Example with Parentheses
Step 1: Reverse the Infix Expression
When converting to prefix, we first reverse the given infix
expression and swap ‘(‘ with ‘)’ and vice versa.
Original Infix:
(A+B)∗(C−D)
Reversed Expression (Swapping Parentheses):
(D−C)∗(B+A)
Stack-Based Memory Management

Stacks manage function calls in programming languages.

Local variables, return addresses, and function parameters are
stored on the stack.
Each function call creates a new stack frame, and when the function
completes, it is popped from the stack.
Backtracking Using Stacks

Stacks help track decision points in recursive algorithms.

Used in:
• Undo/Redo in applications

By pushing and popping states, backtracking efficiently explores

possibilities.
QUEUES
Introduction to Queues

• A queue is a linear data structure that follows the FIFO (First In, First
Out) principle. This means:
• The first inserted element is the first to be removed.
• Similar to a queue in real life (e.g., a line of people waiting for a
service).
Characteristics of a Queue
• Insertion happens at the rear (end)
Deletion happens at the front (beginning)
FIFO ordering is maintained
Queue Operations
The fundamental operations in a queue are:
Operation Description
Inserts an element at the rear of the
Enqueue
queue
Removes an element from the front of
Dequeue
the queue
Retrieves the front element without
Peek/Front
deleting it
IsEmpty Checks if the queue is empty
Checks if the queue is full (in a fixed-size
IsFull
queue)
Queue Implementation using
Arrays
 // Function to remove (dequeue) an integer from the
#include <stdio.h> queue
#include <stdlib.h> int dequeue() {
if (start == end) {
#define MAX 5 // Maximum queue size printf("Queue is empty.\n");
return -1;
int arr[MAX]; // Array to store integers }
int start = 0, end = 0; // Front and rear positions return arr[start++]; // Return and move front pointer
}
// Function to insert an integer into the queue // Function to display queue elements
void enqueue(int item) { void displayQueue() {
if (end == MAX) { if (start == end) {
printf("Queue is full. Cannot add new printf("Queue is empty.\n");
items.\n"); return;
return; }
} printf("Queue contents: ");
arr[end] = item; // Store item in queue for (int i = start; i < end; i++) {
end++; // Move rear printf("%d ", arr[i]);
} }
printf("\n");
}
int main() {
Expected Output
// Insert elements into queue
enqueue(10);
enqueue(20);
Inserted: 10
enqueue(30);
Inserted: 20
Inserted: 30
// Display queue
Queue contents: 10 20 30
displayQueue();
Dequeued: 10
Queue contents: 20 30
// Remove an element
Dequeued: 20
printf("Dequeued: %d\n",
Queue contents: 30
dequeue());
Dequeued: 30
Queue is empty.
// Display queue after deletion
Queue contents:
displayQueue();
Queue is empty.
Dequeued: -1
return 0;
}
 Queue State
Step Operation start end
(arr[] )
1 enqueue(10) [10] 0 1
2 enqueue(20) [10, 20] 0 2
3 enqueue(30) [10, 20, 30] 0 3
4 dequeue() [20, 30] 1 3
5 dequeue() [30] 2 3
6 enqueue(40) [30, 40] 2 4
7 dequeue() [40] 3 4
[] (Queue
8 dequeue() 4 4
Empty)
Limitation of a Simple Queue
A simple queue (FIFO) cannot reuse memory after dequeuing elements. Let's
demonstrate this disadvantage with a small program.
#include <stdio.h> void displayQueue() {
#define SIZE 5 if (start == end) {
printf("Queue is empty!\n");
int queue[SIZE]; return;
int start = 0, end = 0; }
printf("Queue contents: ");
void enqueue(int value) { for (int i = start; i < end; i++)
if (end == SIZE) { printf("%d ", queue[i]);
printf("Queue is full (even if space is available)!\n"); printf("\n");
return; }
} int main() {
queue[end++] = value; enqueue(10);
printf("Inserted: %d\n", value); enqueue(20);
} enqueue(30);
enqueue(40);
int dequeue() { enqueue(50);
if (start == end) { displayQueue();
printf("Queue is empty!\n"); dequeue();
return -1; dequeue();
} displayQueue();
return queue[start++]; enqueue(60); // This should fit, but it doesn't!
} return 0;
}
Circular Queue
• A Circular Queue is a type of queue in which the last position is connected to the
first position to make a circular structure. Unlike a linear queue, a circular queue
reuses empty spaces efficiently when elements are dequeued.

Key Features of Circular Queue

Uses a fixed-size array with start (front) and end (rear) pointers.
Prevents memory wastage by wrapping around when the rear reaches the end.
Uses the modulus operator (% SIZE) to cycle through indices.
Efficient for scenarios where insertions and deletions happen frequently (e.g.,
CPU scheduling, buffering).
 Circular Queue (Fixing Wasted Space)
• Circular Queue allows memory reuse by using the modulus operator (% SIZE).

#include <stdio.h> void enqueue (int value) {

#define SIZE 5 if (isFull()) {
printf("Queue is full!\n");
int queue[SIZE]; return;
int start = 0, end = 0, count = 0; // count keeps track of }
elements queue[end] = value;
end = (end + 1) % SIZE;
int isFull() { count++;
return count == SIZE; printf("Inserted: %d\n", value);
} }

int isEmpty() {
return count == 0;
}
int dequeue() {
if (isEmpty()) {
printf("Queue is empty!\n"); int main() {
return -1; enqueue(10);
} enqueue(20);
int data = queue[start]; enqueue(30);
start = (start + 1) % SIZE; enqueue(40);
count--; enqueue(50);
return data;
} displayQueue();

void displayQueue() { dequeue();

if (isEmpty()) { dequeue();
printf("Queue is empty!\n");
return; displayQueue();
}
printf("Queue contents: "); enqueue(60); // Now it fits!
for (int i = 0, index = start; i < count; i++) { enqueue(70);
printf("%d ", queue[index]);
index = (index + 1) % SIZE; displayQueue();
}
printf("\n"); return 0;
} }
Notice:
Index 0 is reused for 60 after the queue
wrapped around!
start and end correctly cycle through
indices using % SIZE.
The modulus operator (%) ensures
circular movement within the array.
end = (end + 1) % SIZE; wraps (reset) the
rear pointer if it reaches the last index.
start = (start + 1) % SIZE; wraps (reset)
the front pointer if it reaches the last index.
This prevents wasted space and overflow
errors in a circular queue.
Double-Ended Queue (Deque)
• A Double-Ended Queue (Deque) is a type of queue where insertion and
deletion can be performed from both the front and rear ends.
Types of Deques
1.Input-Restricted Deque – Insertion allowed only at rear, but deletion can
be done from both ends.
2.Output-Restricted Deque – Deletion allowed only at front, but insertion
can be done from both ends.
Key Features of Deque
More flexible than a standard queue (Supports both front and rear operations).
Efficient memory utilization (No need to shift elements).
Uses circular structure to optimize space.
However, to maintain FIFO (First-In, First-Out) order, we must restrict operations as follows:

• Insertion at Rear (insertRear()) – Elements are added at the end.

Deletion from Front (deleteFront()) – Elements are removed from the front.
#include <stdio.h> // Delete from front
#define SIZE 5 void deleteFront() {
if (front == rear) {
int deque[SIZE]; printf("Queue is empty (Underflow).\n");
int front = 0, rear = 0; } else {
printf("Deleted %d from front\n", deque[front++]);
// Insert at rear }
void insertRear(int value) { }
if (rear == SIZE) {
printf("Queue is full at rear (Overflow).\n"); // Delete from rear
} else { void deleteRear() {
deque[rear++] = value; if (front == rear) {
printf("Inserted %d at rear\n", value); printf("Queue is empty (Underflow).\n");
} } else {
} printf("Deleted %d from rear\n", deque[--rear]);
}
// Insert at front }
void insertFront(int value) {
if (front == 0) {
printf("Cannot insert at front (No space at front).\n");
} else {
deque[--front] = value;
printf("Inserted %d at front\n", value);
}}
 int main() {
insertRear(10);
insertRear(20);
insertRear(30);
// Display the queue display();
void display() {
if (front == rear) { deleteFront();
printf("Queue is empty.\n"); display();
} else {
printf("Queue: "); insertFront(5); // Will fail because front == 0
for (int i = front; i < rear; i++) { display();
printf("%d ", deque[i]);
} deleteRear();
printf("\n"); display();
}
} return 0;
}
Inserted 10 at rear
Inserted 20 at rear
Inserted 30 at rear
Queue: 10 20 30
Deleted 10 from front
Queue: 20 30
Cannot insert at front (No space
at front).
Queue: 20 30
Deleted 30 from rear
Queue: 20
Priority Queue
• A Priority Queue is a special type of queue where elements are removed based
on their priority, rather than the order in which they were inserted (FIFO). The
element with the highest priority is dequeued first.
Key Features of a Priority Queue
Each element has a priority value associated with it.
The element with the highest priority is processed first, regardless of when it
was enqueued.
If two elements have the same priority, they follow FIFO order.
Can be implemented using arrays, linked lists, or heaps.
Types of Priority Queues
1.Ascending Priority Queue – The smallest priority value is dequeued first.
2.Descending Priority Queue – The largest priority value is dequeued first.
 // Function to insert an element based on priority
void insert(int value, int priority) {
if (count == SIZE) {
#include <stdio.h>
printf("Priority Queue is full!\n");
#define SIZE 5
return;
struct PriorityQueueItem {
}
int data;
int i = count - 1;
int priority;
while (i >= 0 && queue[i].priority > priority) {
};
queue[i + 1] = queue[i]; // Shift elements
// Declare the queue array using struct
i--;
struct PriorityQueueItem queue[SIZE];
}
queue[i + 1].data = value;
int count = 0;
queue[i + 1].priority = priority;
count++;
printf("Inserted: %d with priority: %d\n", value, priority);
}
 printf("Priority Queue contents: ");
for (int i = 0; i < count; i++) {
// Function to remove and return the highest priority element
printf("[%d, P%d] ", queue[i].data,
int deleteHighestPriority() { queue[i].priority);
if (count == 0) { }
printf("Priority Queue is empty!\n"); printf("\n");
return -1; }
} int main() {
return queue[--count].data; insert(10, 2);
} insert(20, 1);
// Function to display the queue insert(30, 3);
void displayQueue() { displayQueue();
if (count == 0) { printf("Deleted highest priority element: %d\n",
printf("Priority Queue is empty!\n"); deleteHighestPriority());
return; displayQueue();
} return 0; }
Insert () function working example int i = count - 1;
while (i >= 0 && queue[i].priority > priority) {
Suppose you already have this:
queue[i + 1] = queue[i]; // Shift elements
queue[0] = {value: 10, priority: 1}
queue[1] = {value: 30, priority: 3} i--;

count = 2 }
Now, you're inserting: queue[i + 1].data = value;
insert(20, 2) queue[i + 1].priority = priority;

Now i = 0, so:
queue[i + 1] = queue[1] = {value: 20, priority: 2};
Final queue:
[10(p1), 20(p2), 30(p3)]
Done — inserted in the right position with proper shifting!
based on the program in last slides
Applications of Queue
1. Operating Systems (OS):
• CPU Scheduling (Round Robin, FCFS).
• Disk Scheduling (I/O request handling).
• Print Queue (Manages print jobs).
2. Networking & Communication:
• Packet Scheduling (Routers, switches).
• Call Center Queues (Customer support).
• Message Queues (Kafka, RabbitMQ).
 3. Real-World Applications:
• Banking & Ticket Counters (FIFO service).
• Traffic Management (Toll booths, traffic lights).
• Restaurant Order System (Food ordering).
4. Computer Science & Programming:
• Job Scheduling (Task execution in servers).
• BFS Algorithm (Graph & Tree Traversal).
• Undo Mechanisms (Software history tracking).
5. AI & Cloud Computing:
• Task Scheduling (Neural networks, ML pipelines).
• Job Queues in Cloud Services (AWS Lambda, Google Cloud)