Data Structure
AI-414
4(3-1)
M. Mudassir Riaz
Department of Computer Sciences
The University of Faisalabad (TUF)
[Link]
unioffaisalabad
Today lecture topics:
▪ Stack Algorithms
▪ Push
▪ Pop
[Link]
unioffaisalabad
Definition of Stack:
• A Stack is a linear data structure in which insertion and deletion
of elements are done only from one end, called the top.
• It works on the principle of LIFO (Last In, First Out) —
which means the last element inserted is the first one to be
removed.
• Example:
• Think of a stack of books —
you can add or remove only the top book, not the ones below it.
[Link]
unioffaisalabad
Main Operations:
• Push: Adds (inserts) an element to the top of the stack.
Before adding, check if the stack is full (to avoid overflow).
Example: If stack = [10, 20] and we PUSH(30) → stack becomes [10, 20, 30]
• Pop: Removes the element from the top of the stack.
Before removing, check if the stack is empty (to avoid underflow).
Example: If stack = [10, 20, 30] and we POP() → 30 is removed → stack becomes [10, 20]
•Peek: Displays the element present at the top of the stack without removing it.
•Example: If stack = [10, 20, 30], then PEEK() = 30
•IsEmpty: Shows the last element.
Returns true if empty, otherwise false.
[Link]
unioffaisalabad
• Definition of PUSH:
• The PUSH operation is used to add (insert) a new element onto
the top of the stack.
It follows the LIFO (Last In, First Out) rule —
The last item added will be the first one to be removed.
• Before adding, we must check if the stack is full to avoid
overflow.
[Link]
unioffaisalabad
Example:
Let’s say our stack can hold 3 elements (MAX = 3).
Initially, the stack is empty and TOP = -1.
• Operation TOP Value Stack Content
• PUSH(10) 0 [10]
• PUSH(20) 1 [10, 20]
• PUSH(30) 2 [10, 20, 30]
• If we try PUSH(40) after the stack is full,
• it shows "Stack Overflow" message.
[Link]
unioffaisalabad
Algorithm for PUSH:
Step 1: Start
Step 2: Check if TOP == MAX - 1
If true → print "Stack Overflow" and stop
Step 3: Increase TOP by 1 → TOP = TOP + 1
Step 4: Insert the new element → STACK[TOP] = ITEM
Step 5: Print "Item inserted successfully"
Step 6: Stop
[Link]
unioffaisalabad
#include <iostream>
using namespace std;
int main() {
int stack[5]; // stack array of size 5
int top = -1; // initially stack is empty // Display elements
int item; cout << "\nStack elements are: ";
// PUSH operation for (int i = 0; i <= top; i++) {
cout << stack[i] << " ";
cout << "Enter an element to push: ";
}
cin >> item; cout << endl;
if (top == 4) { // check if stack is full
return 0;
cout << "Stack Overflow! Cannot insert." << endl;
}
} else {
top = top + 1; // increase top position
stack[top] = item; // insert item at top
cout << item << " pushed into stack successfully." << endl;
}
[Link]
unioffaisalabad
• Definition of POP Operation:
• The POP operation is used to remove (delete) the top element from
a stack.
• It follows the LIFO (Last In, First Out) principle —
The last element inserted into the stack is the first one to be
removed.
• Before removing, we must check if the stack is empty to avoid
underflow (trying to remove from an empty stack).
[Link]
unioffaisalabad
• Example:
• If stack = [10, 20, 30]
• After POP(), element 30 is removed.
• New stack = [10, 20]
• If stack = [ ] (empty)
• POP is not possible → shows "Stack Underflow"
[Link]
unioffaisalabad
Step-by-Step Working:
[Link] if the stack is empty
•If TOP == -1, it means there is no element in the stack.
•Display message: "Stack Underflow"
[Link] the stack is not empty
•Access the element at the top position → ITEM = STACK[TOP]
•Decrease TOP by 1 → TOP = TOP - 1
•Print the removed element
[Link]
[Link]
unioffaisalabad
• Example:
• Let’s say stack = [10, 20, 30] and TOP = 2
Step Action TOP Stack Content
1 POP() 2 30 is removed
2 POP() 1 20 is removed
3 POP() 0 10 is removed
4 POP() -1 Stack Underflow (empty)
[Link]
unioffaisalabad
Algorithm of POP Operation:
Step 1: Start
Step 2: Check if the stack is empty
If TOP == -1, then print "Stack Underflow" and stop
Step 3: If the stack is not empty, take out the element from the top
ITEM = STACK[TOP]
Step 4: Reduce the top position by one
TOP = TOP - 1
Step 5: Print "Deleted item is ITEM"
Step 6: Stop
[Link]
unioffaisalabad
#include <iostream> // POP operation
using namespace std; if (top == -1) {
cout << "Stack Underflow! Cannot delete." <<
int main() { endl;
int stack[5]; // stack array of size 5 } else {
int top = -1; // initially stack is empty item = stack[top]; // get top element
int item; top = top - 1; // decrease top
cout << "Deleted item is: " << item << endl;
// First, insert a few elements (PUSH manually) }
stack[++top] = 10;
stack[++top] = 20; // Display remaining elements
stack[++top] = 30; cout << "Stack after POP: ";
for (int i = 0; i <= top; i++) {
cout << "Stack before POP: "; cout << stack[i] << " ";
for (int i = 0; i <= top; i++) { }
cout << stack[i] << " "; cout << endl;
}
cout << endl; return 0;
}
[Link]
unioffaisalabad
Any Question ?