Fundamentals of
Data Structures
Learn, Apply and Build Projects
Topic: Stacks
By
Mr. Ravi Kant Sahu
(Oracle Certified Associate, Java SE8 Programmer)
Assistant Professor, Lovely Professional University
Phagwara (Punjab)
Outlines
• Introduction
• Stack Fundamentals
• Stack Operations
• Problems on Stack
• Quick Sort
• Interview Questions
© Ravi Kant Sahu, Assistant Professor (Lovely Professional University, Punjab)
Stack
• A Stack is a linear data structure that follows the LIFO(Last In First
Out) ordering.
• A stack is a list of elements in which an element may be inserted or
deleted only at one end, called the “TOP” of the Stack.
© Ravi Kant Sahu, Assistant Professor (Lovely Professional University, Punjab)
Stack
© Ravi Kant Sahu, Assistant Professor (Lovely Professional University, Punjab)
Applications of Stack
• Function calls
• Recursion
• Depth First Search
• Expression evaluation
• Memory management
© Ravi Kant Sahu, Assistant Professor (Lovely Professional University, Punjab)
Stack Operations
void push(int stack[], int size, int top, int item)
{
if(top == size-1)
cout<<“Stack is Full”;
else
{
top = top+1;
stack[top] = item;
}
}
© Ravi Kant Sahu, Assistant Professor (Lovely Professional University, Punjab)
Stack Operations
int pop(int stack[], int size, int top)
{
int item = -1;
if(top == -1)
cout<<“Stack is Empty”;
else
{
item = stack[top];
top = top-1;
}
return item;
}
© Ravi Kant Sahu, Assistant Professor (Lovely Professional University, Punjab)
Problem Solving-1
Check if given Parentheses expression is balanced or not?
[Link]
Given a string str of length N, consisting of '(' and ')' only, the task is to
check whether it is balanced or not.
Examples:
Input: str = ((()))()() Output: Balanced
Input: str = ())((()) Output: Not Balanced
© Ravi Kant Sahu, Assistant Professor (Lovely Professional University, Punjab)
Problem Solving-2
20. Valid Parentheses
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the
input string is valid.
An input string is valid if:
• Open brackets must be closed by the same type of brackets.
• Open brackets must be closed in the correct order.
• Every close bracket has a corresponding open bracket of the same type.
Examples:
• Input: ([)} Output: false
• Input: {[()]} Output: true
© Ravi Kant Sahu, Assistant Professor (Lovely Professional University, Punjab)
Problem Solving-3
234. Palindrome Linked List
Given the head of a singly linked list, return true if it is a palindrome or
false otherwise.
Example:
Input: 1->2->3->2->1 Output: true
Input: 1->4->3->4 Output: false
Input: 4->5->5->4 Output: true
© Ravi Kant Sahu, Assistant Professor (Lovely Professional University, Punjab)
Quick Sort
QUICK_SORT (A, p, r)
1. if p < r
2. then: q = PARTITION ( A, p, r)
3. QUICK_SORT (A, p, q-1)
4. QUICK_SORT (A, q+1, r)
© Ravi Kant Sahu, Assistant Professor (Lovely Professional University, Punjab)
Quick Sort
PARTITION (A, p, r)
1. Set x = A[r].
2. Set i = p-1.
3. Repeat Step 4 to 6 for j = p to r-1
4. do if A[j] <= x.
5. then Set i = i+1.
6. Exchange A[i] A[j]
[End of Loop]
7. Exchange A[i+1] A[r]
8. return i+1.
© Ravi Kant Sahu, Assistant Professor (Lovely Professional University, Punjab)
Interview Questions
1. What is the time complexity of stack operations?
2. What are the applications of a stack?
3. What is the condition of Overflow in a Stack implemented using
Array of size N?
4. How will you implement a Queue using 2 Stacks?
5. How will you implement 2 Unbounded Stacks in a Single Array?
© Ravi Kant Sahu, Assistant Professor (Lovely Professional University, Punjab)
Student Feedback (Daily)
LPU Touch
Dashboard → Skill Development Feedback → Select Course
Code(PETV71) → Submit Feedback
UMS:
UMS Navigation-----LMS------Skill Development Feedback
(Select course code: PETV71) and fill the feedback
© Ravi Kant Sahu, Assistant Professor (Lovely Professional University, Punjab)
WhatsApp Group
© Ravi Kant Sahu, Assistant Professor (Lovely Professional University, Punjab)