Stack :-
A Stack is a linear data structure that follows the
principle of LIFO(Last In First Out) or FILO(First In Last
Out).
Example :
Undo operation in text editor : The most recent change
is undone first.
Browser back button : Pages visited are stored in a
stack. Pressing back goes to the most recently visited
page.
Function calls in programming : When a function calls
another, it goes on top of the call stack . The last called
function finishes first.
Key Operations on Stack Data Structures :-
Push: Adds an element to the top of the stack.
Pop: Removes the top element from the stack.
Peek/top: Returns the top element without removing it.
IsEmpty: Checks if the stack is empty.
IsFull: Checks if the stack is full (in case of fixed-size
arrays).
or
Stack :-
cap
100 top
200
arr
0 1 2 3 4 5
Here:- cap = capacity of stack
top = top most value of stack
arr = hold address of stack
If (top==-1)
{
Printf(“stack is empty”);
}
Syntax :-
struct stack
{
int cap;
int top;
int *arr;
}
Program:- in text editor
Pseudo Code/Algorithm for Stack Push Operation :
void push(struct node *st, int data)
PUSH(stack, data):
{
if stack is not full then
if ( !isFull(st) ) {
increase TOP by 1
st->top++;
put DATA at position
st-> arr[st->top] = data;
TOP in stack array
printf("Pushed %d data\n", data);
} else {
print "DATA pushed"
printf("Stack is full\n"); else
} print "Stack is full"
}
Pseudo Code/Algorithm for Stack Pop Operation :
int pop(struct node *st) { POP(stack):
if ( !isEmpty(st) ) { if stack is not empty then
data = stack[top]
int data = st-> arr[st->top];
decrease top by 1
st->top--;
return data
return data;
else
} else {
print "Stack is empty"
printf("Stack is empty\n"); return -1
return -1; //stack underflow
}
Applications of Stack:
Expression Evaluation
Used to evaluate Infix, Prefix, and Postfix expressions.
Example: Calculator solving an expression.
Expression Conversion
Converting from Infix → Postfix / Prefix and vice-versa.
Useful in compilers.
Function Calls (Recursion)
When one function calls another, the return address and local
variables are stored in stack.
Example: Recursive functions in C, C++.Undo/Redo Operations
In text editors like MS Word or Notepad, Undo (Ctrl+Z) and Redo
(Ctrl+Y) are done using stack.
Backtracking
Used in problems where you need to go back when a
wrong path is chosen.
Example: Sudoku solving.
Browser History
When you press the "Back" button in a browser, it goes to
the last visited page using a stack.
Parsing in Compilers
Stack is used for syntax analysis in compilers.
Memory Management
Runtime stack memory stores local variables, function
calls, etc.
String Reversal
A string can be reversed easily using stack.
Arithmetic Expressions:
An arithmetic expression mainly comprises of 2 parts, that are
Operands and Operators.
Operands are either numbers or variables that can be replaced
by numbers to evaluate the expressions.
Operators are symbols symbolizing the operation to be
performed between operands present in the expression.
Each operator has its priority for an expression :
Higher Priority Operators: *, /, %
Lower Priority Operators: +, -
Order of Operators:+, -, ∗, /, ^
Polish & Reverse Polish Notation :-
Polish notation, also known as prefix notation, is a
mathematical notation in which operators precede their
operands.
In contrast, there is reverse Polish notation (RPN)
(also called postfix notation), where operators follow their
operands.
Stacks are commonly used to evaluate expressions
written in reverse Polish notation.
Types of Notations :
Infix Notation
Prefix Notation
Postfix Notation
Infix Notation
infix notation is one of the ways to write arithmetic
expressions, where the operator is placed between the
operands.
This is the most common notation used in arithmetic and
is easy for humans to read but can be difficult for
computers to evaluate directly without converting it to a
different form, like postfix or prefix notation.
Example :-
A+B*C
A, B, and C are operands.
+ and * are operators.
Prefix Notation
Prefix notation is a way of writing expressions in which
the operator comes before the operands.
Rules for Prefix Notation:
Operators precede their operands.
If operators have same precedence then start from left.
Operator precedence & associativity
(),^, *, /, %, +, -
Example :-
(A + B) * (C - D)
+AB * -CD
* + A B - C D (prefix notation)
Prefix Notation Questions Answers :
1. Convert the infix expression A + B to prefix.
2. Convert the infix expression (A + B) * (C + D) to prefix.
3. Convert the infix expression A + B * C to prefix.
4. Convert the infix expression (A + B) / C to prefix.
5. Evaluate the prefix expression * + 23 4 5.
Step-by-step approach to Evaluate the prefix expression using a
stack:
Scan from right to left (opposite of postfix).
If it’s a number, push it onto the stack.
If it’s an operator (+ - * /):
Pop the top two numbers from the stack.
Apply the operator (operator first popped second popped).
Push the result back onto the stack.
After scanning everything, the stack will have the final result.
Answer 1. +AB
Answer 2. *+AB+CD
Answer 3. +A*BC
Answer 4. /+ABC
Answer 5. 135
Postfix Notation :
Postfix notation, also known as Reverse Polish Notation (RPN), is
a way of writing expressions in which the operator comes after the
operands.
If operators have same precedence then start from left.
Example :-
A+B*C
A+BC*
BC*A+
Postfix Notation Questions Answers :
1. Convert the infix expression A + B * C - D / E to postfix.
2. Evaluate the postfix expression 234*+5-.
3. Evaluate the postfix expression 92/34+*.
4. Convert the infix expression A - B / C + D to postfix.
5. Convert the infix expression (A + B) * (C - D) to postfix.
Step-by-step approach Evaluate the postfix expression
using a stack:
Scan from left to right.
If it’s a number, push it onto the stack.
If it’s an operator (+ - * /):
Pop the top two numbers from the stack.
Apply the operator (first popped op second popped).
Push the result back onto the stack.
After scanning everything, the stack will have the final
result.
Answer 1. ABC*+DE/-
Answer 2. 9
Answer 3. 18
Answer 4. ABC/-D+
Answer 5. AB+CD-*
What is Queue ?
A queue is a linear data structure that follows the First In
First Out (FIFO) principle
first element added to the queue will be the first one to be
removed.
It is similar to a real-world queue, like people standing in line.
Key Terminology :
• Enqueue: (insert) The operation of adding an element to
the back of the queue.
• Dequeue: (delete) The operation of removing an element
from the front of the queue
.
• Front: The element at the front of the queue.
• Rear (or Back): The element at the back of the
queue.
• Empty Queue: A queue with no elements.
• Size: The number of elements in the queue.
Front= -1; // when queue is empty
Rear = -1;
Enqueue (insert) :
Enqueue means inserting (adding) an element at the rear (end) of the
queue .
A queue always inserts at the rear side and removes (dequeue) from
the front side.
Steps of Enqueue :
Check overflow → If the queue is full, you cannot insert (Overflow
condition).
If not full →Increase rear by 1.
Insert the new element at queue[rear].
Pseudo code : else:
Enqueue(queue, item): rear = rear + 1
if rear == size-1: queue[rear] = item
print "Queue Overflow"
Dequeue (delete) :
Dequeue means removing (deleting) an element from the front
of the queue .
Always deletion happens from the front side in a normal queue.
Steps of Dequeue :
Check underflow → If the queue is empty, deletion is not
possible .
If not empty →Take the element at queue[front].
Increase front by 1.
Pseudo code : else:
Dequeue(queue): item = queue[front]
if front > rear: front = front + 1
print "Queue Underflow" return item
Applications of Queue :
CPU scheduling – processes wait in a queue for CPU time.
Disk & printer scheduling – I/O and print jobs handled in
order.
Customer service systems – calls, tickets, or helpdesks
use queues.
Data buffering – keyboard buffer, streaming, and IO
operations.
Network traffic management – packets stored in queues
before forwarding.
Web servers – client requests are queued and processed
one by one.
Breadth First Search (BFS) – queue used in graph
traversal.