Data Structures Lab | C++ | Lecture Notes

Program 1
Array Implementation of Stack

🎯 What will you learn? By the end of this session you will understand: what a Stack is and
how it works in real life, how an array stores stack elements in memory, what
Push/Pop/Peek/Display operations do, how each line of the C++ code works, and how to write
your own stack program from scratch.
 SECTION 1 — WHAT IS A STACK?

🎯 Real-Life Analogy: Imagine a stack of plates in a mess/canteen. You can only add a plate
on TOP. You can only remove a plate from TOP. You cannot take a plate from the middle! This
is EXACTLY how a Stack data structure works in a computer.

1.1 The Golden Rule of Stacks: LIFO

LIFO = Last In, First Out → The LAST element added is the FIRST one to be removed.

Stack of Plates — LIFO Demo

After Push 10,20,30,40 PUSH 10 → Plate 10 placed first (bottom)

40 ← TOP PUSH 20 → Plate 20 placed on top of 10

30 PUSH 30 → Plate 30 placed on top of 20

20 PUSH 40 → Plate 40 placed on top (TOP)

POP → Plate 40 removed FIRST (LIFO!)

10
▓▓▓▓▓ BOTTOM ▓▓▓▓▓

top=3

1.2 Stack Operations

Operation What it does Real Life Analogy When it fails

PUSH Add a new element on top of Put a new plate on top of Stack is FULL (Overflow)
the stack the pile

POP Remove the top element from Take the top plate off the Stack is EMPTY
the stack pile (Underflow)

PEEK See the top element WITHOUT Look at the top plate Stack is EMPTY
removing it without lifting it

DISPLAY Show all elements from top to Count all plates from top Stack is EMPTY (nothing
bottom to bottom to show)

1.3 Stack in Memory — How Arrays Store It

An array is like a row of boxes in memory. Each box has an index (0, 1, 2...). We use a variable called top
to remember WHICH box currently holds the topmost element.

Array: stack[100] | After pushing 10, 20, 30, 40

 10 20 30 40

[0] [1] [2] [3] [4] [5] [...]

💡 Key Insight: top = 3 means stack[3] = 40 is the topmost element. top = -1 means the stack
is empty (no elements). top = size-1 means the stack is full (overflow if you try to push).
SECTION 2 — FULL CODE WALKTHROUGH (LINE BY LINE)

📖 How to Read This Section: LEFT side = the actual C++ code (exactly as you write it).
RIGHT side = a plain English explanation of what that line does and WHY it is written that way.
Read left and right together — like reading subtitles on a movie!

Block 1 — Includes & Namespace

💻 Code 📖 Explanation (Line by Line)

#include <iostream> 📦 This is like a toolbox import.

iostream stands for 'input-output stream'. It gives us
two superpowers:
• cout → to PRINT things on screen (Output)
• cin → to READ input from the keyboard (Input)
Without this line, the program cannot print or take input.

using namespace std; 🗂️ A namespace is like a surname for functions.

Without this line, you would have to write: std::cout
and std::cin every time.
With this line, you just write: cout and cin —
much shorter and cleaner!
Think of it as: 'Use everything from the std (standard)
family without typing the family name each time.'

Block 2 — The Stack Class Definition

🏫 What is a Class? A class is a blueprint — like a blueprint for building a house. The blueprint
is not the house itself; it just describes how to build one. Similarly, 'class Stack' is the blueprint
for a Stack. When we write Stack s; in main(), we are BUILDING one actual stack from that
blueprint.

💻 Code 📖 Explanation (Line by Line)

class Stack 🏛️ This declares a new class called Stack.

{
Everything between { and the closing } belongs to
this class.
Think of it as: 'I am now defining what a Stack IS and
what it can DO.'

private: 🔒 private means: NOBODY OUTSIDE the class

can touch these variables.
It's like the internal engine of a car — you don't
need to see the engine to drive the car. You just
press the accelerator.
The variables declared below (stack[], top, size) are
hidden from main().
 💻 Code 📖 Explanation (Line by Line)

int stack[100]; 📦 This creates an ARRAY of 100 integer boxes.

stack[0], stack[1], stack[2], ..., stack[99] — 100 slots
ready to hold numbers.
We chose 100 as the MAXIMUM possible size. The
actual size will be chosen by the user at runtime.
Visual: [ ][ ][ ][ ]...[ ] ← 100 empty
boxes

int top; 📍 top is the most IMPORTANT variable in the

stack.
It acts like a POINTER — it always tells us WHERE
the topmost element is.
top = -1 → Stack is empty (nothing pushed yet)
top = 0 → One element at stack[0]
top = 3 → Four elements, topmost is at stack[3]
Rule: Always push to stack[++top] and pop from
stack[top--]

int size; 📏 size stores the MAXIMUM number of elements

allowed.
The user will enter this at the start. For example: if
user enters 5, then size=5 and the stack can hold
only 5 elements.
We check: if top == size-1, stack is full (don't allow more
pushes).

📊 Memory Layout — What These 3 Variables Do Together

stack[100] in memory after user enters size=5 and pushes 10, 20, 30

10 20 30

[0] [1] [2] [3] [4] [5] [...]

top = 2 size = 5 stack[100]

Topmost element is at index 2 (value = User set max limit as The actual storage array (100 slots, only 5
30) 5 usable)

Block 3 — Constructor (Stack Initialization)

🏗️ What is a Constructor? A constructor is a special function that runs AUTOMATICALLY

when you create an object. When you write Stack s; in main(), the constructor runs immediately
— before anything else. It sets up the initial state of the stack.

💻 Code 📖 Explanation (Line by Line)

public: 🔓 public: means these functions can be called

Stack() from OUTSIDE the class (from main()).
{
 💻 Code 📖 Explanation (Line by Line)

Stack() — notice: same name as the class, NO

return type. That's how C++ identifies a constructor.
Think of it as the 'birth' function — runs the moment the
stack is created.

top = -1; 🎯 Setting top = -1 means the stack starts EMPTY.

Why -1? Because array indices start at 0. If even
one element was added, top would be 0.
So -1 is the 'nothing is here yet' state — it's below
the first valid index.
Visual: top → -1 means stack is empty (no
valid index)

cout << "Enter Stack Size 🎤 Ask the user how big they want the stack.
: ";
cin >> size; cout prints the question on screen. cin reads the
user's answer and stores it in size.
Example: User types 5. Now size = 5. The stack
can hold at most 5 elements.
This makes our code flexible — different users can
choose different sizes.

Block 4 — push() Function

🍽️ push() = Putting a new plate on top of the stack Before placing the plate, we first
CHECK: Is the stack already full? If yes → refuse (Stack Overflow). If no → place the element
and move top up by 1.

💻 Code 📖 Explanation (Line by Line)

void push() 📣 void means this function RETURNS NOTHING

{ — it just does a job.
push() is the function name. The () means it takes
no parameters — it will ask the user for the value
inside.

if(top == size - 1) 🚨 OVERFLOW CHECK — the most critical check

{ in push!
cout << "Stack
Overflow!\n"; top == size-1 means all slots are filled. Example:
return; size=5, so valid indices are 0,1,2,3,4. When top=4
} (=size-1=5-1), all 5 slots are used.
If full: print 'Stack Overflow!' and return (stop the
function immediately).
The return; here is like an emergency exit — no further
code in this function runs.

int value; 🎤 Ask the user WHAT to push.

cout << "Enter Element :
"; int value — creates a temporary box to hold the
cin >> value; number the user types.
cin >> value — reads the number from the
keyboard.
Example: User types 42. Now value = 42. Next step: put
it in the stack.
 💻 Code 📖 Explanation (Line by Line)

stack[++top] = value; ⭐ THE HEART OF PUSH — most important line!

++top means: FIRST increase top by 1, THEN use
the new top as the index.
So if top was 2, it becomes 3, and we store value in
stack[3].
Why ++top (pre-increment) and not top++?
Because we want the INCREMENTED value to be
used as the index, not the old value.
Trace: top was -1 (empty) → ++top makes it 0
→ stack[0] = 10 ✅

cout << value << " ✅ Confirmation message to the user.

inserted successfully.\n";
Prints something like: '10 inserted successfully.'
The << is the 'send to output' operator. You chain
multiple << to print several things.
\n means 'newline' — moves the cursor to next line after
printing.

📊 Step-by-Step Trace: Pushing 10, 20, 30

Step Action top before top after stack state

Start (empty stack) -1 -1 [ ][ ][ ][ ][ ] all empty

Push 10 stack[++top]=10 -1 0 [10][ ][ ][ ][ ] top→0

Push 20 stack[++top]=20 0 1 [10][20][ ][ ][ ] top→1

Push 30 stack[++top]=30 1 2 [10][20][30][ ][ ] top→2

Block 5 — pushMultiple() Function

💻 Code 📖 Explanation (Line by Line)

void pushMultiple() 📋 Ask the user HOW MANY elements to push at

{ once.
int n;
cout << "How many
n is how many elements they want to add. For
elements...?"; example, if n=3, we push 3 elements.
cin >> n; This is a convenience function — instead of calling
push() 3 times, you call this once.

for(int i = 1; i <= n; 🔄 A for loop runs the push action n times.

i++)
{ int i = 1 → start from 1 (counter)
i <= n → keep going as long as i doesn't exceed n
i++ → increase i by 1 after each loop run
Example: n=3 → loop runs for i=1, i=2, i=3 (three times)

if(top == size - 1) 🚨 OVERFLOW CHECK — same as in push().

{
cout << "Stack
Even inside the loop, we must check EVERY TIME
Overflow!\n"; before pushing.
return;
 💻 Code 📖 Explanation (Line by Line)

} Scenario: user asks to push 5 more but only 2 slots

remain — push 2, then stop when full.
The return; exits the ENTIRE pushMultiple() function, not
just the loop.

cout << "Enter Element 🔁 The SAME push logic, inside the loop.
" << i << ": ";
cin >> value; Prints: 'Enter Element 1:', 'Enter Element 2:' etc.
stack[++top] = value; (uses i to number them)
Reads each value and pushes it using stack[++top]
= value — same as single push()
After the loop finishes: 'Elements inserted successfully.'
is printed.

Block 6 — pop() Function

🍽️ pop() = Removing the top plate Before removing, we CHECK: Is the stack empty? If yes
→ refuse (Stack Underflow). If no → print the top element and reduce top by 1.

💻 Code 📖 Explanation (Line by Line)

void pop() 🚨 UNDERFLOW CHECK — check before

{ removing!
if(top == -1)
{
top == -1 means the stack is EMPTY. Nothing to
cout << "Stack
remove!
Underflow!\n"; 'Stack Underflow!' is the error — like trying to take a
return; plate from an empty pile.
} return; stops the function immediately if empty.

cout << "Deleted Element : ⭐ THE HEART OF POP — most important line!
"
<< stack[top--] << stack[top--] means: FIRST use the current top index
endl; to get the value, THEN decrease top by 1.
Why top-- (post-decrement)? Because we want to
PRINT the value at top FIRST, then reduce top.
Example: top=3, stack[3]=40 → prints 40, then top
becomes 2
endl flushes the output and moves to next line (similar to
\n but safer).

📊 Step-by-Step Trace: Popping from [10][20][30][40]

Step Action top before top after Stack State

Start (stack full) 3 3 [10][20][30][40] top→3

Pop() Print stack[3--]→40 3 2 [10][20][30][--] top→2

Pop() Print stack[2--]→30 2 1 [10][20][--][--] top→1

Pop() Print stack[1--]→20 1 0 [10][--][--][--] top→0

Pop() Print stack[0--]→10 0 -1 [--][--][--][--] top→-1 (empty!)

Block 7 — popMultiple() Function

💻 Code 📖 Explanation (Line by Line)

void popMultiple() 🚨 First check if stack is already empty.

{
if(top == -1)
Same underflow check as pop(). If empty at the
{ cout << "Stack start, no point asking how many to delete.
Underflow!\n"; return; }

int n; 🎤 Ask how many elements to remove.

cout << "How many elements
to delete? "; User enters n. We will try to pop n elements one by
cin >> n; one.

for(int i=1; i<=n && top 🔄 Loop runs n times BUT ALSO checks top != -1
!= -1; i++)
each time.
{
cout << "Deleted: " << The condition i<=n && top != -1 has TWO parts
stack[top--]; joined by &&:
} • i <= n → don't pop more than n times
• top != -1 → don't pop if already empty (safety
net!)
Example: user wants 5 pops but only 3 elements remain
→ pops 3 and stops safely.

Block 8 — peek() Function

💻 Code 📖 Explanation (Line by Line)

void peek() 👁️ peek() lets you SEE the top without removing
{ it.
if(top == -1)
{ cout << "Stack is
First check: if empty, tell the user and exit. Can't
Empty.\n"; return; } show top of an empty stack!

cout << "Top Element : " 🔍 stack[top] — Read the value at index top
<< stack[top] << WITHOUT changing top.
endl;
IMPORTANT: We use stack[top] NOT stack[top--]!
stack[top] → Just READS the value. top stays
unchanged.
stack[top--] → READS and then DECREMENTS
top (that's pop, not peek!)
Example: top=3, stack[3]=40 → prints '40'. top is still 3
after peek.

Block 9 — display() Function

💻 Code 📖 Explanation (Line by Line)

void display() 📋 display() shows ALL elements from top to

{ bottom.
if(top == -1)
 💻 Code 📖 Explanation (Line by Line)

{ cout << "Stack is Same empty check — nothing to display if stack is

Empty.\n"; return; } empty.
cout << "Stack Elements 🖨️ Print a header line before showing elements.
(Top to Bottom)\n";
Just a label to make output readable for the user.
for(int i = top; i >= 0; 🔄 Loop from top DOWN TO 0 — this is why it
i--)
prints top-to-bottom!
{
cout << stack[i] << " i = top → start from the topmost element's index
"; i >= 0 → stop after printing index 0 (the
} bottommost)
i-- → go down one index each time
Example: top=3 → prints stack[3], stack[2], stack[1],
stack[0]
Output: 40 30 20 10 (top to bottom order)

Block 10 — main() Function (The Starting Point)

🚀 main() is where your program STARTS running. Every C++ program must have exactly
one main() function. When you run the program, the computer jumps directly to main() and starts
executing from there.

💻 Code 📖 Explanation (Line by Line)

int main() 🏗️ Stack s; creates ONE Stack object called 's'.

{
Stack s;
The moment this line runs, the constructor Stack()
is automatically called.
The constructor asks: 'Enter Stack Size:' — user
types their answer — and the stack is ready.
Think of it as: 'Build me a stack and call it s. Set it up
right now.'

int choice; 🔄 do-while loop keeps the menu running until the
do user exits.
{
int choice — stores which menu option the user
picks (1–7).
do { ... } while(condition) — runs the block FIRST,
then checks the condition.
Key difference from while: do-while ALWAYS runs at
least once — the menu must show at least once.

cout << "\n===== Stack 🖨️ Print the menu options and read user's choice.
Menu =====\n";
cout << "1. Push\n"; \n at the start prints a blank line (spacing for
// ... (all menu options) readability)
cout << "\nEnter Choice: Each cout prints one menu option. All 7 options
"; (Push, Pop, Peek... Exit) are shown.
cin >> choice; cin >> choice reads which number the user typed (1 to
7).

switch(choice) 🔀 switch-case routes each choice to the right

{ function.
 💻 Code 📖 Explanation (Line by Line)

case 1: [Link](); switch(choice) checks the value of choice and

break; jumps to the matching case.
case 2:
[Link](); break; [Link]() → calls the push() function on object s
case 3: [Link](); [Link]() → calls the pop() function on object s
break; break; → MANDATORY! Without break, execution
case 4: falls through to the next case.
[Link](); break;
default: → runs when user enters something other
case 5: [Link]();
than 1–7 (invalid input).
break;
case 6: [Link]();
break;
case 7: cout<<"Program
Terminated."; break;
default:
cout<<"Invalid Choice!";
}

} while(choice != 7); 🔄 while(choice != 7) — Keep looping UNTIL user

return 0; chooses 7 (Exit).
}
After every menu selection, this condition is
checked:
• choice != 7 is TRUE → show menu again
• choice == 7 → condition is FALSE → loop exits
return 0; tells the operating system 'program ended
successfully'. 0 = no error.

📊 Complete Program Execution Flow

User
Stack s switch:
Start enters Show Read choice==7?
main() → Constructor → stack → Menu → choice → call → Exit / Loop
runs function
size
SECTION 3 — SAMPLE RUN (What You See on Screen)

What User Types (Input) What Appears on Screen (Output)

Enter Stack Size: 5 (Stack is created with max 5 elements)

Choice: 1 → Element: 10 10 inserted successfully.

Choice: 2 → How many: 3 → Elements: 20, Elements inserted successfully.

30, 40

Choice: 6 Stack Elements (Top to Bottom) 40 30

20 10

Choice: 5 Top Element : 40

Choice: 3 Deleted Element : 40

Choice: 4 → How many: 2 Deleted Element : 30 Deleted Element :

20

Choice: 6 Stack Elements (Top to Bottom) 10

Choice: 7 Program Terminated.

 SECTION 4 — KEY CONCEPTS, COMMON ERRORS &
APPLICATIONS

4.1 Key Concepts at a Glance

Concept What It Means Code Location

Stack LIFO data structure — Last In First Out class Stack

Array Fixed-size storage boxes with index numbers int stack[100]

top Tracks which index holds the TOP element. Starts int top = -1
at -1 (empty)

size Maximum number of elements the stack can hold cin >> size (in
constructor)

Stack Overflow Trying to push when stack is full (top == size-1) if(top==size-1) in push()

Stack Underflow Trying to pop/peek when stack is empty (top == -1) if(top==-1) in pop()

push: ++top Increment top FIRST, then store at that index stack[++top] = value

pop: top-- Read value at top FIRST, then decrement top stack[top--]

peek: top (no Read value at top WITHOUT changing top stack[top]
change)

do-while Menu always shows at least once; repeats until exit do{...}while(choice!=7)

switch-case Efficiently routes each menu choice to correct switch(choice) in main()

function

private / public private = hidden internals. public = usable from class members
outside

4.2 Common Errors & How to Fix Them

Error What Happens Why It Happens How to Fix

Stack Overflow Program prints 'Stack top == size-1 (array Check array full
Overflow!' and stops full) before pushing
push

Stack Underflow Program prints 'Stack top == -1 (array Check empty

Underflow!' and stops empty) before popping
pop

Using top++ instead of Wrong index used Post-increment Always use ++top
++top in push (stores at OLD top, not returns value (pre-increment) for
new top) BEFORE push
incrementing

Using --top instead of top-- Deletes wrong element Pre-decrement Always use top--
in pop changes top first (post-decrement)
for pop
 Error What Happens Why It Happens How to Fix

Missing break; in switch Multiple cases execute switch falls through to Add break; at end
unintentionally (fall- next case without of every case
through) break

Forgetting return; after Code continues after No early exit from Always add return;
overflow/underflow printing error function after error
message messages

4.3 Real-World Applications of Stack

Application How Stack is Used Your Everyday Example

Browser Back Pages visited are pushed onto a stack. You visit Page A, B, C. Press Back → C
Button Back button pops the stack. removed, B shown. Press Back → B
removed, A shown.

Undo/Redo in Every action (typing, deleting) is pushed. You type 'Hello', then delete 'o'. Press
editors Ctrl+Z pops the last action. Ctrl+Z → 'o' is restored (last action
undone).

Function Call When function A calls function B, B is main() calls push(), push() runs, returns →
Stack pushed. When B returns, B is popped main() continues. This uses the CPU's call
and A resumes. stack.

Expression Infix to Postfix conversion (Program 5 in ( 3 + 4 ) * 2 → converted to 3 4 + 2 * using

Evaluation your syllabus!) uses a stack to handle stack
operators.

Balancing Opening brackets pushed; closing { [ ( ) ] } → Each closing bracket must

Brackets brackets pop and check matching. match the most recent opening one.
 SECTION 5 — QUICK REVISION (Read Before Lab)

⚡ The 10 Things You MUST Remember: 1. Stack = LIFO (Last In First Out). 2. top starts at -
1 (empty). top = size-1 means full. 3. push: check overflow FIRST → stack[++top] = value. 4.
pop: check underflow FIRST → cout << stack[top--]. 5. peek: check empty FIRST → cout <<
stack[top] (NO decrement!). 6. display: loop from top DOWN to 0. 7. ++top (pre) for push. top--
(post) for pop. 8. break; is mandatory in every switch-case. 9. private = hidden. public =
accessible from main(). 10. do-while ensures the menu runs at least once.

5.1 Three-Level Understanding Check

Level Question Answer

🐢 Slow What does 'Stack Overflow' The stack is full. We tried to push when top == size-1.
Learner mean? The program prints 'Stack Overflow!' and stops.

🐢 Slow What is the initial value of top and top = -1. Because no element is present yet. -1 is below
Learner why? all valid indices (0,1,2...).

📚 What is the difference between pop() removes the top element (top--). peek() only
Average pop() and peek()? READS the top element (top unchanged). Both check if
empty first.

📚 Why do we use ++top in push but push: increment first, then store (pre-increment = right
Average top-- in pop? slot). pop: print current top first, then reduce (post-
decrement = right value).

🏆 Topper What happens if we remove After executing case 1 (push), execution will fall through
break; from case 1 in switch? and also execute case 2 (pushMultiple) without user
asking — a bug called switch fall-through.

🏆 Topper How would you modify this code Push each character of the string onto the stack. Pop all
to implement a 'Reverse a String' characters and print them — they come out in reverse
feature using Stack? order (LIFO property).

5.2 Try It Yourself — Extend the Code

Challenge Hint Difficulty

Add a function isFull() that returns true if stack return (top == size - 1); 🐢 Easy
is full

Add a function isEmpty() that returns true if return (top == -1); 🐢 Easy
stack is empty

Add a function count() that returns the number return (top + 1); — because top is 📚
of elements 0-indexed Medium

Modify display() to also print index numbers Print i alongside stack[i] in the for 📚
beside each element loop Medium

Add a function search(int x) to find if element x Loop through stack[0] to stack[top] 🏆 Hard
is in stack and compare
 Challenge Hint Difficulty

Use this stack to reverse a string input by the Push each char, then pop all to get 🏆 Hard
user reverse

✅ You are ready for the Lab when you can: 1. Write the full Stack class from memory
(without looking). 2. Explain what every single line does in plain English. 3. Draw the stack state
after each push and pop operation. 4. Spot and fix overflow/underflow errors instantly. 5.
Answer all three levels of revision questions above.