Stack Questions

1. Define a stack and explain its main operations with examples, and its application.

Definition: A stack is a linear data structure that follows the LIFO (Last In, First Out)
principle.

Main Operations:

Push → Insert element at top.

Pop → Remove element from top.

Peek → View top element without removing.

IsEmpty/IsFull → Check stack status.

Example: If we push 10, 20, 30, then stack = [10, 20, 30]. Popping removes 30 first.

Applications:

Undo/Redo feature in text editors.

Function call management in recursion.

Expression evaluation (Postfix/Prefix).

2. What is stack overflow and underflow? Provide scenarios.

Stack Overflow → Occurs when we try to push into a full stack. Example: Fixed-size stack of
size 3 → push(10), push(20), push(30), push(40) → Overflow.

Stack Underflow → Occurs when we try to pop from an empty stack. Example: Pop from an
empty stack.

3. Describe the LIFO principle with a real-world analogy.

LIFO: Last element added is the first removed.

Analogy: Stack of plates. The last plate placed on top is the first one taken out.

4. How is a stack implemented using an array and linked list?

Array: Fixed size, top variable tracks position. Push increments top, Pop decrements top.

Linked List: Dynamic, each node has data and next. The top pointer points to latest
inserted node.

5. Write an algorithm to reverse a string using a stack. Algorithm ReverseString(str)

2. For each character c in str: PUSH(S, c)

3. Initialize empty string result

4. While stack is not empty: result = result + POP(S)

5. Return result

6. What is the role of a stack in recursion?

Each recursive call stores local variables, return address, and parameters on the stack.

Example: Factorial recursion → function calls are stored in stack until base case is reached,
then they return back.

7. Discuss the difference between static and dynamic stack.

Static Stack: Implemented using arrays. Fixed size, may cause overflow.

Dynamic Stack: Implemented using linked list. Flexible size, no overflow unless memory
exhausted.

8. Write a program to sort a stack using only stack operations.

(Approach: Use a temporary stack)

void sortStack(Stack& s) { Stack temp; while (!s.isEmpty()) { int val = s.pop(); while
(!temp.isEmpty() && temp.peek() > val) { s.push(temp.pop()); } temp.push(val); } while
(!temp.isEmpty()) { s.push(temp.pop()); } }

9. How can you reverse a linked list using a stack?

Push all nodes into a stack.

Pop one by one and reconnect → new reversed list.

10. How can you implement two stacks in a single array?

Use one stack growing from left to right, another from right to left.

Overflow occurs when both meet in the middle.

Queue Questions

1. Define a queue and explain its main operations with examples, and applications.

Definition: A queue is a linear data structure that follows FIFO (First In, First Out) principle.
Operations:

Enqueue → insert at rear

Dequeue → remove from front

Peek → view front element

Example: Enqueue(10,20,30) → Queue=[10,20,30], Dequeue → removes 10 first.

Applications:

CPU scheduling

Printer job scheduling

Customer service line

2. FIFO principle with analogy.

FIFO: First inserted = first removed.

Analogy: People standing in a line at a ticket counter.

3. How is a queue implemented using array and linked list?

Array: Uses front and rear indices. Fixed size.

Linked list: Uses two pointers (front, rear). Dynamic size.

4. Difference between circular queue and regular queue?

Regular Queue: Wasted space after dequeuing.

Circular Queue: Connects last position to first → efficient memory usage.

5. Algorithm to implement circular queue using arrays.

Enqueue: rear = (rear+1) % max

Dequeue: front = (front+1) % max

Full: size == max

Empty: size == 0

6. What is a priority queue?

A queue where each element has priority.

Deletion is based on priority, not arrival order.

Insert & delete possible from both ends.

Types: Input-restricted & Output-restricted deques.

8. Queue overflow and underflow with examples.

Overflow: Trying to enqueue when queue is full.

Underflow: Trying to dequeue from empty queue.

9. Program to reverse first k elements of a queue.

(Use stack for first k elements, then enqueue back).

10. Implement circular queue using linked list.

Maintain front and rear pointers.

Rear’s next always points to front.

11. Difference between Linear, Circular, Priority queue with use cases.

Linear → simple, but wastes space (use: basic waiting line).

Circular → efficient reuse of memory (use: buffering in OS).

Priority → higher priority first (use: CPU scheduling).

Stack & Queue Combined Questions

1. Compare stack and queue (differences).

Stack: LIFO, insertion/deletion at top.

Queue: FIFO, insertion at rear, deletion at front.

2. Implement stack using two queues.

Push → Enqueue in main queue.

Pop → Dequeue all except last into helper queue, return last.

3. Implement queue using two stacks.

Enqueue → Push in stack1.

Dequeue → If stack2 empty, move all elements from stack1 to stack2, then pop.

4. When to use stack vs queue (scenarios).

Queue: Scheduling, buffering, message passing.

5. Palindrome check using stack & queue.

Push string into stack (reverse order).

Enqueue string into queue (normal order).

Compare both → if same → palindrome.