1
$\begingroup$

I am Implementing a Queue using circular arrays in C language .The Implementation uses one empty position to indicate that the queue is full.That is if the rear is two position behind front. The condition is we cant use a variable to count the entries in the queue as we insert or delete . I have created this function to find the size of queue with Time Complexity Big-Oh(n) because it starts with front and goes upto rear in a loop .

int QueueSize(Queue *q)
{
    if(QueueEmpty(q))
    {
        return 0;
    }
    else{
        int count=0;
    for(int i=q->front;;i=(i+1)%MAXQUEUE)
    {
        count++;
        if(i==q->rear) break;
    }
        return count;
}
}

Is there a way to find the size of queue in constant time ? Elements are inserted from rear and deleted from front ! My Queue starts from 0 and assume maximum queue size is 6 in below example

10 Appended at position 0
20 Appended at position 1
30 Appended at position 2
40 Appended at position 3
50 Appended at position 4
10 Removed from position 0
20 Removed from position 1
60 Appended at position 5
70 Appended at position 0
30 Removed from position 2
40 Removed from position 3
80 Appended at position 1
90 Appended at position 2
Queue Size:5
Position:4  Element:50 (front)
Position:5  Element:60
Position:0  Element:70
Position:1  Element:80
Position:2  Element:90 (rear)
$\endgroup$

closed as off-topic by Yuval Filmus, David Richerby, Evil, fade2black, Rick Decker Aug 24 '17 at 13:33

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions about software development or programming tools are off-topic here, but can be asked on Stack Overflow." – Yuval Filmus, David Richerby, Evil, fade2black, Rick Decker
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ This seems to be very implementation-dependent, and so more of a programming question. Try computing q->rear - q->front. $\endgroup$ – Yuval Filmus Aug 22 '17 at 15:40
  • $\begingroup$ Should I post the whole code ? Or ask It at stack overflow ? $\endgroup$ – Pradeep Kumar Aug 22 '17 at 15:45
  • 1
    $\begingroup$ If your question involves code then it belongs on stackoverflow. $\endgroup$ – Yuval Filmus Aug 22 '17 at 15:45
  • $\begingroup$ No you just need to know the implementation details . $\endgroup$ – Pradeep Kumar Aug 22 '17 at 15:49
  • 2
    $\begingroup$ I don't understand the question. In a circular buffer, the number of elements in it can be computed in constant time. (It's basically the distance between the pointers, wrapping around and $\pm 1$.) (And that much doesn't seem to language dependent, @YuvalFilmus?) $\endgroup$ – Raphael Aug 22 '17 at 16:36
1
$\begingroup$

Suppose that the queue consists of elements $Q[a],\ldots,Q[b]$, where $Q = Q[1],\ldots,Q[n]$ is an array of length $n$. If $a \leq b$ then the queue contains $b-a+1$ elements, and if $a > b$ then the queue contains $b-a+1+n$ elements.

$\endgroup$
  • $\begingroup$ How can queue contain more than n elements ? $\endgroup$ – Pradeep Kumar Aug 22 '17 at 17:27
  • $\begingroup$ It doesn't contain more than $n$ elements. I encourage you to try some example such as $a=n$ and $b=1$. The queue in this case contains $b-a+1+n = 2$ elements, $Q[n]$ and $Q[1]$. $\endgroup$ – Yuval Filmus Aug 22 '17 at 17:29
  • $\begingroup$ 10 Appended 20 Appended 30 Appended 40 Appended 50 Appended 10 Removed 20 Removed 60 Appended 70 Appended 30 Removed 40 Removed 80 Appended 90 Appended Queue Size:5 Position:4 Element:50 Position:5 Element:60 Position:0 Element:70 Position:1 Element:80 Position:2 Element:90 Now here the front is at 4 and rear is at 2 $\endgroup$ – Pradeep Kumar Aug 22 '17 at 17:34
  • $\begingroup$ My indices start at 1. You'll have to figure out on your own what changes (if anything) when the indices start at 0. $\endgroup$ – Yuval Filmus Aug 22 '17 at 17:36
  • 1
    $\begingroup$ Take it as a challenge. $\endgroup$ – Yuval Filmus Aug 22 '17 at 18:38

Not the answer you're looking for? Browse other questions tagged or ask your own question.