Exams › GATE › Technical

Suppose a circular queue of capacity $(n-1)$ elements is implemented with an array of $n$ elements. Assume that the insertion and deletion operations are carried out using REAR and FRONT as array index variables, respectively. Initially, REAR = FRONT = 0. The conditions to detect queue full and queue empty are

1. full: $(\text{REAR} + 1) \bmod n = \text{FRONT}$; empty: REAR = FRONT
2. full: $(\text{REAR} + 1) \bmod n = \text{FRONT}$; empty: $(\text{FRONT} + 1) \bmod n = \text{REAR}$
3. full: REAR = FRONT; empty: $(\text{REAR} + 1) \bmod n = \text{FRONT}$
4. full: $(\text{FRONT} + 1) \bmod n = \text{REAR}$; empty: REAR = FRONT

Correct answer: full: $(\text{REAR} + 1) \bmod n = \text{FRONT}$; empty: REAR = FRONT

Solution

In a circular queue of capacity $n-1$ using an array of size $n$, one slot is kept empty to distinguish full from empty. The queue is empty when FRONT and REAR are equal, and it is full when advancing REAR by one position would make it equal to FRONT.

Related GATE Technical questions

• A binary search tree T contains n distinct elements. What is the time complexity of picking an element in T that is smaller than the maximum element in T?
• An array \([82, 101, 90, 11, 111, 75, 33, 131, 44, 93]\) is heapified. Which one of the following options represents the first three elements in the heapified array?
• Consider a binary min-heap containing 105 distinct elements. Let \(k\) be the index in the underlying array of the maximum element stored in the heap. The number of possible values of \(k\) is
• Which of the following statement(s) is/are TRUE for any binary search tree (BST) having $n$ distinct integers?
• The height of a binary tree is the maximum number of edges in any root-to-leaf path. The maximum number of nodes in a binary tree of height $h$ is:
• The maximum number of binary trees that can be formed with three unlabeled nodes is:

⚔️ Practice GATE Technical free + battle 1v1 →