search
Log In
29 votes
7k views

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: $(REAR+1) \mod n == FRONT$
    empty: $REAR == FRONT$
     
  2.  full: $(REAR+1) \mod n == FRONT$
    empty: $(FRONT+1) \mod n == REAR$
     
  3.  full: $REAR == FRONT$
    empty: $(REAR+1) \mod n == FRONT$
     
  4.  full: $(FRONT+1) \mod n == REAR$
    empty: $REAR == FRONT$
in DS
edited by
7k views
5
Notice -> In this implementation we are wasting one unit of memory.
2
Yes, otherwise we can store n elements into a circular queue of size n

4 Answers

33 votes
 
Best answer

$\text{REAR} =\text{Write}$ 

$\text{FRONT} = \text{Read}$

full: $(\text{REAR}+1) \mod n == \text{FRONT}$

empty: $\text{REAR} == \text{FRONT}$

Only option (A) matches.


edited by
1
From the Given options it is clear that  Option A is Ans.

@Anirudh but

Initially when queue is empty @time Front=Rear=0

Now after Insertion of 1 element into empty Q at which index does front and rear point?? Can u plz explain??
2
First of all, i did not understand - circular queue of size = n-1, while array has n elements ...
Does it mean that circular queue can only accomodate n-1 element or its index can varry from 0 to n-1 ??
1
Same [email protected] this was my next confusion ;p
18
@rajeshpradhan+vijaycs
in this implementation of circular queue it is given that "Suppose a circular queue of capacity (n−1) elements is implemented with an array of n elements. " so it means that its index varies from 1 to n{array contains n slots} but it can accomodate n-1 elements
now initially rear=front=0 // means queue is empty
  in this implementation rear is always points to an empty location where a new element will be inserted suppose n=10 front is at 6 and rear is at 5 this means currently 5 is an empty location and new element will be inserted at location 5 but before insertion at loc 5 it will check for full condition "(rear+1)modn=front" so for this case (5+1)mod 10=6 so this meets the full condition as  "(rear+1)modn=front"  but here is still an empty slot so that is the reason that why we can accomodate only n-1 elements.
and now if f=r so as i told u before that rear is always pointed to an empty location so at ths tme both front and rear pointing to an empty location so this meets the condtion that circular queue is empty.
-------- i hope tht this will help u if u have any doubt after then plzz refer to CLRS (Ed 3) Pg:234-235and excercise 10.1.4
3
it means that the no of elements in the circular array in max on n-1 . Yes it means that the no of elements is of maximum of n-1 . this is done to make sure that rear==front means that the array is empty.

 

if we allow maximum of n elements in the circular array then if the circular array is full in that case rear would be equal to front. which by the convention means the array is empty.
so in order to avoid this confusion . we allow a maximum of n-1 elements.
0
@ Saurabh, front never points to any queue element right? Queue starts from front+1 , i mean if front is currently at say 4 and the size of queue is 5, then queue will contain elements at 5,0,1,2,3 right?
0

Prashant. this figure is not compitable with ques.

you take the array index from 0 to n now there will be n+1 slots are available in array but in ques  circular queue of capacity (n−1) elements is implemented with an array of n elements.

then how can u implement a circular queue of capacity (n−1) elements with an array of n+1elements.

 initially rear=front=0 { means queue is empty}

if(rear=front=0) {

 F++

R++}

1st element should be inserted at location 1

0
in case of just 1element in the queue front and rear both will be 1 ,   according to option A  if front=rear then queue is empty  .  here  contradiction    .... plz clear it
0
Can you please tell me how you are considering that rear will always point to the next empty location.As rear always point to the newly inserted element not to the next memory location of newly inserted element
1

If the capacity of the queue itself is "n-1", are we not supposed to use       

 (rear +1)mod(n-1) == front?

13 votes

D -> This is incorrect, because if you have two elements in Queue of size 5, Front + 1 will not point to Rear. full: (FRONT+1) mod n == REAR is incorrect.

C-> full: REAR == FRONT This is wrong part. Even initially we had rear = front = 0 , does this means queue is full ?

B-> empty: (FRONT+1) mod n == REAR , Initially queuee is empty, still  this heuristic will say that queue is not empty. As Rear = front = 0, So Front + 1 % mod n = 1 != 0

A is correct option.

11 votes
A will be the correct option just dry run it with smaller size of array..i did a programme on it earlier so i just answered to it by looking at it..
0
after one insertion the queue will not be empty and still rear and front will point to the same location?
2

No.
FRONT will be pointing to the first item in the queue, while REAR will be pointing to the next empty location. 

See this :

7 votes

In Circular Queue 

If Queue is full then first element should 0th element and last element should be n-1th element , lets assume an example if circular queue contains 5 element then :- 

1st element should be 0th element or front =0 and last will be 4th element or rear =4

so according to option A :- full: (REAR+1) mod n == FRONT

(4+1) mod 5 = 0 = Front then this condition satisfies so option C and D eliminated 

now we have to check 2nd condition of option A whether it is correct or not 

empty: $REAR == FRONT$ 

As we know in queue

if Front = Rear = -1 then queue is Empty 

So option B is eliminated 

Option A will be right option


edited by
Answer:

Related questions

27 votes
3 answers
1
3.9k views
The height of a tree is defined as the number of edges on the longest path in the tree. The function shown in the pseudo-code below is invoked as height (root) to compute the height of a binary tree rooted at the tree pointer root. int height(treeptr n) { if(n == NULL) return -1; if(n -> left == ... $\max(h1, h2) $ B1: $(1+ \text{height}(n \to \text{ right}))$ ; B2: $\max(h1, h2)$
asked Sep 29, 2014 in DS Arjun 3.9k views
33 votes
2 answers
2
4.3k views
The worst case running time to search for an element in a balanced binary search tree with $n2^{n}$ elements is $\Theta(n\log n)$ $\Theta(n2^n)$ $\Theta(n)$ $\Theta(\log n)$
asked Aug 5, 2014 in DS gatecse 4.3k views
21 votes
5 answers
3
4.7k views
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 ... ? $\Theta(1), \Theta(1)$ $\Theta(1), \Theta(n)$ $\Theta(n), \Theta(1)$ $\Theta(n), \Theta(n)$
asked Feb 14, 2018 in DS gatecse 4.7k views
40 votes
3 answers
4
8.8k views
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. At most one ... complexity for both operations will be $\Omega (n)$. Worst case time complexity for both operations will be $\Omega (\log n)$
asked Feb 12, 2016 in DS Sandeep Singh 8.8k views
...