views:

91

answers:

4

I'm learning queues from a book. The author explains the operation of inserting an element in queue using the following code.

#define MAX 100
char *p[MAX];
int spos = 0; // spos: holds the index of the **next free** storage location

int rpos = 0;// rpos: holds the index of the next item to retrieve

void qstore(char *q)
{
  if(spos==MAX) {
    printf("List Full\n");
    return;
  }
  p[spos] = q;
  spos++;
}

So according to the above code, a queue is full if spos=100 i.e the last element in the array. Now, since spos holds the index of the next free storage location, then when spos=100, the last position in the array is empty. So why is it explained as List full? Shouldn't this code be modified such that it allows the last position in the array to be filled or am I missing something very obvious?

Thanks.

+5  A: 

p[100] allocates 100 slots, at indexes 0 through 99. There is no position 100.

Ignacio Vazquez-Abrams
+2  A: 

I guess because p[100] is an invalid access you can do to your array. The last valid location is p[99]

Plus considering that you are implementing a queue using an array, never confuse an abstract data type with one of its possible implementations

rano
+1  A: 

The index of the last element of the array if 99, not 100.

So when spos=100, the queue is really full.

Curd
+2  A: 

Array indexing starts from 0, so for you MAX == 100 you'll have valid array locations between 0 - 99. So when spos == 99 means the last position in array is available and you are allowed to put something in the queue, then spos gets incremented and actually "points" to an invalid location, meaning the list is full which is actually true as you have already filled the 0 -99 positions in the array.

celavek