Stack
A Linear Data-Structure
Introduction
• A Stack is a linear data structure that follows a particular order in which the
operations are performed.
• The order may be LIFO(Last In First Out) or FILO(First In Last Out).
• LIFO implies that the element that is inserted last, comes out first
and FILO implies that the element that is inserted first, comes out last.
• It behaves like a stack of plates, where the last plate added is the first one to be
removed. Think of it this way:
– Pushing an element onto the stack is like adding a new plate on top.
– Popping an element removes the top plate from the stack.
Basic Stack Operation
Types of Stack:
• Fixed Size Stack : As the name suggests, a fixed size stack has a fixed
size and cannot grow or shrink dynamically. If the stack is full and an
attempt is made to add an element to it, an overflow error occurs. If
the stack is empty and an attempt is made to remove an element from
it, an underflow error occurs.
Types of Stack Cont…
• Dynamic Size Stack : A dynamic size stack can grow or shrink
dynamically. When the stack is full, it automatically increases its size
to accommodate the new element, and when the stack is empty, it
decreases its size. This type of stack is implemented using a linked
list, as it allows for easy resizing of the stack.
Basic Operations on Stack:
In order to make manipulations in a stack, there are certain operations
provided to us.
• push() to insert an element into the stack
• pop() to remove an element from the stack
• top() Returns the top element of the stack.
• isEmpty() returns true if stack is empty else false.
• isFull() returns true if the stack is full else false.
• To implement stack, we need to maintain reference to the top item.
Push Operation on Stack
Algorithm for Push Operation:
Before pushing the element to the stack, we check if the stack is full .
If the stack is full (top == Size-1) , then Stack Overflows and we cannot insert the
element to the stack.
Otherwise, we increment the value of top by 1 (top = top + 1) and the new value is
inserted at top position .
The elements can be pushed into the stack till we reach the size of the stack.
Pop Operation in Stack
Algorithm for Pop Operation:
Before popping the element from the stack, we check if the stack
is empty .
If the stack is empty (top == -1), then Stack Underflows and we cannot
remove any element from the stack.
Otherwise, we store the value at top, decrement the value of top by
1 (top = top - 1) and return the stored top value.
Peek Operation on Stack
Algorithm for Top Operation:
• Before returning the top element
from the stack, we check if the
stack is empty.
• If the stack is empty (top == -1),
we simply print "Stack is
empty".
• Otherwise, we return the
element stored at index = top .
isEmpty Operation in Stack Data Structure:
• Returns true if the stack is
empty, else false.
Algorithm for isEmpty
Operation:
• Check for the value
of top in stack.
• If (top == -1), then the stack
is empty so return true .
• Otherwise, the stack is not
empty so return false .
isFull Operation in Stack Data Structure
Returns true if the stack is full, else
false.
• Algorithm for isFull Operation:
• Check for the value of top in
stack.
• If (top == Size-1), then the stack
is full so return true.
• Otherwise, the stack is not full so
return false.
Multiple stacks(2) using a single array
• Half-Divide Approach (Fixed Partitioning)
• Space Optimization Approach (Flexible Growth from Both
Ends)
Half-Divide Approach (Fixed Partitioning)
• Stack 1 uses indices 0 to MAX/2 - 1
• Stack 2 uses indices MAX/2 to MAX - 1
Space Optimization Approach (Flexible
Growth from Both Ends)
• Stack 1 grows from the beginning (left)-0 index of the array.
• Stack 2 grows from the end (right) of the array. Start index=(size – 1)
• They grow towards each other dynamically.
if top1 == top2 - 1 then
print "Stack Overflow"
else
// Safe to push
Function PUSH1(value):
if top1 == top2 - 1 then
print "Stack Overflow in Stack 1"
else
top1 ← top1 + 1
stack[top1] ← value
Function PUSH2(value):
if top1 == top2 - 1 then
print "Stack Overflow in Stack 2"
else
top2 ← top2 - 1
stack[top2] ← value
Function POP1():
if top1 ≥ 0 then
value ← stack[top1]
top1 ← top1 - 1
return value
else
print "Stack 1 Underflow"
return -1
Function POP2():
if top2 < MAX then
value ← stack[top2]
top2 ← top2 + 1
return value
else
print "Stack 2 Underflow"
return -1
Function PEEK1():
if top1 ≥ 0 then
return stack[top1]
else
print "Stack 1 is Empty"
return -1
Function PEEK2():
if top2 < MAX then
return stack[top2]
else
print "Stack 2 is Empty"
return -1
Feature Array Stack
A collection of elements stored at
A linear data structure that follows
Definition contiguous memory locations,
LIFO (Last In, First Out) principle.
accessible by index.
Random access via indices (e.g., Access only at one end called the
Access
arr[0], arr[5]). top (push and pop operations).
Only two main operations: push
Insert, delete, or access elements
Operations (add to top) and pop (remove from
anywhere (if allowed).
top).
When you need to reverse things,
When you need fast indexed access
Use cases undo operations, parse expressions,
or storing a fixed-size list.
function call management.
Can be implemented using arrays or
Fixed size (static arrays) or dynamic
Memory linked lists; size can be fixed or
(dynamic arrays).
dynamic.
Only top element is accessible; to
Traversal Can traverse all elements easily.
get others, must pop elements.
Implement Stack using Array
• Stack is a linear data structure which follows LIFO principle. To
implement a stack using an array, initialize an array and treat its end as
the stack’s top. Implement push (add to end), pop (remove from end),
and peek (check end) operations, handling cases for an empty or full
stack.
• Step-by-step approach:
• Initialize an array to represent the stack.
• Use the end of the array to represent the top of the stack.
• Implement push (add to end), pop (remove from the end),
and peek (check end) operations, ensuring to handle empty and full stack
conditions.
Stack Operations Using Array – Pseudocode
Initialize:
stack[MAX]
top ← -1
Push(stack, value)
if top == MAX - 1 then
print "Stack Overflow"
else
top ← top + 1
stack[top] ← value
end if
Stack Operations Using Array – Pseudocode
Initialize:
stack[MAX]
top ← -1
Pop(stack)
if top == -1 then
print "Stack Underflow"
else
value ← stack[top]
top ← top - 1
return value
end if
Stack Operations Using Array – Pseudocode
Initialize:
stack[MAX]
top ← -1
Display(stack)
if top == -1 then
print "Stack is empty"
else
for i ← top to 0 step -1 do
print stack[i]
end for
end if
Stack Operations Using Array – Pseudocode
Initialize:
stack[MAX]
top ← -1
isEmpty()
return top == -1
isFull()
return top == MAX - 1
Stack Operations Using Array – Pseudocode
Initialize:
stack[MAX]
top ← -1
isEmpty()
return top == -1
isFull()
return top == MAX – 1
Stack Operations Using Array – Pseudocode
Initialize:
stack[MAX]
top ← -1
Peek(stack)
if isEmpty() then
print "Stack is empty"
else
return stack[top]
end if
Introduction to Recursion
• The process in which a function calls itself is called recursion and the
corresponding function is called a recursive function.
• A recursive algorithm takes one step toward solution and then
recursively call itself to further move. The algorithm stops once we
reach the solution.
• Since called function may further call itself, this process might
continue forever. So it is essential to provide a base case to terminate
this recursion process.
int factorial(int n) {
return n * factorial(n - 1); }
Steps to Implement Recursion
Step1 - Define a base case: Identify the simplest (or base) case for which the solution
is known or trivial. This is the stopping condition for the recursion, as it prevents the
function from infinitely calling itself.
Step2 - Define a recursive case: Define the problem in terms of smaller subproblems.
Break the problem down into smaller versions of itself, and call the function recursively
to solve each subproblem.
Step3 - Ensure the recursion terminates: Make sure that the recursive function
eventually reaches the base case, and does not enter an infinite loop.
Step4 - Combine the solutions: Combine the solutions of the subproblems to solve the
original problem.
Example 1: Factorial of a Number
Factorial(n)
fact ← 1
for i ← 1 to n do
fact ← fact × i
end for
return fact
With Recursion
#include <stdio.h>
int fact(int n) {
// BASE CONDITION
if (n == 1)
return 1;
return n * fact(n - 1);
}
int main() {
printf("Factorial of 5 : %d\n", fact(5));
return 0;
}
Sum of Natural Numbers Using Recursion
#include <stdio.h>
int sum(int n) {
// BASE CONDITION
if (n==1)
return 1;
return n+sum(n-1);
}
int main() {
printf("Sum of 5 natural numbers : %d\n", sum(5));
return 0;
}
int sum(int n) { int sum(int n) {
// BASE CONDITION // BASE CONDITION
if (n==1) if (n==1)
return 1; return 1;
return n+sum(n-1); return n+sum(n-1);
} }
int sum(int n) { int sum(int n) {
// BASE CONDITION // BASE CONDITION
if (n==1) if (n==1)
return 1; return 1;
return n+sum(n-1); return n+sum(n-1);
} }
Print n to 1
void printDescending(int n) {
if (n == 0)
return;
printf("%d ", n);
printDescending(n - 1);
}
Decimal to Binary (Recursive)
void decimalToBinary(int n) {
if (n == 0)
return;
decimalToBinary(n / 2);
printf("%d", n % 2);
}
Dry run----
decimalToBinary(13)
→ decimalToBinary(6)
→ decimalToBinary(3)
→ decimalToBinary(1)
→ decimalToBinary(0) ← base case (return)
← print 1 (1 % 2)
← print 1 (3 % 2)
← print 0 (6 % 2)
← print 1 (13 % 2)
Fibonacci Series
It’s a sequence where each term is the sum of
the two preceding ones:
0, 1, 1, 2, 3, 5, 8, 13, ...
Do it yourself.
int fibonacci(int n) {
if (n == 0)
return 0;
if (n == 1)
return 1;
return fibonacci(n - 1) + fibonacci(n - 2);
}
int main() {
int n = 10;
printf("Fibonacci series up to %d terms:\n", n);
for (int i = 0; i < n; i++) {
printf("%d ", fibonacci(i));
}
return 0;
}
Binary Search using Recursion
int binarySearch(int arr[], int low, int high, int key) {
if (low > high)
return -1; // Key not found
int mid = (low + high) / 2;
if (arr[mid] == key)
return mid; // Key found
else if (key < arr[mid])
return binarySearch(arr, low, mid - 1, key); // Search in left half
else
return binarySearch(arr, mid + 1, high, key); // Search in right half
}
Bubble Sort using Recursion
void bubbleSort(int arr[], int n) {
// Base case: If size is 1, return
if (n == 1)
return;
// Perform one pass of bubble sort
for (int i = 0; i < n - 1; i++) {
if (arr[i] > arr[i + 1]) {
// Swap arr[i] and arr[i+1]
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}} bubbleSort(arr, n - 1);}
Infix to Postfix Expression
Infix expression: The expression of the form "a operator b" (a + b) i.e.,
when an operator is in-between every pair of operands.
<operand><operator><operand>
Postfix expression: The expression of the form "a b operator" (ab+) i.e.,
When every pair of operands is followed by an operator.
<operand><operand><operator>
Operator Presidency
Operator Precedence
^ Highest
*/ Medium
+- Low
Rules For Conversion
1. If an operand (A-Z, 0-9) is encountered, add it directly to the output.
2. If an operator is encountered:
•Pop operators from the stack to the output if they have higher or
equal precedence.
•Higher precedence never come before lower, first pop higher one
then push lower one.
•Push the current operator onto the stack.
3. If an opening parenthesis ( is found, push it onto the stack.
4. If a closing parenthesis ) is found, pop operators from the stack to the
output until an opening parenthesis is encountered.
5. After scanning the entire expression, pop any remaining operators
from the stack to the output.
Example
For input: A+(B*C-(D/E^F)*G)*H
Output: ABC*DEF^/G*-H*+
Prefix to Infix Expression
•Prefix (Polish Notation): Operator comes before operands.
Example: + A B
•Infix: Operator comes between operands.
Output: A + B
•Example
• Prefix=+-*AB/CDE
•Infix= (A*B)-(C/D)+E
Algorithm for Prefix to Infix Converter
• Start scanning the prefix expression from right to left.
• If the current character is an operand (a number or a variable), push it onto a
stack.
• If the current character is an operator (+, -, *, /, ^), pop two operands from the
stack and concatenates them with the operator in between to form an infix
sub-expression. Then push the infix sub-expression onto the stack.
• Repeat steps 2 and 3 until the entire prefix expression has been scanned.
• The final infix expression will be the only item remaining on the stack.
Postfix to Infix
Start with scanning the equation from left to right and
1. if the symbol is an operand then Push it onto the stack. or else,
2. if the symbol is an operator then,
3. Pop the top 2 values from the stack.
4. Put the operator, with the values as arguments and form a string.
5. Push the resulted string back to stack.
6. If there is only one value in the stack That value in the stack is the desired
infix string.
example : AB+CD-*