Question

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)

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top