Data Structure

25. Printer spool is an example of application of

a) Stacks b) Queued c) Linked lists d) Graphs

✅ b) Queued — Correct Answer

Explanation:

 A queue is a First-In-First-Out (FIFO) data structure.

 In a printer spooler, print jobs are added to the queue as they arrive.
 The first job submitted is the first to be printed, just like a queue at a ticket counter.
 This ensures fairness and predictable processing.

Real-world analogy:

text
Job1 → Job2 → Job3 → Job4
Printer processes: Job1, then Job2, and so on.

❌ a) Stacks

Explanation:

 A stack is Last-In-First-Out (LIFO).

 If a printer used a stack, the last job added would be printed first, which is not how
printers work.
 This would be chaotic in shared environments—imagine submitting a report and
someone else's last-minute job jumps ahead.

Verdict: Not suitable for printer spooling.

❌ c) Linked lists

Explanation:

 A linked list is a flexible structure for storing elements in sequence.

 While a queue can be implemented using a linked list, the linked list itself doesn’t
enforce FIFO behavior.
 It’s more of a building block than a direct model of the spooler.

Verdict: Possible internal implementation, but not the conceptual model.

❌ d) Graphs
Explanation:

 A graph models relationships between nodes—like networks, dependencies, or routes.

 Printer spooling doesn’t involve complex relationships or traversal paths.
 No need for edges or cycles—just a straight line of jobs.

� Queue in Data Structures

� What Is a Queue?

A queue is a linear data structure that follows the FIFO (First-In-First-Out) principle. The first
element added to the queue is the first one to be removed. Think of it like a line at a ticket
counter—people are served in the order they arrive.

� Basic Operations:

Operation Description

enqueue() Add an element to the rear of the queue

dequeue() Remove an element from the front of the queue

peek() or front() View the front element without removing it

isEmpty() Check if the queue is empty

isFull() Check if the queue is full (for fixed-size queues)

� Queue Representation

Queues can be implemented using:

 Arrays (fixed size)

 Linked Lists (dynamic size)
 Circular Arrays (efficient space reuse)

� Types of Queues

�⃣ Simple Queue

 Standard FIFO behavior.

 Insert at rear, delete from front.
cpp

queue<int> q;
q.push(10); // enqueue
q.pop(); // dequeue

�⃣ Circular Queue

 The last position is connected back to the first.

 Prevents wastage of space in array-based queues.

cpp

class CircularQueue {
int front, rear, size;
int* arr;
// Logic wraps around using modulo
};

�⃣ Priority Queue

 Elements are dequeued based on priority, not arrival time.

 Higher priority elements are served first.

cpp

priority_queue<int> pq;
pq.push(50); // Highest priority

�⃣ Deque (Double-Ended Queue)

 Elements can be inserted or removed from both ends.

 Supports both FIFO and LIFO behavior.

cpp

deque<int> dq;
dq.push_front(10);
dq.push_back(20);
dq.pop_front();

�⃣ Input-Restricted & Output-Restricted Deque

 Input-Restricted: Insert at rear only, delete from both ends.

 Output-Restricted: Insert at both ends, delete from front only.
� Applications of Queues

Queues are widely used in real-world systems and computer science:

Application Description

Printer Spooling Jobs are printed in the order they arrive (FIFO)

CPU Scheduling Processes are scheduled using queues

Breadth-First Search (BFS) Graph traversal uses queues

Call Center Systems Calls are answered in order of arrival

Data Buffers Streaming data uses queues to manage flow

Task Scheduling Queues manage background tasks in OS and apps

Messaging Systems Message queues handle asynchronous communication

� Why Use Queues?

 Ensures fairness in processing tasks.

 Simplifies resource management.
 Ideal for real-time systems where order matters.
 Supports modular design in software architecture.

� Queue vs Stack (Quick Comparison)

Feature Queue (FIFO) Stack (LIFO)

Insertion Rear Top

Deletion Front Top

Use Case Scheduling, buffering Undo, recursion

Order Oldest first Newest first

� Stack in Data Structures
� What Is a Stack?

A stack is a linear data structure that follows the LIFO (Last-In-First-Out) principle. The last
element added to the stack is the first one to be removed. Think of it like a stack of plates—only
the top plate can be removed first.

� Basic Operations:

Operation Description

push() Add an element to the top of the stack

pop() Remove the top element from the stack

peek() / top() View the top element without removing it

isEmpty() Check if the stack is empty

isFull() Check if the stack is full (for fixed-size stacks)

� Stack Representation

Stacks can be implemented using:

 Arrays (fixed size, simple)

 Linked Lists (dynamic size, flexible)
 Dynamic Libraries (e.g., STL in C++, Collections in Java)

� Types of Stacks

�⃣ Simple Stack

 Standard LIFO behavior.

 Insert and remove from the top only.

cpp

stack<int> s;
s.push(10); // Add element
s.pop(); // Remove top element

�⃣ Array-Based Stack
  Uses a fixed-size array.
 Efficient but limited by predefined size.

cpp

int stack[MAX];
int top = -1;

�⃣ Linked List-Based Stack

 Each node points to the next.

 No size limitation; dynamic memory allocation.

cpp

struct Node {
int data;
Node* next;
};

�⃣ Dynamic Stack (Using STL or Libraries)

 Built-in stack classes in languages like C++, Java, Python.

 Handles memory and operations internally.

python

s = []
s.append(10) # push
s.pop() # pop

� Applications of Stack

Stacks are fundamental in many areas of computer science and real-world systems:

Application Description

Function Call Management Tracks function calls and returns (call stack)

Expression Evaluation Used in parsing and evaluating expressions (infix, postfix)

Undo Mechanism Tracks previous states in editors or apps

Syntax Parsing Compilers use stacks to check balanced parentheses and tags

Backtracking Algorithms Used in maze solving, puzzle solving (e.g., Sudoku)

 Application Description

Memory Management Stack memory allocation in programming languages

Browser History Navigating back and forth through visited pages

� Why Use Stacks?

 Efficient for managing nested structures (e.g., recursion).

 Simple to implement and use.
 Ideal for problems requiring reversal or backtracking.
 Supports modular design in compilers, interpreters, and OS.

� Stack vs Queue (Quick Comparison)

Feature Stack (LIFO) Queue (FIFO)

Insertion Top Rear

Deletion Top Front

Use Case Recursion, Undo Scheduling, Buffering

Order Newest first Oldest first

� What Is a Linked List?

A linked list is a linear data structure where elements (called nodes) are stored in non-
contiguous memory locations. Each node contains:

 Data: The actual value.

 Pointer (Link): A reference to the next node in the sequence.

Unlike arrays, linked lists allow dynamic memory allocation, making them flexible for
insertions and deletions.

� Structure of a Node

cpp

struct Node {
int data;
Node* next;
};
� Types of Linked Lists

�⃣ Singly Linked List

 Each node points to the next node.

 Traversal is one-way (forward only).

cpp

Node* head;
head->next = second;

✅ Pros: Simple, memory-efficient ❌ Cons: No backward traversal

�⃣ Doubly Linked List

 Each node has two pointers: one to the next node and one to the previous.
 Allows bidirectional traversal.

cpp

struct Node {
int data;
Node* prev;
Node* next;
};

✅ Pros: Easy to traverse both directions ❌ Cons: More memory usage due to extra pointer

�⃣ Circular Linked List

 The last node points back to the first node, forming a circle.
 Can be singly or doubly circular.

cpp

last->next = head; // Circular link

✅ Pros: Efficient for cyclic operations ❌ Cons: Careful handling required to avoid infinite
loops

�⃣ Circular Doubly Linked List

 Combines circular and doubly linked features.

 Each node links to both previous and next, and the list loops back to the start.
✅ Pros: Full flexibility with cyclic structure ❌ Cons: Complex implementation

� Applications of Linked Lists

Linked lists are widely used in systems where dynamic memory and flexible data manipulation
are required:

Application Description

Dynamic Memory Allocation OS uses linked lists to manage free memory blocks

Implementing Stacks & Queues Linked lists are used to build dynamic stacks and queues

Graph Representations Adjacency lists in graph algorithms use linked lists

Music/Video Playlists Tracks linked sequentially for navigation

Undo/Redo Functionality Doubly linked lists track user actions

Polynomial Arithmetic Terms of polynomials stored as linked nodes

Hash Tables (Chaining) Collisions handled using linked lists

� Advantages of Linked Lists

 Dynamic Size: No need to define size in advance.

 Efficient Insert/Delete: Especially in the middle of the list.
 Memory Utilization: No wasted space like in arrays.

⚠� Disadvantages of Linked Lists

 No Random Access: Must traverse from the head to access elements.

 Extra Memory: Each node stores a pointer.
 Slower Traversal: Compared to arrays due to pointer chasing.

� Linked List vs Array (Quick Comparison)

Feature Linked List Array

Dynamic Fixed
Memory
allocation size

Access Time O(n) O(1)

 Feature Linked List Array

Efficient (O(1) Costly

Insertion/Deletion
at head) (O(n))

Extra pointer
Memory Overhead None
per node
 Feature Linked List Array

Graph Data Structure

� What Is a Graph?

A graph is a non-linear data structure consisting of:

 Vertices (Nodes): Represent entities.

 Edges (Links): Represent relationships or connections between
entities.

Graphs are used to model pairwise relationships between objects. Unlike

trees, graphs can have cycles, multiple connections, and bidirectional
links.

� Formal Definition:

A graph G is defined as: $$ G = (V, E) $$ Where:

 V is a set of vertices.
 E is a set of edges connecting pairs of vertices.

� Types of Graphs

�⃣ Directed Graph (Digraph)

 Edges have direction.

 Represented as ordered pairs: (u → v)

✅ Used in: Web page links, task scheduling

�⃣ Undirected Graph

 Edges have no direction.

 Represented as unordered pairs: {u, v}

✅ Used in: Social networks, road maps

�⃣ Weighted Graph
 Feature Linked List Array

 Each edge has a weight (cost, distance, time).

✅ Used in: GPS navigation, network routing

�⃣ Unweighted Graph

 Edges have no weight.

✅ Used in: Basic relationship modeling

�⃣ Cyclic Graph

 Contains at least one cycle (path that starts and ends at the same
vertex).

✅ Used in: Feedback systems, circular dependencies

�⃣ Acyclic Graph

 No cycles present.

✅ Used in: Dependency resolution, DAGs in compilers

�⃣ Connected Graph

 There is a path between every pair of vertices.

✅ Used in: Communication networks

�⃣ Disconnected Graph

 Some vertices are isolated or unreachable.

✅ Used in: Fault-tolerant systems analysis

� Graph Representations

� Adjacency Matrix

 2D array of size V×V.

 Feature Linked List Array

 Entry (i, j) is 1 (or weight) if edge exists between vertex i and j.

✅ Fast edge lookup ❌ High space usage for sparse graphs

� Adjacency List

 Array of lists.
 Each vertex stores a list of connected vertices.

✅ Space-efficient for sparse graphs ❌ Slower edge lookup

� Edge List

 List of all edges as pairs (or triples for weighted graphs).

✅ Simple and compact ❌ Inefficient for frequent lookups

� Applications of Graphs

Graphs are foundational in computer science, networking, and real-world

systems:

Domain Application

Social Networks Users as nodes, friendships as edges

Web Crawling Pages as nodes, hyperlinks as edges

Routing Algorithms Cities as nodes, roads as weighted edges

Computer Networks Devices as nodes, connections as edges

Recommendation Systems Products/users linked by preferences

Dependency Resolution Package managers, build systems

AI & Machine Learning Graph neural networks, knowledge graphs

Scheduling Tasks as nodes, dependencies as edges

Game Development Pathfinding using graphs (A* algorithm)

 Feature Linked List Array

� Graph Traversal Techniques

� Depth-First Search (DFS)

 Explores as far as possible along each branch before backtracking.

✅ Used in: Maze solving, cycle detection

� Breadth-First Search (BFS)

 Explores all neighbors before moving to the next level.

✅ Used in: Shortest path, level-order traversal

� Why Use Graphs?

 Model complex relationships and networks.

 Enable efficient algorithms for search, optimization, and analysis.
 Support real-time systems like GPS, social media, and AI.

26. The postfix form of the expression A-B/(CD)+E is

a) ABCDE^/ b) ABCDE^/- c) AB-CDE^/* d) ABCDE^/-

Expression Notations: Infix, Prefix, and Postfix

Expressions in programming and mathematics can be written in different notations depending on

the position of operators relative to operands. These notations are crucial for parsing, evaluating,
and converting expressions in compilers and interpreters.

� 1. Infix Notation

� Definition:

In infix notation, the operator is placed between the operands.

� Example:

Code

A + B
(3 + 4) * 5

✅ Pros:

 Most natural and readable for humans.

 Commonly used in arithmetic and algebra.

❌ Cons:

 Requires parentheses and operator precedence rules to resolve ambiguity.

 Difficult for machines to parse directly.

� 2. Prefix Notation (Polish Notation)

� Definition:

In prefix notation, the operator is placed before the operands.

� Example:

Code

+ A B
* + 3 4 5

Equivalent to: (3 + 4) * 5

✅ Pros:

 No need for parentheses.

 Easier for machines to parse recursively.

❌ Cons:

 Less intuitive for humans.

 Requires stack or recursion for evaluation.

� 3. Postfix Notation (Reverse Polish Notation)

� Definition:

In postfix notation, the operator is placed after the operands.

� Example:
Code

A B +
3 4 + 5 *

Equivalent to: (3 + 4) * 5

✅ Pros:

 No need for parentheses.

 Ideal for stack-based evaluation (used in calculators and compilers).

❌ Cons:

 Harder to read and write manually.

� Conversion Between Notations

Infix Prefix Postfix

A+B +AB AB+

A+B*C +A*BCABC*+

(A + B) * C * + A B C A B + C *

� Applications
Domain Usage

Compilers Convert infix to postfix/prefix for parsing

Expression Evaluation Postfix used in stack-based evaluation

Scientific Calculators Use postfix internally

Programming Languages Abstract syntax trees use prefix/postfix

Reverse Engineering Understanding compiled code structures

� Evaluation Using Stack (Postfix Example)

Expression: 3 4 + 5 *

Steps:
 1. Push 3 → Stack: [3]
2. Push 4 → Stack: [3, 4]
3. Operator + → Pop 4 and 3 → Push result (7) → Stack: [7]
4. Push 5 → Stack: [7, 5]
5. Operator * → Pop 5 and 7 → Push result (35) → Stack: [35]

27. Given the code fragment

cpp
struct NodeType {
int data;
NodeType* next;
};

NodeType* p;
NodeType* q;
p = new NodeType;
p->data = 12;
p->next = NULL;
q = new NodeType;
q->data = 5;
q->next = p;
Which of the following expressions has the value NULL? a) p b) q c) q->next d) q->next-
>next

✅ Evaluating the Options

Expression Value Explanation

a) p Not NULL p points to a valid node with data 12

b) q Not NULL q points to a valid node with data 5

c) q->next Not NULL q->next is p, which is a valid node

d) q->next->next NULL q->next is p, and p->next is NULL

� Final Answer: d) q->next->next

28. In a circular queue we can disambiguate empty from full queues by a) Using a gap in
the array b) Incrementing queue positions by 2 instead of 1 c) Keeping a count of the
number of elements d) a and c

The correct answer is: d) a and c

✅ Explanation:

In a circular queue, the front and rear pointers wrap around the array. This creates a
challenge: when front == rear, is the queue empty or full?

To resolve this ambiguity, we can use two common techniques:

� Option a) Using a gap in the array

 This method intentionally leaves one slot unused.

 So, the queue is considered full when (rear + 1) % size == front.
 This ensures that front == rear only when the queue is empty.
 It sacrifices one slot for clarity, but simplifies logic.

� Option c) Keeping a count of the number of elements

 Maintain a separate counter that tracks how many elements are currently in the queue.
 When count == 0, the queue is empty.
 When count == size, the queue is full.
 This method uses all slots but requires extra bookkeeping.

29. Suppose we have an empty stack of integers and an empty queue of integers to begin
with, what will the following code fragment print?
cpp
for (i = 0; i < 50; i++) stackPush(i);
for (i = 0; i < 50; i++) queuePut(stackPop());
for (i = 0; i < 50; i++) stackPush(queueGet());
for (i = 0; i < 50; i++) cout << stackPop();
a) 1,2,3...50 b) 99,98,97...1 c) 0,1,2,50,49,48...6 d) 0,1,2...99
30. Which option would be the best one for implementing 'Email is forwarded to your
inbox as it arrives. You want the ability to read the messages in the order, chosen by you.'
a) Queue b) Stack c) Linked lists d) Trees

he correct answer is: c) Linked lists

Let’s unpack each option and explain why linked lists are the best fit for the scenario:

� Scenario Recap:

 Emails arrive and are forwarded to your inbox as they come.

 You want the flexibility to read them in any order you choose, not strictly first-in-first-
out or last-in-first-out.

� Option Analysis:

a) Queue

 Structure: First-In-First-Out (FIFO)

 Use Case: Ideal when processing items in the exact order they arrive.
 Limitation: You can only access the front item; no random access.
 Verdict: ❌ Not suitable if you want to read emails in any order.

b) Stack

 Structure: Last-In-First-Out (LIFO)

 Use Case: Useful for undo operations or backtracking.
 Limitation: Only the top item is accessible; no flexibility in choosing order.
 Verdict: ❌ Doesn’t allow arbitrary access to older emails.

c) Linked Lists

 Structure: A sequence of nodes where each node points to the next.

 Use Case: You can traverse the list and access any email in any order.
 Advantages:
o Dynamic memory allocation (no fixed size).
o Easy insertion and deletion at any position.
o Can be singly or doubly linked for bidirectional access.
 Verdict: ✅ Best fit for flexible email reading.

d) Trees

 Structure: Hierarchical, with parent-child relationships.

 Use Case: Great for organizing data with nested relationships (e.g., folders).
  Limitation: Not ideal for linear arrival and arbitrary access.
 Verdict: ❌ Overkill for simple inbox management.

� Final Verdict:

Linked lists offer the perfect balance of dynamic structure and flexible access, making them
ideal for managing emails that arrive sequentially but need to be read in any order.

31. One can convert a binary tree into its mirror image by traversing it in a) Inorder b)
Postorder c) Preorder d) Any order

he correct answer is: d) Any order

Let’s break it down clearly and explain why any traversal order can be used to convert a binary
tree into its mirror image — as long as the swapping of left and right children is done at every
node.

� What is a Mirror Image of a Binary Tree?

A mirror image of a binary tree is formed by swapping the left and right children of every
node in the tree.

For example:

Code

Original: Mirror:
1 1
/ \ / \
2 3 3 2

� Option Analysis

a) Inorder Traversal

 Visits: Left → Root → Right

 You can still swap left and right children at each node during traversal.
 But the swap affects the traversal path itself, so care must be taken.
 ✅ Possible, but not the most intuitive.

b) Postorder Traversal

 Visits: Left → Right → Root

 Swapping after visiting children works well.
 ✅ Effective, especially when you want to swap after processing subtrees.
c) Preorder Traversal

 Visits: Root → Left → Right

 Swapping immediately after visiting the root is straightforward.
 ✅ Very common method for mirroring trees.

d) Any order

 Since the core operation is swapping left and right children, it can be done in any
traversal order.
 The result will be a mirrored tree regardless of the order, as long as every node is visited
and swapped.

✅ Final Verdict:

d) Any order is correct — because the mirror transformation depends on the swap operation,
not the traversal sequence.

32. What is the minimum possible number of children for a node in a Binary Tree? a) 0 b)
1 c) 2 d) Cannot be known in advance

� Explanation:

In a binary tree, each node can have:

 0 children (called a leaf node)

 1 child (either left or right)
 2 children (both left and right)

So the minimum possible number of children for any node is zero — meaning the node has no
children at all.

� Option Breakdown:

Option Meaning Verdict

Node has no children (leaf
a) 0 ✅ Correct
node)
b) 1 Node has only one child ❌ Not the minimum
c) 2 Node has both children ❌ Maximum, not minimum
d) Cannot be known in
Suggests uncertainty ❌ Incorrect — we do know the
advance minimum is 0

� Example:
cpp
struct Node {
int data;
Node* left;
Node* right;
};

If both left and right are NULL, the node has 0 children — it's a leaf.