Data Structure
CS2013
Stack
Dr. Shyamapada Mukherjee
Associate Professor
Department of Computer Science and Engineering
NIT Rourkela-769008, India
Lecture 3
August 5, 2025
1/26 Dr. Shyamapada Mukherjee Data Structure
Outline
1 Stack
2 Overflow
3 Underflow
4 Stack Representation
5 Application
6 Question
7 Time Complexity
8 Limitations
2/26 Dr. Shyamapada Mukherjee Data Structure
Stack
A Stack is a linear data structure.
Follows LIFO principle: Last In, First Out.
Figure 1: Example of stack
3/26 Dr. Shyamapada Mukherjee Data Structure
Visual Intuition: Stack
LIFO: Last In, First Out 10 Top
Push adds element on top 20
Pop removes element from top
Only the top is accessible 30
4/26 Dr. Shyamapada Mukherjee Data Structure
Stack Operations
Push(x) – Add element x to the top of the stack.
Pop() – Remove the top element from the stack.
Peek() / Top() – View the top element without removing it.
isEmpty() – Check if the stack is empty.
isFull() – (Only for fixed-size stacks) Check if the stack is full.
5/26 Dr. Shyamapada Mukherjee Data Structure
Working of a Stack
C Top
B Top B B Top
Top A A A A Top A
Push(A) Push(B) Push(C) Pop() Pop()
6/26 Dr. Shyamapada Mukherjee Data Structure
Push-pop Questions
Push(5), Push(10), Pop(), Push(3), Peek()
margan=*, label=0.
What is the final content of the stack and what is the value returned by Peek()?
Push(1), Push(2), Push(3), Pop(), Push(4), Push(5), Pop(), Pop(), Peek()
mbrgbn=*, lbbel=0.
What is the stack content after all operations?
Push(7), Push(9), Push(11), Peek(), Pop(), Peek(), Pop(), Push(15), Peek()
mcrgcn=*, lcbel=0.
Show the Peek() values and final stack content.
Push(1), Push(2), Pop(), Push(3), Push(4), Pop(), Push(5), Pop(), Pop()
mdrgdn=*, ldbel=0.
What is the maximum depth the stack reached?
7/26 Dr. Shyamapada Mukherjee Data Structure
Push-pop Questions
Push(1), Push(2), Push(3), Pop(), Push(4), Pop(), Push(5), Push(6), Pop(), Peek()
margan=*, label=0.
What are the contents of the stack at the end and what is the maximum size the stack
reached?
Push(A), Push(B), Pop(), Push(C), Push(D), Pop(), Pop(), Push(E), Push(F), Pop(),
mbrgbn=*, lbbel=0.
Peek()
What is the current top element and what is the stack content from bottom to top?
If a stack starts empty, and we perform 14 operations in total with the rule:
mcrgcn=*, lcbel=0.
Every Push adds a number, Every Pop removes top element, Final stack size is 4.
How many Push and Pop operations were performed?
8/26 Dr. Shyamapada Mukherjee Data Structure
Stack Overflow
Definition:
Occurs when trying to push an element into a full stack.
Common in fixed-size (array-based) stacks.
Operations: Push(1), Push(2), Push(3), Push(4)
Overflow!
1
Bottom of Stack
9/26 Dr. Shyamapada Mukherjee Data Structure
Stack Overflow - Code
# define SIZE 3
int stack [ SIZE ] , top = -1;
void push ( int val ) {
if ( top == SIZE - 1)
printf (" Stack Overflow \ n ") ;
else
stack [++ top ] = val ;
}
10/26 Dr. Shyamapada Mukherjee Data Structure
Stack Underflow
Definition:
Occurs when trying to pop from an empty stack.
Happens if top == -1.
Initial stack is empty, trying Pop() operation
Underflow!
Bottom of Stack
11/26 Dr. Shyamapada Mukherjee Data Structure
Stack Underflow - Code
int pop () {
if ( top == -1)
printf (" Stack Underflow \ n ") ;
else
return stack [ top - -];
}
12/26 Dr. Shyamapada Mukherjee Data Structure
How to Prevent Stack Overflow/Underflow
Check before performing operations:
Use if(top == SIZE - 1) before push
Use if(top == -1) before pop
Use dynamic data structures like linked lists for flexible stack size
13/26 Dr. Shyamapada Mukherjee Data Structure
Questions: Stack Overflow/Underflow
An array-based stack has a size of 5.
margan=*, label=0.
Operations: Push(1), Push(2), Push(3), Push(4), Push(5), Push(6)
At which operation does overflow occur and what is the stack content before overflow?
A stack has 5 elements and receives this sequence:
mbrgbn=*, lbbel=0.
Pop(), Pop(), Push(10), Pop(), Pop(), Pop()
After how many operations does the stack underflow?
If a stack has size 10, and x Push and y Pop operations are performed such that the
mcrgcn=*, lcbel=0.
stack overflows. What is the minimum value of x ´ y ?
You are allowed only 10 stack slots and must push 20 values. Each Pop frees a slot.
mdrgdn=*, ldbel=0.
What is the minimum number of Pop operations required during the 20 Pushes to avoid
overflow?
A program performs 50 Pushes and 60 Pops. How many underflows occur assuming the
mergen=*, lebel=0.
stack was empty initially?
14/26 Dr. Shyamapada Mukherjee Data Structure
Stack Representation
Array-based implementation
Linked list implementation
Stack grows in one direction
15/26 Dr. Shyamapada Mukherjee Data Structure
Stack using Array (C Code)
# define SIZE 100
int stack [ SIZE ] , top = -1;
void push ( int val ) {
if ( top == SIZE - 1)
printf (" Stack Overflow \ n ") ;
else
stack [++ top ] = val ;
}
int pop () {
if ( top == -1)
printf (" Stack Underflow \ n ") ;
else
return stack [ top - -];
}
16/26 Dr. Shyamapada Mukherjee Data Structure
Stack using Linked List (C Code)
struct Node {
int data ;
struct Node * next ;
};
void push ( struct Node ** top , int val ) {
struct Node * newNode = malloc ( sizeof ( struct Node ) ) ;
newNode - > data = val ;
newNode - > next = * top ;
* top = newNode ;
}
17/26 Dr. Shyamapada Mukherjee Data Structure
Stack using Linked List (C Code)
int pop ( struct Node ** top ) {
if (* top == NULL ) return -1;
int val = (* top ) -> data ;
* top = (* top ) -> next ;
return val ;
}
18/26 Dr. Shyamapada Mukherjee Data Structure
Applications of Stack
Expression evaluation and conversion(Infix - Postfix)
Function call management (Call stack)
Undo operations in software
Depth-First Search (DFS)
Backtracking algorithms
19/26 Dr. Shyamapada Mukherjee Data Structure
Stack in Real Life
Web browser history
Recursive function handling
Undo feature in text editors
20/26 Dr. Shyamapada Mukherjee Data Structure
Infix, Prefix, and Postfix Notation
Definitions:
Infix: Operators are written between operands. Example: A ` B
Prefix (Polish Notation): Operators are written before operands. Example: `AB
Postfix (Reverse Polish Notation): Operators are written after operands. Example:
AB`
Infix Prefix Postfix
A+B*C +A*BC ABC*+
(A + B) * (C - D) *+AB-CD AB+CD-*
(A + B) * (C - D) / (E +
/*+AB-CD+E*FG AB+CD-*EFG*+/
F * G)
21/26 Dr. Shyamapada Mukherjee Data Structure
Infix and Postfix Using Stack
1. Evaluate Postfix Expressions Using Stack
a) 5 6 2 + * 12 4 / -
b) 7 8 + 3 2 + /
2. Convert Infix to Postfix Using Stack
a) (A + B) * C
b) A + B * C - D
3. Convert Postfix to Infix Using Stack
a) AB+C*
b) ABCD+*-
22/26 Dr. Shyamapada Mukherjee Data Structure
Time Complexity
Operation Array Linked List
Push O(1) O(1)
Pop O(1) O(1)
Peek O(1) O(1)
23/26 Dr. Shyamapada Mukherjee Data Structure
Limitations of Stack
Fixed size in array implementation
No random access
Not suitable for FIFO requirements
24/26 Dr. Shyamapada Mukherjee Data Structure
Summary
Stack is a simple LIFO data structure
Core operations: Push, Pop, Peek
Applications in many algorithms
Implementation using array or linked list
25/26 Dr. Shyamapada Mukherjee Data Structure
References
References
Karumanchi, N. Data Structures and Algorithms Made Easy: Data Structure and
Algorithmic Puzzles, 5thed., CareerMonk Publications, 2016. ISBN978-8193245279
https://ia601202.us.archive.org/8/items/data-structures-and-algorithms-narasimha-
karumanchi/Data
Schaum’s Outline of Data Structures, revised edition, SeymourLipschutz. New Delhi:
McGraw-Hill Education (India) Pvt Ltd, 2014. ISBN 978-1259029967
https://gnindia.dronacharya.info/IT/3rdSem/Downloads/DataStructure/Books/DATA-
STRUCTURE-BOOK-3.pdf
26/26 Dr. Shyamapada Mukherjee Data Structure
