Data Structures
Lab Assignment — Stack & Queue using Linked List
CLO-04 | 10 Marks | C++ Implementation with Dry Runs
Q1
Q1 — Stack using Linked List
Insert name characters • Display stack • Pop to reverse name [CLO-04 | 05 Marks]
Concept & Explanation
A Stack is a Last-In First-Out (LIFO) data structure. The last element pushed is the first to be popped.
Implemented here using a singly linked list where the HEAD of the list acts as the TOP of the stack.
Push Operation : A new node is created and its 'next' pointer is set to the current top.
Then 'top' is updated to the new node. Time Complexity: O(1)
Pop Operation : The top node's data is saved, 'top' advances to the next node, and
the old node is deleted. Time Complexity: O(1)
Display : Traverses from top to bottom, printing each character. O(n)
Why a Linked List? Unlike arrays, a linked list stack needs no pre-defined size.
Memory is allocated dynamically — making it memory-efficient for unknown input sizes.
C++ Code — Stack (Linked List)
#include <iostream>
#include <string>
using namespace std;
// ── Node for the linked list ──────────────────────────────────
struct Node {
char data; // stores one character
Node* next; // pointer to the node below
Node(char c) : data(c), next(NULL) {}
};
// ── Stack class built on top of a linked list ─────────────────
class Stack {
Node* top; // always points to the topmost node
public:
Stack() : top(NULL) {}
// PUSH: create a new node and link it above the current top
void push(char c) {
Node* newNode = new Node(c);
newNode->next = top; // new node points to old top
top = newNode; // top now moves up
}
// POP: remove the top node and return its data
char pop() {
if (isEmpty()) {
cout << "Stack Underflow!" << endl;
return '\0';
}
char val = top->data;
Node* temp = top;
top = top->next; // move top down
delete temp; // free memory
return val;
}
// PEEK: look at the top without removing
char peek() { return top ? top->data : '\0'; }
bool isEmpty() { return top == NULL; }
// DISPLAY: traverse from top to bottom
void display() {
if (isEmpty()) { cout << "Stack is empty." << endl; return; }
cout << "Stack (Top → Bottom): ";
Node* curr = top;
while (curr) {
cout << curr->data;
if (curr->next) cout << " → ";
curr = curr->next;
}
cout << endl;
}
};
int main() {
Stack s;
string name = "Abdullah"; // your name
// Step 1: Push each character
cout << "Pushing characters of: " << name << endl;
for (char c : name)
[Link](c);
// Step 2: Display the stack
[Link]();
// Step 3: Pop all to print name in reverse
cout << "Name in Reverse: ";
while (![Link]())
cout << [Link]();
cout << endl;
return 0;
}
Dry Run (Name = "Abdullah")
Step 1 — Pushing each character
Characters pushed one by one: A → b → d → u → l → l → a → h (h is pushed last → becomes the top)
Operation Character Stack State (Top → Bottom) top Points To
push('A') A A A
push('b') b b → A b
push('d') d d → b → A d
push('u') u u → d → b → A u
push('l') l l → u → d → b → A l
push('l') l l → l → u → d → b → A l
push('a') a a → l → l → u → d → b → A a
push('h') h h → a → l → l → u → d → b → A h
Step 2 — Display Stack
Output: Stack (Top → Bottom): h → a → l → l → u → d → b → A
Step 3 — Popping to Print Name in Reverse
Pop # Popped Char Stack Remaining Output So Far
1 h a → l → l → u → d → b → A h
2 a l → l → u → d → b → A ha
3 l l → u → d → b → A hal
4 l u → d → b → A hall
5 u d → b → A hallu
6 d b → A hallud
7 b A halludb
8 A (empty) halludbA
Final Output: Name in Reverse: halludbA
Note: Popping a LIFO stack always yields characters in reverse insertion order.
Expected Console Output
Pushing characters of: Abdullah
Stack (Top → Bottom): h → a → l → l → u → d → b → A
Name in Reverse: halludbA
Q2 — Queue using Linked List
Insert roll number digits • Dequeue all • Calculate digit sum [CLO-04 | 05 Marks]
Concept & Explanation
A Queue is a First-In First-Out (FIFO) data structure. The first element enqueued is the first dequeued.
Implemented with a linked list using TWO pointers: 'front' (dequeue side) and 'rear' (enqueue side).
Enqueue Operation : A new node is added after 'rear', then 'rear' advances. O(1)
Dequeue Operation : The 'front' node is removed and 'front' advances to next. O(1)
If queue becomes empty, 'rear' is also set to NULL.
Digit extraction : Each character of the roll number string is converted to an
integer using (c - '0'), which gives the numeric value 0–9.
Sum calculation : Each dequeued digit is added to a running total.
C++ Code — Queue (Linked List)
#include <iostream>
#include <string>
using namespace std;
// ── Node for the linked list ──────────────────────────────────
struct Node {
int data; // stores one digit
Node* next;
Node(int d) : data(d), next(NULL) {}
};
// ── Queue class built on top of a linked list ─────────────────
class Queue {
Node* front; // points to the node to be dequeued next
Node* rear; // points to the last node (enqueue here)
public:
Queue() : front(NULL), rear(NULL) {}
// ENQUEUE: add to the rear
void enqueue(int d) {
Node* newNode = new Node(d);
if (!rear) { // queue was empty
front = rear = newNode;
return;
}
rear->next = newNode; // link new node at rear
rear = newNode; // update rear pointer
}
// DEQUEUE: remove from the front and return the value
int dequeue() {
if (isEmpty()) {
cout << "Queue Underflow!" << endl;
return -1;
}
int val = front->data;
Node* temp = front;
front = front->next; // advance front
if (!front) rear = NULL; // queue became empty
delete temp;
return val;
}
bool isEmpty() { return front == NULL; }
// DISPLAY: show all elements in order
void display() {
if (isEmpty()) { cout << "Queue is empty." << endl; return; }
cout << "Queue (Front → Rear): ";
Node* curr = front;
while (curr) {
cout << curr->data;
if (curr->next) cout << " → ";
curr = curr->next;
}
cout << endl;
}
};
int main() {
Queue q;
string rollNum = "FA24-BCS-112"; // your roll number
// Only digits will be extracted and enqueued
// Step 1: Enqueue each digit
cout << "Enqueuing digits of Roll No: " << rollNum << endl;
for (char c : rollNum)
if (c >= '0' && c <= '9') // skip letters and hyphens
[Link](c - '0'); // convert char digit to int
// Show the queue before dequeuing
[Link]();
// Step 2: Dequeue all and sum
int sum = 0;
cout << "Dequeuing: ";
while (![Link]()) {
int digit = [Link]();
cout << digit << " ";
sum += digit;
}
cout << endl;
cout << "Sum of Digits: " << sum << endl;
return 0;
}
Dry Run (Roll No = "FA24-BCS-112" → Digits: 2, 4, 1, 1, 2)
Step 1 — Enqueuing each digit
Letters (F, A, B, C, S) and hyphens are skipped. Only numeric digits are enqueued: 2, 4, 1, 1, 2
Operation Digit Queue State (Front → Rear) front / rear
enqueue(2) 2 2 2 / 2
enqueue(4) 4 2 → 4 2 / 4
enqueue(1) 1 2 → 4 → 1 2 / 1
enqueue(1) 1 2 → 4 → 1 → 1 2 / 1
enqueue(2) 2 2 → 4 → 1 → 1 → 2 2 / 2
Step 2 — Dequeuing & Summing
Dequeue # Value Queue Remaining Running Sum
1 2 4 → 1 → 1 → 2 2
2 4 1 → 1 → 2 6
3 1 1 → 2 7
4 1 2 8
5 2 (empty) 10
Final Output: Sum of Digits = 2+4+1+1+2 = 10
Roll No: FA24-BCS-112 → Extracted digits: 2, 4, 1, 1, 2 → Sum = 10
The queue maintained FIFO order — digits were processed exactly as they appeared in the roll number.
Expected Console Output
Enqueuing digits of Roll No: FA24-BCS-112
Queue (Front → Rear): 2 → 4 → 1 → 1 → 2
Dequeuing: 2 4 1 1 2
Sum of Digits: 10
Viva Questions & Answers
Q1: What is a Stack and what is its access order?
A: A Stack is a linear data structure that follows LIFO (Last-In First-Out). The last element pushed is the first to be popped.
Real-world analogy: a stack of plates.
Q2: Why do we use a linked list instead of an array for the Stack/Queue?
A: Linked lists allow dynamic memory allocation — no fixed size is needed. Elements are added/removed without shifting.
Arrays waste memory if pre-allocated too large, or crash if too small.
Q3: What is Stack Underflow and Overflow?
A: Underflow: trying to pop from an empty stack. Overflow: pushing to a full stack (only relevant for array-based stacks;
linked-list stacks overflow only when system memory is exhausted).
Q4: What is the time complexity of push() and pop() operations?
A: Both push() and pop() run in O(1) — constant time — because we only update the 'top' pointer and no traversal is
needed.
Q5: What is a Queue and how does it differ from a Stack?
A: A Queue is FIFO (First-In First-Out). The element added first is removed first. Stack = LIFO (like a pile). Queue = FIFO (like
a waiting line). Queue needs two pointers (front, rear); Stack needs one (top).
Q6: What happens to 'rear' when the last element is dequeued?
A: When the last element is dequeued, 'front' becomes NULL. At that point 'rear' must also be set to NULL — otherwise
'rear' becomes a dangling pointer pointing to deleted memory.
Q7: How do you convert a character digit to an integer in C++?
A: Using the expression (c - '0'). In ASCII, character '0' = 48. So '5' - '0' = 53 - 48 = 5. This gives the numeric integer value of
any digit character 0–9.
Q8: What is the role of 'delete' in the pop/dequeue operations?
A: Since nodes are created with 'new' (heap allocation), they must be freed manually with 'delete'. Failing to do so causes a
memory leak — the program slowly consumes RAM without releasing it.
Q9: Can you implement a Queue using two Stacks? How?
A: Yes. Enqueue pushes to Stack1. For dequeue, if Stack2 is empty, pop all from Stack1 into Stack2, then pop from Stack2.
This gives amortized O(1) dequeue using two LIFO stacks.
Q10: What are real-world applications of Stacks and Queues?
A: Stack: function call stack, undo/redo, browser back-button, expression parsing. Queue: CPU scheduling, print spooling,
BFS graph traversal, message queues in OS.
Name: Abdullah | Roll Number: FA24-BCS-112 | CLO-04 | Data Structures Lab