Queues - Practice MCQs for CCAT

Correct Answer: B - FIFO

Queue follows FIFO - First In First Out principle.

Correct Answer: B - O(1)

Both enqueue and dequeue are O(1) operations.

Correct Answer: C - CPU Scheduling

CPU scheduling algorithms like Round Robin use queues.

Correct Answer: C - Queue

BFS uses queue to explore nodes level by level.

Correct Answer: C - rear wraps to front

In circular queue, rear wraps around to beginning if space available.

Correct Answer: B - Elements served by priority

In priority queue, elements are served based on priority, not arrival order.

Correct Answer: B - Double-ended queue

Deque is Double-ended queue allowing insertion/deletion at both ends.

Correct Answer: D - Expression evaluation

Expression evaluation uses stack, not queue.

Correct Answer: A - Both and space wastage

Array queue has overflow, underflow, and space wastage when elements are dequeued.

Correct Answer: C - Space wastage in linear queue

Circular queue reuses empty spaces at the front, solving space wastage.

Correct Answer: A - (rear + 1) % size == front

Queue is full when the next position of rear equals front: (rear + 1) % size == front.

Correct Answer: B - Stack

Two queues can be used to implement a stack by transferring elements.

Correct Answer: D - Insert at one end only

Input-restricted deque allows insertion at only one end but deletion at both ends.

Correct Answer: A - Insert at both ends, delete at one

Output-restricted deque allows insertion at both ends but deletion at only one end.

Correct Answer: C - Heap

Heap provides O(log n) insert and O(log n) extract-min/max for priority queue.

Correct Answer: C - Deque

Deque (double-ended queue) efficiently solves sliding window maximum in O(n).

Correct Answer: D - Empty

When front equals rear in most implementations, the queue is empty.

Correct Answer: B - Queue with hash map

Queue maintains order of characters while hash map tracks frequency.

Correct Answer: A - FIFO tracks access order

FIFO property helps track which element was accessed least recently.

Correct Answer: B - Circular queue

Circular queue models the circular arrangement of people in Josephus problem.

Correct Answer: C - FIFO (First In First Out)

A queue follows FIFO — the first element enqueued (added) is the first one to be dequeued (removed), similar to people waiting in a line.

Correct Answer: C - Enqueue and Dequeue

The standard queue operations are enqueue (adding an element to the rear) and dequeue (removing an element from the front).

Correct Answer: A - Wasted space at the front (cannot reuse freed positions)

In a linear queue, after dequeuing, the front moves forward, leaving unused space at the beginning of the array that cannot be reused, even if the rear reaches the end.

Correct Answer: C - By wrapping around to the beginning of the array when the rear reaches the end

A circular queue uses modular arithmetic (rear = (rear + 1) % size) to wrap around to index 0 when the rear reaches the end of the array, reusing previously freed positions.

Correct Answer: B - (rear + 1) % n == front

In a circular queue, full condition is (rear + 1) % n == front. One position is deliberately left empty to distinguish between full and empty states.

Correct Answer: B - A queue where insertion and deletion can happen at both front and rear

A deque allows insertion and deletion at both the front and rear ends. It combines the functionality of both stacks and queues.

Correct Answer: D - Priority value

In a priority queue, each element has an associated priority. Elements with higher (or lower, depending on implementation) priority are dequeued before elements with lower priority.

Correct Answer: B - Heap

A binary heap provides O(log n) insertion and O(log n) deletion of the highest-priority element, making it the most efficient common implementation for priority queues.

Correct Answer: B - O(1) each

Using a linked list with both head (front) and tail (rear) pointers, enqueue (insert at tail) and dequeue (remove from head) are both O(1) operations.

Correct Answer: A - BFS (Breadth-First Search) of a graph

BFS uses a queue to explore nodes level by level. The current node's neighbors are enqueued and processed in FIFO order. Function calls, undo, and expression evaluation typically use stacks.

Correct Answer: D - 2

Number of elements = (rear - front + size) % size = (4 - 2 + 5) % 5 = 7 % 5 = 2. The elements are at indices 2 and 3.

Correct Answer: C - Both A and B are used in different implementations

Different implementations use different conventions. Some use front == rear to indicate empty, while others initialize both to -1 and check that condition. Both are valid approaches.

Correct Answer: B - Insertion only at the rear, deletion at both ends

An input-restricted deque restricts insertion to one end (rear) but allows deletion from both the front and rear ends.

Correct Answer: A - Insertion at both ends, deletion only at the front

An output-restricted deque allows insertion at both front and rear, but restricts deletion to only the front end.

Correct Answer: D - Priority queue

CPU scheduling algorithms like Priority Scheduling use priority queues where processes with higher priority are scheduled before those with lower priority.

Correct Answer: A - O(1)

In an unsorted array implementation, insertion is O(1) — we simply add the element at the end. However, dequeue (removing the highest priority) requires O(n) to find it.

Correct Answer: C - O(1)

In a sorted array implementation, the highest-priority element is always at a known position (front or rear), so dequeue is O(1). However, insertion requires O(n) to maintain the sorted order.

Correct Answer: D - All of the above

Queues handle scenarios where requests must be processed in order of arrival: print jobs wait in a queue, keystrokes are buffered in order, and web server requests are queued for processing.

Correct Answer: A - Multiple queues, each with its own scheduling algorithm

Multilevel queue scheduling partitions processes into groups, each with its own queue and scheduling algorithm (e.g., foreground processes use round-robin, background uses FCFS).

Correct Answer: D - n - 1

A circular queue of size n can hold at most n - 1 elements. One position is kept empty to distinguish between the full and empty conditions.

Correct Answer: D - O(1)

Although a single dequeue might take O(n) when S2 is empty (transferring all elements from S1), each element is transferred at most once. Over n operations, the amortized cost per dequeue is O(1).

Correct Answer: A - Queue

Level-order (BFS) traversal processes nodes level by level. A queue ensures that nodes at the current level are processed before their children (next level).

Correct Answer: D - rear = (rear + 1) % size

rear = (rear + 1) % size wraps the rear index around to 0 when it reaches the end of the array, implementing the circular behavior.

Correct Answer: A - Deque

A deque (specifically a monotonic deque) efficiently solves the sliding window maximum in O(n). Elements are added/removed from both ends to maintain the window and the maximum property.

Correct Answer: A - O(V + E)

BFS visits each vertex once (O(V)) and explores each edge once (O(E)). The queue operations (enqueue and dequeue) are O(1) each, giving total time O(V + E).

Correct Answer: C - Stack

If both insertion and deletion happen at the same end, the last element inserted is the first to be deleted — this is exactly LIFO behavior, which is a stack.

Correct Answer: D - The largest element

A max-priority queue always removes the element with the highest priority (largest value). A min-priority queue would remove the smallest element.

Correct Answer: A - Enqueue is O(n), dequeue is O(1)

With only a head pointer, dequeue (remove from head) is O(1). But enqueue (insert at the tail) requires traversing the entire list to reach the end, taking O(n).

Correct Answer: B - Circular queue

A circular buffer uses a fixed-size array with wrap-around semantics, implementing a circular queue. It's commonly used in producer-consumer scenarios and I/O buffering.

Correct Answer: D - O(log n)

In a heap-based priority queue, the new element is added at the end and then percolated up (heapify up) to maintain the heap property. The maximum number of swaps is the height of the heap, which is O(log n).