Size of Circular Queue [closed]
-
04-11-2019 - |
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