Queues Questions and Answers

Q: A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed efficiently. Which one of the following statements is CORRECT (\(n\) refers to the number of items in the queue)?

Both operations can be performed in \(O(1)\) time.Implement the queue as a circular array with two indices, front and rear. ENQUEUE writes at rear and advances it modulo the array size; DEQUEUE reads at front and advances it modulo the size. Neither operation shifts any elements, so each takes constant time.The \(\Omega(n)\) options describe a naive array that shifts all elements forward on every DEQUEUE, which the question rules out by saying the operations are performed efficiently. \(\Omega(\log n)\) belongs to heap-based priority queues, not to a simple queue.

Q: A data structure where elements can be added or removed at either end but not in the middle.

This data structure is a deque.A deque (double-ended queue) allows insertion and deletion at both the front and the rear, but not in the middle. It generalises both the stack and the queue.A stack allows insertion and removal at one end only (last in, first out). A queue inserts at the rear and removes from the front (first in, first out), so each end supports only one operation. A linked list allows insertion and deletion anywhere, including the middle.

Q: Identify the odd one :

The odd one is Tower of Hanoi.A priority queue, a circular queue and a deque (double-ended queue) are all queue data structures: variations on storing elements and removing them in a defined order from the ends or by priority.The Tower of Hanoi is a problem, a puzzle of moving discs between pegs, usually solved by recursion and often used to illustrate stacks and recursion. It is not a kind of queue, so it does not belong with the other three.

Q: A queue data structure can be used for :

A queue can be used for Resource allocation.A queue is first-in, first-out, so it suits sharing a resource fairly among waiting requests: CPU scheduling, printer spooling and disk request queues all serve jobs in the order they arrive.Expression parsing, expression evaluation and recursion all depend on last-in, first-out behaviour, so they use a stack, not a queue.

Q: A deque is :

A deque is a queue with insert and delete defined for both front and rear ends of the queue.Deque stands for double-ended queue. Unlike an ordinary queue, which inserts at the rear and deletes at the front, a deque allows insertion and deletion at both ends, so it can serve as a stack or a queue.The definition is about the operations allowed, not the implementation. A deque can be implemented with a doubly linked list or a circular array, so options A and B describe possible implementations rather than what a deque is, and 'just a queue' misses the two-ended operations.

Q: In an array-based implementation of a circular queue, overflow occurs when

Overflow occurs when (rear + 1) % size == front.In the usual array implementation, one slot is kept empty so that a full queue can be told apart from an empty one. The queue is full when advancing rear by one position, wrapping round with the modulus, would land on front.\[ (rear + 1) \bmod size = front \Rightarrow \text{full} \]rear == front is the test for an empty queue in this scheme. rear == size - 1 is the overflow test for a linear queue; in a circular queue there may still be free slots at the start of the array. front == -1 is how some implementations mark an empty queue, not a full one.

Q: Which of the following operations can be performed on a queue ?

The operations on a queue are Enqueue and Dequeue.A queue is a first-in, first-out structure: enqueue adds an element at the rear and dequeue removes one from the front.Push and pop are the stack's operations, at a single end, so 'All of the above' is wrong too.Queues are used in printer spooling, CPU scheduling and breadth-first search.

Q: In a circular queue implemented using an array of size 5, if front = 2 and rear = 4, how many elements are currently in the queue ?

There are 3 elements in the queue.With front pointing to the first element and rear to the last, the queue occupies positions 2, 3 and 4. Since rear is not behind front, there is no wrap-around:\[ \begin{aligned} \text{count} &= \text{rear} - \text{front} + 1 \\ &= 4 - 2 + 1 = 3 \end{aligned} \]2 is the slip of computing rear minus front without adding 1. In general a circular queue uses \((\text{rear} - \text{front} + 1 + n) \bmod n\) for a non-empty queue, so the count can be determined.

Q: Which of the following operations on a queue data structure has a time complexity of O(1) ?(a) Enqueue (b) Dequeue (c) Peek (d) Clear

The O(1) operations are a, b and c: enqueue, dequeue and peek.With front and rear pointers (in a linked list or circular array), enqueue adds at the rear, dequeue removes at the front and peek reads the front, each in constant time whatever the length of the queue.Clear has to release or reset every element, so it generally takes time proportional to the number of elements. That rules out options leaving out enqueue or peek.

A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed efficiently. Which one of the following statements is CORRECT (\(n\) refers to the number of items in the queue)?

A.Both operations can be performed in \(O(1)\) time
B.At most one operation can be performed in \(O(1)\) time but the worst case time for the other operation will be \(\Omega(n)\)
C.The worst case time complexity for both operations will be \(\Omega(n)\)
D.Worst case time complexity for both operations will be \(\Omega(\log n)\)

Exam Year(s)

GATE CS - 2016,

Answer: A

Both operations can be performed in \(O(1)\) time.

Implement the queue as a circular array with two indices, front and rear. ENQUEUE writes at rear and advances it modulo the array size; DEQUEUE reads at front and advances it modulo the size. Neither operation shifts any elements, so each takes constant time.

The \(\Omega(n)\) options describe a naive array that shifts all elements forward on every DEQUEUE, which the question rules out by saying the operations are performed efficiently. \(\Omega(\log n)\) belongs to heap-based priority queues, not to a simple queue.

Discuss in Forum

A queue is implemented using a non-circular singly linked list. The queue has a head pointer and a tail pointer, as shown in the figure. Let \(n\) denote the number of nodes in the queue. Let enqueue be implemented by inserting a new node at the head, and dequeue be implemented by deletion of a node from the tail.

Singly linked list of nodes, each pointing to the next, with head pointing to the first node, tail pointing to the last node and the last node's next pointer null

Which one of the following is the time complexity of the most time-efficient implementation of enqueue and dequeue, respectively, for this data structure?

A.\(\theta(1), \theta(1)\)
B.\(\theta(1), \theta(n)\)
C.\(\theta(n), \theta(1)\)
D.\(\theta(n), \theta(n)\)

Exam Year(s)

GATE CS - 2018,

Answer: B

The best possible times are \(\theta(1)\) for enqueue and \(\theta(n)\) for dequeue.

Enqueue inserts at the head: make the new node point to the current first node and move head to it. That is a fixed number of pointer changes, so \(\theta(1)\).

Dequeue deletes at the tail. Removing the last node means setting the second-to-last node's next pointer to null and moving tail to it, but in a singly linked list the links point from head towards tail, so the only way to reach that node is to walk from the head: \(\theta(n)\).

\(\theta(1), \theta(1)\) would need the opposite arrangement (enqueue at the tail, dequeue at the head). Enqueue at the head never needs a traversal, which rules out the options with \(\theta(n)\) for enqueue.

Discuss in Forum

A data structure where elements can be added or removed at either end but not in the middle.

A.Linked lists
B.Stacks
C.Queues
D.deque

Exam Year(s)

MH SET - 2018, SET Exam - 2018,

Answer: D

This data structure is a deque.

A deque (double-ended queue) allows insertion and deletion at both the front and the rear, but not in the middle. It generalises both the stack and the queue.

A stack allows insertion and removal at one end only (last in, first out). A queue inserts at the rear and removes from the front (first in, first out), so each end supports only one operation. A linked list allows insertion and deletion anywhere, including the middle.

Discuss in Forum

Identify the odd one :

A.Priority queue
B.Circular queue
C.Deque
D.Tower of Hanoi

Exam Year(s)

MH SET - 2019, MH SET - 2025, SET Exam - 2019, SET Exam - 2025,

Answer: D

The odd one is Tower of Hanoi.

A priority queue, a circular queue and a deque (double-ended queue) are all queue data structures: variations on storing elements and removing them in a defined order from the ends or by priority.

The Tower of Hanoi is a problem, a puzzle of moving discs between pegs, usually solved by recursion and often used to illustrate stacks and recursion. It is not a kind of queue, so it does not belong with the other three.

Discuss in Forum

A queue data structure can be used for :

A.Resource allocation
B.Expression parsing
C.Recursion
D.Expression evaluation

Exam Year(s)

MH SET - 2020, SET Exam - 2020,

Answer: A

A queue can be used for Resource allocation.

A queue is first-in, first-out, so it suits sharing a resource fairly among waiting requests: CPU scheduling, printer spooling and disk request queues all serve jobs in the order they arrive.

Expression parsing, expression evaluation and recursion all depend on last-in, first-out behaviour, so they use a stack, not a queue.

Discuss in Forum

A deque is :

A.A queue implemented with a doubly linked list
B.A queue implemented with both singly and doubly linked lists
C.Just a queue
D.A queue with insert and delete defined for both front and rear ends of the queue

Exam Year(s)

MH SET - 2023, SET Exam - 2023,

Answer: D

A deque is a queue with insert and delete defined for both front and rear ends of the queue.

Deque stands for double-ended queue. Unlike an ordinary queue, which inserts at the rear and deletes at the front, a deque allows insertion and deletion at both ends, so it can serve as a stack or a queue.

The definition is about the operations allowed, not the implementation. A deque can be implemented with a doubly linked list or a circular array, so options A and B describe possible implementations rather than what a deque is, and 'just a queue' misses the two-ended operations.

Discuss in Forum

In an array-based implementation of a circular queue, overflow occurs when

A.rear == front
B.rear == size - 1
C.front == -1
D.(rear + 1) % size == front

Exam Year(s)

Tripura Public Service Commission - 2026,

Answer: D

Overflow occurs when (rear + 1) % size == front.

In the usual array implementation, one slot is kept empty so that a full queue can be told apart from an empty one. The queue is full when advancing rear by one position, wrapping round with the modulus, would land on front.

\[ (rear + 1) \bmod size = front \Rightarrow \text{full} \]

rear == front is the test for an empty queue in this scheme. rear == size - 1 is the overflow test for a linear queue; in a circular queue there may still be free slots at the start of the array. front == -1 is how some implementations mark an empty queue, not a full one.

Discuss in Forum

Which of the following operations can be performed on a queue ?

A.Push
B.Pop
C.Enqueue and Dequeue
D.All of the above

Exam Year(s)

Tripura Public Service Commission - 2025,

Answer: C

The operations on a queue are Enqueue and Dequeue.

A queue is a first-in, first-out structure: enqueue adds an element at the rear and dequeue removes one from the front.

Push and pop are the stack's operations, at a single end, so 'All of the above' is wrong too.

Queues are used in printer spooling, CPU scheduling and breadth-first search.

Discuss in Forum

In a circular queue implemented using an array of size 5, if front = 2 and rear = 4, how many elements are currently in the queue ?

A.2
B.3
C.4
D.Cannot be determined

Exam Year(s)

Tripura Public Service Commission - 2026,

Answer: B

There are 3 elements in the queue.

With front pointing to the first element and rear to the last, the queue occupies positions 2, 3 and 4. Since rear is not behind front, there is no wrap-around:

\[ \begin{aligned} \text{count} &= \text{rear} - \text{front} + 1 \\ &= 4 - 2 + 1 = 3 \end{aligned} \]

2 is the slip of computing rear minus front without adding 1. In general a circular queue uses \((\text{rear} - \text{front} + 1 + n) \bmod n\) for a non-empty queue, so the count can be determined.

Discuss in Forum

10.

Which of the following operations on a queue data structure has a time complexity of O(1) ?

(a) Enqueue (b) Dequeue (c) Peek (d) Clear

A.a and b
B.b only
C.c only
D.a, b and c

Exam Year(s)

Tripura Public Service Commission - 2025,

Answer: D

The O(1) operations are a, b and c: enqueue, dequeue and peek.

With front and rear pointers (in a linked list or circular array), enqueue adds at the rear, dequeue removes at the front and peek reads the front, each in constant time whatever the length of the queue.

Clear has to release or reset every element, so it generally takes time proportional to the number of elements. That rules out options leaving out enqueue or peek.

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: Queues Questions and Answers || Queues MCQ Questions and Answers || Queues GK Questions and Answers || Queues GK MCQ Questions || Queues Multiple Choice Questions and Answers || Queues GK || GK on Queues || Data Structures and Algorithms Questions and Answers || Data Structures and Algorithms MCQ Questions and Answers || Data Structures and Algorithms GK Questions and Answers || GK on Data Structures and Algorithms

Queues Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications