Assignment
STACKS (Implementation Using Array & Linked list +
Applications)
Submitted By: [Link] Haider, Irfan Haider, Kumail Raza
Roll No: COMPS25BSR17, COMPS25BSR20,COMPS25BSR31
Semester:3rd (Regular)
Submitted To: Muhammad Waris
Course Title: Data Structures & Algorithms
Department Of Computer Science and Information Technology
Thal University,Bhakkar
1. What is a Stack?
Stack = A linear data structure that follows LIFO rule.
LIFO = Last In, First Out
The element that is inserted last will be removed first.
Example: Stack of plates
You put Plate 1, then Plate 2, then Plate 3 on top
When you need a plate, you take Plate 3 first
Main Operations:
Push = Add element on top of stack
Pop = Remove element from top of stack
Peek/Top = See what element is on top without removing it
2. Implementation Using Array
How It Works :
A box with 10 shelves numbered 0 to 9. You also have a variable called `TOP` that remembers
which shelf is currently the top.
At Start:
Box is empty → `TOP = -1`
This means no element is in the stack
Push Operation - Adding Element:
Check: Is the box full? If `TOP = 9` then you cannot add more
If not full: Move `TOP` up by 1 → `TOP = TOP + 1`
Put the new element on that shelf
Example: Push 10, 20, 30
Start: `TOP = -1`, Box =
Push 10: `TOP = 0`, Box =
Push 20: `TOP = 1`, Box =
Push 30: `TOP = 2`, Box = [empty][10][20][30]
Pop Operation - Removing Element:
Check: Is the box empty? If `TOP = -1` then nothing to remove
If not empty: Take element from `TOP` position
Move `TOP` down by 1 → `TOP = TOP - 1`
Example: Pop from, `TOP = 2`
Pop → Remove 30, `TOP = 1`, Box =
Pop → Remove 20, `TOP = 0`, Box = [10][20][30]
3. Implementation Using Linked List
How It Works : A chain of people holding hands. Each person holds a value + holds the hand
of next person. The person at the very front is `TOP`.
At Start:
Chain is empty → `TOP = NULL`
This means no node exists
Push Operation - Adding Element:
Create a new person/node with the value
Tell this new person to hold the hand of old `TOP` person
Now make this new person the new `TOP`
Example: Push 10, 20, 30
Start: `TOP = NULL`
Push 10: New node(10) → NULL, `TOP = 10`
Push 20: New node(20) → 10, `TOP = 20`
Push 30: New node(30) → 20, `TOP = 30`
Final: `TOP → 30 → 20 → 10 → NULL`
Pop Operation - Removing Element:
Check: Is chain empty? If `TOP = NULL` then nothing to remove
If not empty: Note down value of `TOP` person
Move `TOP` to the next person in chain
Old `TOP` person leaves
Example: Pop from `TOP → 30 → 20 → 10`
Pop → Remove 30, `TOP` moves to 20
Chain now: `TOP → 20 → 10 → NULL`
4- Applications of Stack
1. Undo / Redo Feature
Where Used: MS Word, Photoshop, Canva, VS Code
How It Works:
Every action you perform - typing, deleting, applying color
Ctrl+Z =Undo
Ctrl+Y = Redo
2. Browser Back & Forward Button
Where Used: Chrome, Mobile Browser
How It Works:
You open Google → YouTube → Facebook
Each page link gets pushed onto the stack
Back button = Pop the top page and show the previous one
Forward = Uses a second stack
3. Expression Evaluation - BODMAS
Where Used: Calculator, Compiler
Example: `2 + 3 * 4`
How It Works:
Computer uses a stack to do `3 * 4 = 12` first,then `2 + 12 = 14`
Without a stack it would wrongly calculate `20`
4. Recent Apps in Mobile
Where Used : Android, iPhone recent apps button
How It Works:
You open WhatsApp → Instagram → Camera
Press recent button → Camera shows up on top
This is a stack - last used app appears first