DSA QB Solution
4th Module (2 Marks Questions)
64. Define a stack. What is its primary purpose as an Abstract Data Type (ADT)?
1. A stack is a linear data structure that follows LIFO (Last In, First Out) principle.
2. The element inserted last is removed first.
3. It allows operations only at one end called the top.
4. Its primary purpose is to manage function calls, expression evaluation, and backtracking.
65. List the basic operations that can be performed on a stack.
1. Push: Insert an element into the stack.
2. Pop: Remove the top element from the stack.
3. Peek/Top: Retrieve the top element without removing it.
4. isEmpty/isFull: Check if the stack is empty or full.
66. What is the primary difference between a linear queue and a circular queue?
1. In a linear queue, space is not reused after deletions.
2. In a circular queue, the last position connects to the first, reusing memory.
3. Linear queue can cause “queue overflow” even when space is available.
4. Circular queue eliminates this problem by wrapping around.
67. Explain the difference between infix and postfix expressions with an example for each.
1. Infix: Operator is between operands → e.g., A + B.
2. Postfix: Operator comes after operands → e.g., A B +.
3. Infix needs parentheses to define precedence.
4. Postfix doesn’t need parentheses; evaluation uses stack easily.
68. What are the basic operations that can be performed on a queue?
1. Enqueue: Insert an element at the rear.
2. Dequeue: Remove an element from the front.
3. Front/Peek: Retrieve the front element without removing it.
4. isEmpty/isFull: Check queue status (empty/full).
69. Enlist the operations on stack data structures and state the time complexity for each
operation.
1. Push → O(1)
2. Pop → O(1)
3. Peek/Top → O(1)
4. isEmpty/isFull → O(1)
70. State the time complexity for all the operations in the queue data structure.
1. Enqueue → O(1)
2. Dequeue → O(1)
3. Front/Peek → O(1)
4. isEmpty/isFull → O(1)
4th Module (5 Marks Questions)
71. What is Queue? Write a program to implement Linear queue operations.
Definition:
1. A queue is a linear data structure that follows the FIFO (First In, First Out) principle.
2. The element inserted first is deleted first.
3. It has two ends — front (for deletion) and rear (for insertion).
4. Used in scheduling, buffering, and resource management.
Basic Operations:
• Enqueue: Add element at rear.
• Dequeue: Remove element from front.
• Display: Show all elements.
• isFull/isEmpty: Check queue status.
72. Write a program to implement Circular queue operations.
Concept:
1. A Circular Queue links the last position back to the first using modulo (%) arithmetic.
2. It prevents wastage of space found in a linear queue.
3. It follows FIFO (First In, First Out) order.
4. Operations are enqueue, dequeue, display, isFull, isEmpty.
C Program:
73. Convert the following infix expression to postfix using stack:
Expression: A × ( B + C ) / D – E
Step-by-Step Conversion:
Step Symbol Stack Output
1 A A
2 × × A
3 ( ×( A
4 B ×( AB
5 + ×(+ AB
6 C ×(+ ABC
7 ) × ABC+
8 / / ABC+×
9 D / ABC+×D
10 − − ABC+×D/
11 E − ABC+×D/E
Final Postfix Expression:
👉ABC+×D/E–
74. Write an Algorithm to evaluate Prefix Expression.
Concept:
1. A Prefix Expression (also called Polish Notation) is written with operators before
operands.
Example: + 5 * 6 2 means 5 + (6 * 2).
2. Evaluation starts from right to left using a stack.
3. When an operand is found, it’s pushed into the stack.
4. When an operator is found, two operands are popped, operation is performed, and result
is pushed back.
Algorithm: EvaluatePrefix(exp)
1. Start
2. Initialize an empty stack.
3. Scan the prefix expression from right to left.
4. If symbol is operand: → Push it into the stack.
5. If symbol is operator:
→ Pop top two operands from the stack.
→ Apply the operator on them → result = op1 operator op2.
→ Push the result back into the stack.
6. Continue until the full expression is scanned.
7. Result will be at the top of the stack.
8. End
Example:
Expression: + * 2 3 4
Equivalent Infix: (2 * 3) + 4
Step-by-Step Evaluation:
Step Symbol Action Stack (Top → Bottom)
1 4 Operand → Push 4
2 3 Operand → Push 3, 4
3 2 Operand → Push 2, 3, 4
4 * Operator → 2 * 3 = 6 → Push 6, 4
5 + Operator → 6 + 4 = 10 → Push 10
✅ Final Result: 10
• Time Complexity: O(n) — each symbol processed once.
• Space Complexity: O(n) — for the stack storage.
75. Evaluate the following prefix expression:
Expression: + - + * 8 2 * - 7 1 / 9 3 6 3
Step-by-Step Evaluation (Prefix → Right to Left)
Step Symbol Action Stack (Top → Bottom)
1 3 Operand → Push 3
Step Symbol Action Stack (Top → Bottom)
2 6 Operand → Push 6, 3
3 / Operator → (9 / 3) = 3 3
4 9 Operand → Push 9, 3
5 / 9 / 3 = 3 → Push 3
6 1 Operand → Push 1, 3
7 7 Operand → Push 7, 1, 3
8 - 7 - 1 = 6 → Push 6, 3
9 * 6 * 3 = 18 → Push 18
10 2 Operand → Push 2, 18
11 8 Operand → Push 8, 2, 18
12 * 8 * 2 = 16 → Push 16, 18
13 + 16 + 18 = 34 → Push 34
14 - 34 - 3 = 31 → Push 31
15 + 31 + 6 = 37 37
Final Answer: ✅ 37
76. Evaluate the following postfix expression:
Expression: 6 2 3 + - 3 8 2 / + * 2 ^ 3 +
Step-by-Step Evaluation (Postfix → Left to Right)
Step Symbol Action Stack (Top → Bottom)
1 6 Operand → Push 6
2 2 Operand → Push 2, 6
3 3 Operand → Push 3, 2, 6
4 + 2 + 3 = 5 → Push 5, 6
5 - 6 - 5 = 1 → Push 1
6 3 Operand → Push 3, 1
7 8 Operand → Push 8, 3, 1
8 2 Operand → Push 2, 8, 3, 1
Step Symbol Action Stack (Top → Bottom)
9 / 8 / 2 = 4 → Push 4, 3, 1
10 + 3 + 4 = 7 → Push 7, 1
11 * 1 * 7 = 7 → Push 7
12 2 Operand → Push 2, 7
13 ^ 7 ^ 2 = 49 → Push 49
14 3 Operand → Push 3, 49
15 + 49 + 3 = 52 52
Final Answer: ✅ 52
77. State the applications of stacks and queue data structures. Write time
complexity for PUSH, POP, ENQUEUE, DEQUEUE.
Applications of Stack:
1. Expression evaluation and conversion (infix ↔ postfix/prefix).
2. Function call management (recursion).
3. Undo/Redo operations.
4. Backtracking (like in maze or DFS).
Applications of Queue:
1. CPU scheduling and resource sharing.
2. Printer spooling and job management.
3. Data buffering (I/O systems).
4. Level-order traversal in trees.
Time Complexity:
Operation Time Complexity
PUSH O(1)
POP O(1)
ENQUEUE O(1)
DEQUEUE O(1)