Basic Data Structures – Complete Study Guide UIE | 25CSH-103

BASIC DATA STRUCTURES

Complete Study Guide with Examples & Viva Q&A

Subject Code: 25CSH-103

UIE – Department of Engineering Foundations

B.E. Computer Science & Engineering

Academic Session 2025–26 | Even Semester (Jan–May 2026)

Faculty: Dr. Sheenam | E-Code: E6717 | Assistant Professor

TOPICS COVERED IN THIS GUIDE

Unit 1: Sorting Algorithms – Bubble, Insertion, Selection, Merge, Quick Sort

Unit 2: Linked Lists – Singly Linked List, Doubly Linked List, Circular Linked List

Unit 3: Stacks – Introduction, Operations, Applications (Infix/Postfix/Prefix)

Unit 4: Queues – Linear Queue, Circular Queue, Deque, Priority Queue

Dr. Sheenam | Academic Session 2025-26 Page 1

Basic Data Structures – Complete Study Guide UIE | 25CSH-103

TABLE OF CONTENTS
■ 1. SORTING ALGORITHMS
■ 1.1 Bubble Sort
■ 1.2 Insertion Sort
■ 1.3 Selection Sort
■ 1.4 Merge Sort
■ 1.5 Quick Sort
■ 1.6 Sorting Complexity Comparison

■ 2. LINKED LISTS
■ 2.1 Singly Linked List
■ 2.2 Doubly Linked List
■ 2.3 Circular Linked List

■ 3. STACKS
■ 3.1 Introduction to Stack
■ 3.2 Stack Operations (PUSH & POP)
■ 3.3 Applications of Stack

■ 4. QUEUES
■ 4.1 Introduction to Queue
■ 4.2 Operations on Queue
■ 4.3 Circular Queue

■ 5. VIVA QUESTIONS (All Topics)

Dr. Sheenam | Academic Session 2025-26 Page 2

Basic Data Structures – Complete Study Guide UIE | 25CSH-103

UNIT 1: SORTING ALGORITHMS

Bubble • Insertion • Selection • Merge • Quick Sort

Sorting is the process of arranging data elements in a specific order (ascending or descending). It improves the
efficiency of searching and makes data more readable. Sorting can be classified as Internal Sorting (all data fits in
RAM – e.g., Bubble, Insertion) and External Sorting (data stored on disk loaded in chunks – e.g., Merge Sort). A
sort is called Stable if equal elements maintain their original relative order.

1.1 Bubble Sort

Bubble Sort (also called Exchange Sort) repeatedly compares adjacent elements and swaps them if they are in the
wrong order. After each complete pass, the largest unsorted element 'bubbles up' to its correct position at the end of
the array.

How It Works – Step by Step

Consider the array: [5, 3, 8, 1, 9, 2]

Pass 1: Compare pairs (5,3)→swap → (3,5,8,1,9,2). Compare (5,8)→no swap. Compare (8,1)→swap →
(3,5,1,8,9,2). Compare (8,9)→no swap. Compare (9,2)→swap → [3,5,1,8,2,9]. (9 is now fixed.)

Pass 2: Continue comparing until 8 bubbles to second-last → [3,1,5,2,8,9]

Pass 3–5: Repeat until [1,2,3,5,8,9] — fully sorted.

Algorithm
FOR i = 0 to n-2:
FOR j = 0 to n-2-i:
IF arr[j] > arr[j+1]: SWAP arr[j] and arr[j+1]

Time & Space Complexity

Case Time Complexity Space Complexity Notes

Best Case O(n) O(1) Already sorted; optimized with flag

Average Case O(n2) O(1) Random input

Worst Case O(n2) O(1) Reverse sorted input

Bubble Sort is an in-place, stable sorting algorithm.

Q1. What is Bubble Sort and why is it called so?

■ It repeatedly swaps adjacent elements; larger elements 'bubble up' to the end like bubbles rising in water.
Q2. Is Bubble Sort stable?
■ Yes. Equal elements are never swapped, so their relative order is preserved.
Q3. What is the best-case time complexity and when does it occur?
■ O(n) – when the array is already sorted and we use an optimized version with a swap flag.
Q4. What is the difference between internal and external sorting?
■ Internal: all data fits in memory (RAM). External: data is too large; stored on disk and loaded in chunks.
Q5. When would you prefer Bubble Sort over others?

Dr. Sheenam | Academic Session 2025-26 Page 3

Basic Data Structures – Complete Study Guide UIE | 25CSH-103

■ For very small datasets or nearly sorted arrays where simplicity matters more than speed.

Dr. Sheenam | Academic Session 2025-26 Page 4

Basic Data Structures – Complete Study Guide UIE | 25CSH-103

1.2 Insertion Sort

Insertion Sort builds the sorted array one element at a time by inserting each new element into its correct position
among the already-sorted elements. Think of how you sort playing cards in your hand — you pick one card and
slide it into the right place.

How It Works – Step by Step

Array: [10, 40, 100, 20, 35, 3, 15]

Pass 1 (key=40): 40 > 10 → no shift → [10, 40, 100, 20, 35, 3, 15]

Pass 2 (key=100): 100 > 40 → [10, 40, 100, 20, 35, 3, 15]

Pass 3 (key=20): 20 < 100 and 20 < 40 → shift → [10, 20, 40, 100, 35, 3, 15]

Continue... Final: [3, 10, 15, 20, 35, 40, 100]

Algorithm
FOR K = 2 to N:
TEMP = arr[K]; J = K-1
WHILE TEMP < arr[J] AND J >= 1:
arr[J+1] = arr[J]; J = J-1
arr[J+1] = TEMP

Time & Space Complexity

Case Time Complexity Space Complexity Notes

Best Case O(n) O(1) Already sorted

Average Case O(n2) O(1) Random input

Worst Case O(n2) O(1) Reverse sorted

Insertion Sort is in-place and stable. Efficient for small or nearly-sorted datasets.

Q1. What is the basic idea of Insertion Sort?

■ Pick each element as a 'key' and insert it at the correct position in the already-sorted portion.
Q2. How many comparisons does Insertion Sort make in the best case?
■ n-1 comparisons (one per pass) when the array is already sorted.
Q3. Compare Insertion Sort and Bubble Sort.
■ Both are O(n²) in average/worst. Insertion Sort makes fewer swaps; Bubble Sort compares adjacent pairs.
Q4. Is Insertion Sort adaptive?
■ Yes — it is faster on nearly sorted data, making it adaptive.
Q5. What is the real-world analogy for Insertion Sort?
■ Sorting playing cards in hand — you pick up one card and place it in the correct position among others.

Dr. Sheenam | Academic Session 2025-26 Page 5

Basic Data Structures – Complete Study Guide UIE | 25CSH-103

1.3 Selection Sort

Selection Sort divides the array into a sorted and an unsorted portion. It repeatedly finds the minimum element
from the unsorted portion and places it at the beginning of the unsorted portion. The sorted portion grows by one
element each pass.

How It Works – Step by Step

Array: [77, 33, 44, 11, 88, 22, 66, 55]

Pass 1 (k=1): Min=11 at index 4 → swap with index 1 → [11, 33, 44, 77, 88, 22, 66, 55]

Pass 2 (k=2): Min=22 at index 6 → swap with index 2 → [11, 22, 44, 77, 88, 33, 66, 55]

Continue... Final: [11, 22, 33, 44, 55, 66, 77, 88]

Algorithm
FOR i = 0 to n-2:
min_idx = i
FOR j = i+1 to n-1:
IF arr[j] < arr[min_idx]: min_idx = j
SWAP arr[i] with arr[min_idx]

Time & Space Complexity

Case Time Complexity Space Complexity Notes

Best Case O(n2) O(1) Always scans entire unsorted region

Average Case O(n2) O(1) Random input

Worst Case O(n2) O(1) Reverse sorted input

Selection Sort is NOT stable (distant swaps may change relative order). Always O(n²) — not adaptive.

Q1. What is the key idea of Selection Sort?

■ Find the minimum element from the unsorted part and swap it with the first unsorted element.
Q2. Is Selection Sort stable?
■ No. Swapping elements over long distances can change the relative order of equal elements.
Q3. How many swaps does Selection Sort perform?
■ At most n-1 swaps — one per pass. This makes it useful when writes (swaps) are expensive.
Q4. Compare Selection Sort with Insertion Sort.
■ Both are O(n²). Selection Sort makes fewer swaps; Insertion Sort is adaptive (faster on nearly sorted data).
Q5. Can Selection Sort be applied to linked lists?
■ Yes, but it's less efficient because random access is slow on linked lists.

Dr. Sheenam | Academic Session 2025-26 Page 6

Basic Data Structures – Complete Study Guide UIE | 25CSH-103

1.4 Merge Sort

Merge Sort uses the Divide and Conquer paradigm. It recursively divides the array into two halves, sorts each half,
then merges the two sorted halves into one sorted array. It is an external sorting algorithm — ideal when data
does not fit in memory.

How It Works – Step by Step

Array: [7, 4, 9, 1, 2, 8, 10]

Divide: [7,4,9,1] and [2,8,10]

Recursively divide: [7,4] and [9,1] ... until single elements

Merge [7] and [4] → [4,7]; Merge [9] and [1] → [1,9]

Merge [4,7] and [1,9] → [1,4,7,9]

Merge [1,4,7,9] and [2,8,10] → [1,2,4,7,8,9,10]

Algorithm
mergesort(arr, beg, end):
IF beg < end:
mid = (beg + end) / 2
mergesort(arr, beg, mid)
mergesort(arr, mid+1, end)
merge(arr, beg, mid, mid+1, end)

Time & Space Complexity

Case Time Complexity Space Complexity Notes

Best Case O(n log n) O(n) Always divides equally

Average Case O(n log n) O(n) Consistent performance

Worst Case O(n log n) O(n) Always O(n log n) — no bad case
Merge Sort is stable and guarantees O(n log n). Extra O(n) space needed for merging.

Q1. What strategy does Merge Sort use?

■ Divide and Conquer — split the problem into smaller sub-problems, solve recursively, then combine.
Q2. Why is Merge Sort preferred over Quick Sort in some cases?
■ Merge Sort guarantees O(n log n) in all cases; Quick Sort degrades to O(n²) in worst case.
Q3. Is Merge Sort stable?
■ Yes. Equal elements are merged in their original order.
Q4. What is the space complexity of Merge Sort?
■ O(n) extra space is needed for the temporary arrays during the merge step.
Q5. Where is Merge Sort used in practice?
■ External sorting (sorting data on disk), sorting linked lists, and where stability is required.

Dr. Sheenam | Academic Session 2025-26 Page 7

Basic Data Structures – Complete Study Guide UIE | 25CSH-103

1.5 Quick Sort

Quick Sort is a highly efficient Divide and Conquer algorithm. It picks a pivot element and partitions the array so all
elements smaller than the pivot go to its left and all larger go to its right. This process recurses on each partition.
Also called Partition Exchange Sort.

How It Works – Step by Step

Array: [40, 20, 10, 80, 60, 50, 7, 30, 100] — Pivot = 40 (first element)

Partition: Elements < 40: [20,10,7,30] | Pivot: 40 | Elements > 40: [80,60,50,100]

Result after partition: [20,10,7,30, 40, 80,60,50,100]

Recurse on left sub-array [20,10,7,30] and right sub-array [80,60,50,100].

Final sorted: [7,10,20,30,40,50,60,80,100]

Algorithm
quicksort(arr, low, high):
IF low < high:
pivot_index = partition(arr, low, high)
quicksort(arr, low, pivot_index - 1)
quicksort(arr, pivot_index + 1, high)

Time & Space Complexity

Case Time Complexity Space Complexity Notes

Best Case O(n log n) O(log n) Pivot always divides evenly

Average Case O(n log n) O(log n) Random pivot selection

Worst Case O(n2) O(n) Sorted array with first-element pivot

Quick Sort is NOT stable. In-place (no extra array). Fastest in practice for most real data.

Q1. What is a pivot in Quick Sort?

■ A pivot is an element selected to partition the array. Elements smaller go left, larger go right.
Q2. What is the worst case for Quick Sort and how to avoid it?
■ Worst case O(n²) occurs when the pivot is always smallest/largest (e.g., sorted array). Use random pivot or
median-of-three.
Q3. Is Quick Sort stable?
■ No. Swaps in partitioning can change the relative order of equal elements.
Q4. Quick Sort vs Merge Sort — which is faster?
■ Quick Sort is usually faster in practice due to better cache performance, despite same O(n log n) average.
Q5. What does 'partition exchange sort' mean?
■ Partition means splitting around the pivot; exchange means swapping elements to place them on the
correct side.

Dr. Sheenam | Academic Session 2025-26 Page 8

Basic Data Structures – Complete Study Guide UIE | 25CSH-103

1.6 Sorting Algorithms – Complexity Comparison

Algorithm Best Average Worst Space Stable Method

Bubble Sort O(n) O(n²) O(n²) O(1) Yes Exchange

Insertion Sort O(n) O(n²) O(n²) O(1) Yes Insertion

Selection Sort O(n²) O(n²) O(n²) O(1) No Selection

Merge Sort O(n log n) O(n log n) O(n log n) O(n) Yes Divide & Conquer

O(log
Quick Sort O(n log n) O(n log n) O(n²) No Divide & Conquer
n)

Key Takeaway: For small datasets, use Insertion/Bubble. For large datasets needing guaranteed performance, use
Merge Sort. For practical speed on general data, Quick Sort with randomized pivot is best.

Dr. Sheenam | Academic Session 2025-26 Page 9

Basic Data Structures – Complete Study Guide UIE | 25CSH-103

UNIT 2: LINKED LISTS

Singly • Doubly • Circular Linked Lists

A Linked List is a linear data structure where each element (called a node) stores data and a pointer to the next
node. Unlike arrays, linked lists do not occupy contiguous memory and can grow dynamically. They are the
foundation of stacks, queues, trees, and graphs.

Arrays vs Linked Lists

Paragraph(
'caseSensitive': 1
'encoding': 'utf8' 'text':
'Feature' 'frags': [Par Paragraph( 'caseSensitive': 1 Paragraph( 'caseSensitive': 1
aFrag(__tag__='b', 'encoding': 'utf8' 'text': 'Arrays' 'encoding': 'utf8' 'text': 'Linked
bold=1, fontName='H 'frags': [ParaFrag(__tag__='b', Lists' 'frags':
elvetica-Bold', bold=1, [ParaFrag(__tag__='b', bold=1,
fontSize=10, fontName='Helvetica-Bold', fontName='Helvetica-Bold',
greek=0, italic=0, fontSize=10, greek=0, italic=0, fontSize=10, greek=0, italic=0,
link=[], rise=0, link=[], rise=0, text='Arrays', textC link=[], rise=0, text='Linked Lists', t
text='Feature', textCo olor=Color(.129412,.129412,.1294 extColor=Color(.129412,.129412,.
lor=Color(.129412,.1 12,1), us_lines=[])] 'style': 129412,1), us_lines=[])] 'style':
29412,.129412,1), 'bulletText': None 'debug': 0 ) 'bulletText': None 'debug': 0 )
us_lines=[])] 'style': #Paragraph #Paragraph
'bulletText': None
'debug': 0 )
#Paragraph

Memory Contiguous, fixed size Non-contiguous, dynamic

Access O(1) random access O(n) sequential access

Insertion O(n) – shifting needed O(1) – if position known

Deletion O(n) – shifting needed O(1) – if pointer known

Space No pointer overhead Extra pointer per node

2.1 Singly Linked List

In a Singly Linked List, each node has two parts: DATA (the value) and LINK (pointer to the next node). The last
node's LINK is NULL. Traversal is only possible in one direction (forward).
Structure: [DATA | LINK] → [DATA | LINK] → [DATA | NULL]

Operations
• Traversal: Start at HEAD, visit each node until LINK = NULL. Time: O(n)
• Search (Unsorted): Scan each node; return LOC if found, NULL otherwise. Time: O(n)
• Insertion at Beginning: New node's LINK = Start; Start = New. Time: O(1)
• Insertion After Node LOC: New node's LINK = LOC's LINK; LOC's LINK = New. Time: O(1)
• Insertion in Sorted List: Traverse to find correct position, then insert. Time: O(n)
• Deletion: Find predecessor of node to delete; update predecessor's LINK. Time: O(n)

Dr. Sheenam | Academic Session 2025-26 Page 10

Basic Data Structures – Complete Study Guide UIE | 25CSH-103

Time & Space Complexity

Case Time Complexity Space Complexity Notes

Traversal O(n) O(1) Visit all n nodes

Search O(n) O(1) Linear scan

Insert (head) O(1) O(1) Direct pointer update

Insert (tail) O(n) O(1) Must traverse to end

Delete O(n) O(1) Must find predecessor

Singly Linked List — forward traversal only.

Q1. What is a singly linked list?

■ A linear data structure where each node has a data field and a pointer to the next node; the last node points
to NULL.
Q2. What is the advantage of a linked list over an array?
■ Dynamic size — no need to declare size in advance; efficient insertion/deletion without shifting elements.
Q3. How is insertion done at the beginning?
■ Create new node, set its LINK = current START, then update START = new node. O(1) time.
Q4. Why is random access O(n) in a linked list?
■ There are no indices; you must traverse from the HEAD node one by one to reach any position.
Q5. What are applications of linked lists?
■ Implementing stacks, queues, graphs (adjacency list), hash tables, and polynomial arithmetic.

Dr. Sheenam | Academic Session 2025-26 Page 11

Basic Data Structures – Complete Study Guide UIE | 25CSH-103

2.2 Doubly Linked List (DLL)

A Doubly Linked List has three parts per node: BACK (pointer to previous node), DATA, and FORW (pointer to
next node). This allows bidirectional traversal — both forward and backward.
Structure: NULL ← [BACK|DATA|FORW] ↔ [BACK|DATA|FORW] ↔ [BACK|DATA|NULL]

Advantages over Singly Linked List

• Bidirectional traversal — can go both forward and backward
• Deletion is O(1) if the node pointer is given (no need to find predecessor separately)
• Can be used to implement both stacks and deques efficiently

Disadvantages
• Extra memory per node for the BACK pointer
• All operations must update both BACK and FORW pointers — more complex code

Insertion Algorithm (between LOCA and LOCB)

1. Check AVAIL; if NULL → Overflow.
2. NEW = AVAIL; set INFO[NEW] = ITEM
3. FORW[LOCA] = NEW; FORW[NEW] = LOCB
4. BACK[LOCB] = NEW; BACK[NEW] = LOCA

Deletion Algorithm (delete node at LOC)

1. FORW[BACK[LOC]] = FORW[LOC]
2. BACK[FORW[LOC]] = BACK[LOC]
3. Return LOC to AVAIL list

Time & Space Complexity

Case Time Complexity Space Complexity Notes

Traversal O(n) O(1) Both directions

Insert (given) O(1) O(1) Two pointer updates

Delete (given) O(1) O(1) Direct BACK access

Search O(n) O(1) Must scan nodes

DLL requires O(1) more space per node for the BACK pointer.

Real-World Applications
• Browser back/forward navigation
• Undo/Redo in text editors and IDEs
• Music/video player (previous/next track)
• LRU Cache implementation
• Deck of cards in games

Q1. How many pointers does each DLL node have?

■ Two — BACK (previous node) and FORW (next node), plus the DATA field.
Q2. Why is deletion easier in DLL than SLL?
■ In DLL, each node directly stores the address of its predecessor via the BACK pointer, so no traversal is
needed.
Q3. What is the extra memory cost of DLL?

Dr. Sheenam | Academic Session 2025-26 Page 12

Basic Data Structures – Complete Study Guide UIE | 25CSH-103

■ One extra pointer per node — so total space = n × (sizeof(data) + 2 × sizeof(pointer)).

Q4. Name two real-world applications of DLL.
■ Browser history (back/forward) and Undo/Redo functionality in editors.
Q5. Can a DLL be traversed from the last node to the first?
■ Yes — start from the last node and follow BACK pointers until reaching NULL.

Dr. Sheenam | Academic Session 2025-26 Page 13

Basic Data Structures – Complete Study Guide UIE | 25CSH-103

2.3 Circular Linked List

In a Circular Linked List, the last node's LINK does not point to NULL — instead it points back to the first node,
forming a circle. There is no natural start or end, and traversal can continue indefinitely.
Structure: [DATA|LINK] → [DATA|LINK] → [DATA|LINK] → (back to first)

Advantages
• Any node can be a starting point — useful for round-robin scheduling
• Traversal of the whole list from any node is possible
• No need for a NULL check at the end — check if we've returned to start

Real-World Applications
• CPU round-robin scheduling (OS gives each process a time slice in circular order)
• Multiplayer games — turns go to each player in a circular manner
• Media playlists on repeat mode
• Traffic signal control systems

Complexity
Case Time Complexity Space Complexity Notes

Traversal O(n) O(1) Stop when back at start

O(1) at front, O(n) at specific

Insertion O(1)/O(n) O(1)
position

Deletion O(n) O(1) Must find predecessor

Circular Linked List — no NULL termination; use start node as sentinel.

Q1. What distinguishes a circular linked list from a singly linked list?
■ The last node points back to the first node instead of NULL, forming a closed loop.
Q2. How do you detect when traversal is complete in a circular linked list?
■ Check if the current node's LINK equals the starting node (HEAD).
Q3. Give one OS application of circular linked list.
■ Round-robin CPU scheduling — each process gets a time slice and control passes to the next in a circle.
Q4. Can a doubly linked list also be circular?
■ Yes — a Circular Doubly Linked List has FORW of last node pointing to first, and BACK of first pointing to
last.

Dr. Sheenam | Academic Session 2025-26 Page 14

Basic Data Structures – Complete Study Guide UIE | 25CSH-103

UNIT 3: STACKS

Introduction • Operations • Applications

A Stack is a linear data structure that follows the LIFO (Last In, First Out) principle. Operations happen at only one
end, called the TOP. Think of a stack of plates — you can only add or remove the top plate.

3.1 Introduction to Stack

LIFO: The element inserted last is the first one to be removed.

TOP pointer: Always points to the most recently inserted element.

Overflow: Pushing onto a full stack (TOP = MAX-1).

Underflow: Popping from an empty stack (TOP = NULL or 0).

Basic Operations
Operation Description Time Complexity

push(x) Insert element x at TOP O(1)

pop() Remove and return TOP element O(1)

peek() Return TOP element without removing it O(1)

isFull() Check if stack is full O(1)

isEmpty() Check if stack is empty O(1)

Representations
• Array Representation: Simple; TOP tracks the index. Limitation: fixed maximum size (MAX).
• Linked List Representation: Dynamic size; each push creates a new node at front; pop removes front node.

Q1. What is a stack? What principle does it follow?

■ A stack is a linear LIFO (Last In, First Out) data structure where all insertions and deletions happen at the
TOP.
Q2. What is stack overflow and underflow?
■ Overflow: pushing onto a full stack. Underflow: popping from an empty stack.
Q3. What will be on TOP after: push(8), push(3), pop(), push(2), push(5)?
■ Stack: [8, 2, 5]. TOP = 5 (3 was popped, then 2 and 5 pushed).
Q4. Compare array and linked list implementation of stack.
■ Array: simple, fixed size, O(1) ops. Linked list: dynamic size, O(1) ops, but extra pointer memory.
Q5. What is the advantage of linked list implementation of stack?
■ No overflow due to fixed size — the stack grows dynamically as long as memory is available.

Dr. Sheenam | Academic Session 2025-26 Page 15

Basic Data Structures – Complete Study Guide UIE | 25CSH-103

3.2 Stack Operations – PUSH & POP

PUSH Algorithm (Array)

1. IF TOP = MAX: print 'Overflow' and Exit
2. TOP = TOP + 1
3. Stack[TOP] = Item
4. Exit

POP Algorithm (Array)

1. IF TOP = 0: print 'Underflow' and Exit
2. Item = Stack[TOP]
3. TOP = TOP - 1
4. Return Item; Exit

Example Trace
push(1) → Stack: [1] | TOP=1

push(2) → Stack: [1,2] | TOP=2

push(3) → Stack: [1,2,3] | TOP=3

push(4) → Stack: [1,2,3,4] | TOP=4

pop() → removes 4 → Stack: [1,2,3] | TOP=3

pop() → removes 3 → Stack: [1,2] | TOP=2

Output printed: 2 1

Q1. Write the push algorithm for array implementation.

■ Check if TOP=MAX (overflow). If not, increment TOP and store item at Stack[TOP].
Q2. What is the time complexity of push and pop?
■ Both are O(1) — constant time, regardless of stack size.
Q3. What is the role of the TOP variable?
■ TOP always points to the index of the most recently inserted element. It acts as a cursor for the stack.
Q4. What happens if we pop from a stack with only one element?
■ The element is returned and TOP is decremented to 0 (or -1), making the stack empty.

Dr. Sheenam | Academic Session 2025-26 Page 16

Basic Data Structures – Complete Study Guide UIE | 25CSH-103

3.3 Applications of Stack

• Reversing a list — push all elements then pop in reverse order

• Parentheses checker — verify balanced brackets in expressions
• Expression conversion — Infix to Postfix / Prefix
• Expression evaluation — Postfix/Prefix evaluation
• Recursion — each function call is stored as a stack frame
• Tower of Hanoi — recursive solution uses call stack
• Undo/Redo in applications
• Browser back navigation

Notation Types
Paragraph(
'caseSensitive': 1
Paragraph( 'caseSensitive':
'encoding': 'utf8' 'text':
1 'encoding': 'utf8' 'text':
'Notation' 'frags': [Par Paragraph( 'caseSensitive': 1
'Form' 'frags':
aFrag(__tag__='para' 'encoding': 'utf8' 'text': 'Example
[ParaFrag(__tag__='para',
, bold=1, fontName=' (a+b)*c' 'frags':
bold=1,
Helvetica-Bold', [ParaFrag(__tag__='para', bold=1,
fontName='Helvetica-Bold',
fontSize=10, fontName='Helvetica-Bold',
fontSize=10, greek=0,
greek=0, italic=0, fontSize=10, greek=0, italic=0, link=[],
italic=0, link=[], rise=0,
link=[], rise=0, rise=0, text='Example (a+b)*c',
text='Form',
text='Notation', textC textColor=Color(1,1,1,1), us_lines=[])]
textColor=Color(1,1,1,1),
olor=Color(1,1,1,1), 'style': 'bulletText': None 'debug': 0 )
us_lines=[])] 'style':
us_lines=[])] 'style': #Paragraph
'bulletText': None 'debug':
'bulletText': None
0 ) #Paragraph
'debug': 0 )
#Paragraph

Infix Op between operands (a+b)*c

Prefix Op before operands *+abc

Postfix Op after operands ab+c*

Operator Precedence (for Infix→Postfix Conversion)

Highest: ^ (Exponentiation) — Right Associative

Second: * / (Multiplication, Division) — Left Associative

Lowest: + – (Addition, Subtraction) — Left Associative

Q1. What is Infix, Prefix, and Postfix notation?

■ Infix: operator between operands (a+b). Prefix: operator before (+ ab). Postfix: operator after (ab +).
Q2. Why do computers prefer postfix over infix?
■ Postfix has no parentheses or precedence rules — it can be evaluated left-to-right using a stack, efficiently.
Q3. How does a stack help in parenthesis checking?
■ Push '(' onto stack; when ')' is seen, pop and check for match. If stack is empty at end and matched, it's
valid.
Q4. Convert (A + B) * C to Postfix.
■ AB+C* — push operands, handle operators by precedence using stack.

Dr. Sheenam | Academic Session 2025-26 Page 17

Basic Data Structures – Complete Study Guide UIE | 25CSH-103

Q5. What is the role of the stack in recursion?

■ Each recursive call's local variables and return address are stored as a 'stack frame' in the call stack.

Dr. Sheenam | Academic Session 2025-26 Page 18

Basic Data Structures – Complete Study Guide UIE | 25CSH-103

UNIT 4: QUEUES

Linear Queue • Operations • Circular Queue • Deque

A Queue is a linear data structure that follows the FIFO (First In, First Out) principle. Insertions happen at the
REAR end and deletions happen at the FRONT end. Think of a line of people at a ticket counter — the first person
to join is the first to be served.

4.1 Introduction to Queue

FRONT: Points to the first element (deletion end).

REAR: Points to the last element (insertion end).

FIFO: First element inserted is the first element removed.

Types of Queues
• Linear Queue — basic FIFO structure with FRONT and REAR pointers
• Circular Queue — rear wraps around to the beginning when end is reached
• Deque (Double-Ended Queue) — insertion and deletion at both ends
• Priority Queue — element with highest priority is dequeued first

Array Representation
FRONT = 0, REAR = -1 initially (empty queue).
Enqueue: REAR++ then Queue[REAR] = Item.
Dequeue: Item = Queue[FRONT] then FRONT++.
Problem: Even if slots are free before FRONT, they can't be reused — solved by Circular Queue.

Linked Representation
Each node has DATA and NEXT pointer. FRONT = first node, REAR = last node. Insert at REAR ([Link] =
new node; REAR = new node). Delete at FRONT (FRONT = [Link]). Space complexity O(n), time O(1).

Q1. What is a queue and what principle does it follow?

■ A queue is a linear FIFO (First In, First Out) structure; the first element inserted is the first to be removed.
Q2. What are FRONT and REAR in a queue?
■ FRONT is the pointer to the deletion end; REAR is the pointer to the insertion end.
Q3. What is the difference between a stack and a queue?
■ Stack is LIFO (top only); Queue is FIFO (insert at rear, delete from front).
Q4. What is the problem with simple array-based queues?
■ Memory wastage — once elements are dequeued, those slots cannot be reused, leading to false overflow.
Q5. Where is queue used in operating systems?
■ CPU scheduling (ready queue), printer spooler, disk scheduling, and network packet buffering.

Dr. Sheenam | Academic Session 2025-26 Page 19

Basic Data Structures – Complete Study Guide UIE | 25CSH-103

4.2 Operations on Queue

Enqueue (Insert at REAR)

1. Check if queue is full (REAR = N): print 'Overflow'
2. REAR = REAR + 1
3. Queue[REAR] = Item
4. Return success

Dequeue (Delete from FRONT)

1. Check if queue is empty (FRONT = NULL): print 'Underflow'
2. Item = Queue[FRONT]
3. FRONT = FRONT + 1
4. Return Item

Other Operations
peek(): return Queue[FRONT] without modifying FRONT.
isFull(): return (REAR == MAXSIZE - 1)
isEmpty(): return (FRONT < 0 || FRONT > REAR)

Time & Space Complexity of Queue Operations

Case Time Complexity Space Complexity Notes

Enqueue O(1) O(1) Direct REAR pointer update

Dequeue O(1) O(1) Direct FRONT pointer update

peek() O(1) O(1) Read Queue[FRONT]

isEmpty() O(1) O(1) Single comparison

isFull() O(1) O(1) Single comparison

All queue operations run in O(1) time — constant regardless of queue size.

Q1. What are the basic operations of a queue?

■ Enqueue (insert at rear), Dequeue (remove from front), peek (view front), isFull, isEmpty.
Q2. What is queue overflow?
■ Attempting to enqueue when the queue is full (REAR = MAX - 1).
Q3. What is queue underflow?
■ Attempting to dequeue when the queue is empty (FRONT = NULL or FRONT > REAR).
Q4. Which data structure is used for BFS graph traversal?
■ Queue — BFS processes nodes level by level using the FIFO property of a queue.
Q5. What is the time complexity of enqueue and dequeue?
■ O(1) — both operations involve only pointer arithmetic, no traversal.

Dr. Sheenam | Academic Session 2025-26 Page 20

Basic Data Structures – Complete Study Guide UIE | 25CSH-103

4.3 Circular Queue & Deque

A Circular Queue solves the memory wastage problem of linear queues. When REAR reaches the end (MAX-1), it
wraps around to index 0 if there is free space at the beginning. The queue is treated as a circular buffer.

Key Conditions
• Empty: FRONT = -1 (initially) or after last element dequeued
• Full: (REAR + 1) % MAX == FRONT
• Enqueue: REAR = (REAR + 1) % MAX; Queue[REAR] = Item
• Dequeue: Item = Queue[FRONT]; FRONT = (FRONT + 1) % MAX

Circular Queue vs Linear Queue

Paragraph(
'caseSensitive': 1
Paragraph( 'caseSensitive': 1 Paragraph( 'caseSensitive': 1
'encoding': 'utf8' 'text':
'encoding': 'utf8' 'text': 'Linear 'encoding': 'utf8' 'text': 'Circular
'Feature' 'frags':
Queue' 'frags': Queue' 'frags':
[ParaFrag(__tag__='para',
[ParaFrag(__tag__='para', bold=1, [ParaFrag(__tag__='para', bold=1,
bold=1, fontName='Helveti
fontName='Helvetica-Bold', fontName='Helvetica-Bold',
ca-Bold', fontSize=10,
fontSize=10, greek=0, italic=0, fontSize=10, greek=0, italic=0,
greek=0, italic=0, link=[],
link=[], rise=0, text='Linear Queue', link=[], rise=0, text='Circular Queue',
rise=0, text='Feature',
textColor=Color(1,1,1,1), textColor=Color(1,1,1,1),
textColor=Color(1,1,1,1),
us_lines=[])] 'style': 'bulletText': us_lines=[])] 'style': 'bulletText':
us_lines=[])] 'style':
None 'debug': 0 ) #Paragraph None 'debug': 0 ) #Paragraph
'bulletText': None 'debug':
0 ) #Paragraph

Memory Use Wastes dequeued slots Reuses all slots

Overflow False overflow possible True overflow only when actually full

REAR update REAR++ REAR = (REAR+1) % MAX

Use case Simple scenarios CPU scheduling, traffic systems

Deque (Double-Ended Queue)

A Deque (pronounced 'deck') allows insertion and deletion at both FRONT and REAR ends. Two pointers (LEFT
and RIGHT) track both ends. It is implemented using a circular array or circular doubly linked list. No insertions or
deletions are allowed in the middle.

Real-World Applications
• Circular Queue: CPU scheduling, traffic signal control systems, memory management
• Deque: Undo operations in editors (both push to front and back), sliding window problems, palindrome checking
• Priority Queue: Hospital emergency systems, Dijkstra's shortest path algorithm, Huffman coding

Q1. What is a circular queue and why is it used?

■ A circular queue treats the array as a ring — REAR wraps to 0 when it reaches MAX-1. This eliminates
false overflow and reuses all memory.
Q2. How do you check if a circular queue is full?
■ Condition: (REAR + 1) % MAX == FRONT. If true, the queue is full.
Q3. What is a Deque?
■ Double-Ended Queue — allows enqueue and dequeue at both front and rear ends.

Dr. Sheenam | Academic Session 2025-26 Page 21

Basic Data Structures – Complete Study Guide UIE | 25CSH-103

Q4. Difference between Deque and regular Queue.

■ Queue: insert at rear, delete at front only. Deque: insert/delete at both ends.
Q5. What is a Priority Queue?
■ A queue where each element has a priority; the element with the highest priority is dequeued first,
regardless of insertion order.
Q6. Give a real-world example of a circular queue.
■ CPU round-robin scheduling — each process gets equal time in a circular manner.

Dr. Sheenam | Academic Session 2025-26 Page 22

Basic Data Structures – Complete Study Guide UIE | 25CSH-103

UNIT 5: COMPREHENSIVE VIVA QUESTIONS

All Topics – Exam Preparation

Sorting Algorithms – Mixed Viva

Q1. What is stable sorting? Give an example of a stable sort.

■ A sort is stable if equal elements maintain their original relative order. Bubble Sort, Insertion Sort, and
Merge Sort are stable.
Q2. Which sorting algorithm has the best worst-case time complexity?
■ Merge Sort — it guarantees O(n log n) in all cases (best, average, worst).
Q3. Compare Merge Sort and Quick Sort.
■ Both are O(n log n) average. Merge Sort is stable with O(n) space; Quick Sort is faster in practice, in-place,
but O(n²) worst case.
Q4. Why is Quick Sort generally faster than Merge Sort despite the same O(n log n)?
■ Quick Sort has better cache locality (works on contiguous subarrays) and smaller constant factors.
Q5. Which sort would you use for a nearly-sorted array of 100 elements?
■ Insertion Sort — it runs in O(n) for nearly sorted data and has very small overhead.
Q6. What is the space complexity of Quick Sort?
■ O(log n) average (recursive call stack), O(n) worst case (skewed partitions).
Q7. What is divide and conquer? Which sorting algorithms use it?
■ Splitting a problem into smaller sub-problems, solving each, then combining. Merge Sort and Quick Sort
use this strategy.
Q8. Is Selection Sort adaptive?
■ No — it always performs O(n²) comparisons regardless of input order.

Linked Lists – Mixed Viva

Q1. What is the difference between a singly and doubly linked list?
■ SLL has one LINK per node (forward only). DLL has BACK and FORW pointers (bidirectional traversal).
Q2. How would you reverse a singly linked list?
■ Traverse the list; for each node, set its LINK to the previous node. Maintain prev, curr, next pointers. O(n)
time.
Q3. How do you detect a loop (cycle) in a linked list?
■ Floyd's cycle detection — two pointers (slow moves by 1, fast by 2). If they meet, there is a cycle.
Q4. What is the time complexity of searching in a sorted linked list?
■ O(n) — unlike sorted arrays, linked lists don't support binary search due to no random access.
Q5. Can you implement a stack using a linked list? How?
■ Yes — push = insert at front, pop = delete from front. Both O(1). No overflow as long as memory is
available.
Q6. What is the memory overhead of a doubly linked list?
■ Two pointers per node (BACK + FORW) instead of one, so extra n × sizeof(pointer) bytes.

Dr. Sheenam | Academic Session 2025-26 Page 23

Basic Data Structures – Complete Study Guide UIE | 25CSH-103

Stacks – Mixed Viva

Q1. Trace: push(5), push(10), push(15), pop(), pop(), push(20). What is TOP?
■ After operations: stack = [5, 20]. TOP = 20. (15 and 10 were popped, then 20 pushed.)
Q2. What is Polish Notation?
■ Another name for Prefix notation, where the operator precedes its operands. e.g., +ab instead of a+b.
Q3. Evaluate the postfix expression: 2 3 + 4 * using a stack.
■ Push 2, push 3. See +: pop 2,3 → push 5. Push 4. See *: pop 5,4 → push 20. Result = 20.
Q4. Why is postfix expression evaluation simpler than infix?
■ No parentheses or precedence rules needed — operands are pushed, operators pop and process
immediately.
Q5. What data structure does a compiler use for function calls?
■ A call stack — each function call pushes a stack frame; return pops it, restoring the previous context.
Q6. What is the Tower of Hanoi? How is a stack involved?
■ A puzzle of moving n disks from source to destination using an auxiliary peg. Solved recursively; each
recursive call uses the call stack.

Queues – Mixed Viva

Q1. What is the difference between LIFO and FIFO?

■ LIFO (Last In First Out) = Stack — last inserted is first removed. FIFO (First In First Out) = Queue — first
inserted is first removed.
Q2. Why is a circular queue better than a linear queue?
■ Circular queue reuses freed slots by wrapping REAR around to index 0, preventing false overflow.
Q3. What are the four types of queues?
■ Linear Queue, Circular Queue, Deque (Double-Ended Queue), and Priority Queue.
Q4. How is BFS (Breadth First Search) implemented?
■ Using a queue — enqueue the starting node, then repeatedly dequeue and enqueue its unvisited
neighbours.
Q5. What is the formula for enqueue in a circular queue?
■ REAR = (REAR + 1) % MAX; Queue[REAR] = Item. The modulo operator enables circular wrap-around.
Q6. Give two real-world examples of queues.
■ 1) Printer spooler — print jobs processed in order. 2) Customer service line — first customer served first.

Dr. Sheenam | Academic Session 2025-26 Page 24

Basic Data Structures – Complete Study Guide UIE | 25CSH-103

MASTER COMPLEXITY REFERENCE TABLE

Data Structure /
Operation Best Average Worst Space
Algorithm

Bubble Sort Sort O(n) O(n²) O(n²) O(1)

Insertion Sort Sort O(n) O(n²) O(n²) O(1)

Selection Sort Sort O(n²) O(n²) O(n²) O(1)

O(n log O(n log

Merge Sort Sort O(n log n) O(n)
n) n)

O(n log O(log

Quick Sort Sort O(n log n) O(n²)
n) n)

Singly Linked List Search O(1) O(n) O(n) O(n)

Singly Linked List Insert (head) O(1) O(1) O(1) —

Doubly Linked List Insert/Delete O(1) O(1) O(1) O(n)

Stack Push / Pop / Peek O(1) O(1) O(1) O(n)

Queue Enqueue / Dequeue O(1) O(1) O(1) O(n)

Circular Queue Enqueue / Dequeue O(1) O(1) O(1) O(n)

Key Symbols: n = number of elements | log n = base-2 logarithm | O(1) = constant time

Remember: O(1) < O(log n) < O(n) < O(n log n) < O(n²) — smaller is faster!

All the best for your examinations!

Study smart, understand concepts, practise tracing algorithms on paper.

Dr. Sheenam | Academic Session 2025-26 Page 25