1

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.

4
  • Ha! I think I get it now. Since the size of the array is 100, then the last element of the array is actually p[99] so spos=100 means that the queue is full. Such an easy and regular concept and I got confused in it. smacks his head, and goes away muttering to himself Commented Aug 21, 2010 at 11:14
  • Thanks guys. I don't know how I missed this point. Poor me (: Commented Aug 21, 2010 at 11:15
  • stop reading "Naruto" and read more code : P Commented Aug 21, 2010 at 11:45
  • Not at all related to the question, but why does the author of the code sample use two different index variables (spos, rpos)? Seems optimally you'd only need one. Commented Apr 6, 2012 at 18:38

5 Answers 5

5

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

Sign up to request clarification or add additional context in comments.

Comments

2

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.

Comments

2

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

Comments

1

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

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

Comments

0

Implementation of queue in C language

http://www.csnotes32.com/2014/09/c-program-to-implement-queue-using-array.html

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.