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.

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, SET Exam - 2019,

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

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