Conquer the Queue

vegaseat 2 207 Views

Looking at the First In First Out (FIFO) data situation. Just like a line at the grocery store check-out. Its counterpart FILO would be like a stack of dinner plates.

// A linear list of data accessed first in, first out (FIFO) is called a QUEUE.
// compiled with free PellesC:  http://smorgasbordet.com/pellesc/index.htm

#include <stdio.h>   // in/out function header
#include <string.h>  // string function header
#include <stdlib.h>  // malloc()

void q_enter(void);
void q_list(void);
void q_store(char *ptr);
void q_delete(void);

int store = 0;         // next storage position in queue[] 
int retrieve = 0;      // retrieve position in queue[] 
char *queue[100];      // this array forms the queue 

int main()
{
  q_enter();     // enter some data in the queue and list the data 
  printf("\n\nThis is all the data in the fifo queue:");
  q_list();   
  q_delete();  // delete first entry in queue and list again
  printf("\n\nThis is data after one deletion (first in, first out):");
  q_list();    
  getchar();  // wait
  return 0;
}

//
// prompt for data entry and store in queue via q_store()
// gets() allows string input only, kind of poor, 
// could stand a more bulletproof entry here
//
void q_enter(void) 
{
  static char str[100], *ptr;

  do {
    printf("Enter name (ENTER only will exit) : ");
    scanf("%s",str);     // gets(str);
    ptr = (char *) malloc(strlen(str));  // starting address of memory 
    strcpy(ptr,str);
    if (*str)
    {  
      q_store(ptr);   // store in queue if string has info
    } 
  } while (*str);     // until no entry
}

//
// list the contents of the queue 
//
void q_list(void)   
{
  int k;

  for (k = retrieve; k < store; k++)
  {
    printf("\n%d) %s",k+1,queue[k]);
  }
}

//
// store data items in the queue 
//
void q_store(char *ptr)
{   
  if (store == 100) { 
    printf("\nList is full!");  
    return; 
  }
  queue[store] = ptr;
  store++;  // point to next available storage position in queue[] 
}

//
// delete data at retrieve position
//
void q_delete(void)     
{
  if (store == retrieve) { 
    printf("\nQueue is empty!"); 
    return; 
  }
  retrieve++;   // move retrieve position to next data item 
}
Member Avatar for mvmalderen
mvmalderen 2,072 Postaholic

This is just a slightly modified version of the Queue implementation found in the book
C: The Complete Reference by Herb Schildt.
You should take care when using code that was written by Herb Schildt, especially because his code is widely known as buggy code, and you may not have noticed it, but there's a memory leak lurking in the code: in the q_enter() function on line 41, there's this line of code: ptr = (char *) malloc(strlen(str)); .
This line of code dynamically allocates memory, but when does that memory ever get deallocated?
The answer is: never (unless your OS does it, but you should never rely on this).
Another peculiarity can be found on line 40: scanf("%s",str); , well, that's no better than gets(str); since it will still allow an array boundary overrun. You might want to use fgets() instead, or use scanf() in this way: scanf("%99s",str); .
At first sight for the memory allocation problem you might think of a fix like this:

/* this code should execute when main() is entered */
for ( i = 0; i < 100; i++ )
{
  queue[i] = NULL;
}

/* this code should execute before main() returns */
for ( i = 0; i < 100; i++ )
{
  if ( queue[i] )
    free ( queue[i] );
}

However, this is not a very good solution, since it will only make sense when used in this context, it for example won't prevent the user from manually invoking q_store() with as argument a pointer pointing to some not-dynamically-allocated-memory, resulting in calling free() on a pointer that points to memory which wasn't dynamically allocated. And the problem only gets worse when this would be a circular queue :P.

Edited by mvmalderen because: n/a
commented: nice comments :) +27
Member Avatar for Ancient Dragon
Ancient Dragon 5,243 Achieved Level 70

I would think it would be better to implement the queue as a linked list so that it can contain an (nearly) infinite number of items in the queue.

Edited by Ancient Dragon because: n/a
mvmalderen commented: Yes. +8
Member Avatar for jephthah
jephthah 1,888 Posting Maven

everybody loves to hate on Schildt, don't they?

i think the majority of criticisms against his C: A Reference Manual, are trivial. I'm not saying it's a great book, and there are undoubtedly some errors, but it's not as bad as the bandwagon lined up against him would like to make it.

There are very few books out there subject to such scrutiny, that are free of errors. this whole "bullschildt" business is the result of two people on the standards committee apparently having personal grievances against him and setting out on a smear campaign.

there are very few people on these boards who could compete with schildt. Only one person for certain, but I won't name her name.

Member Avatar for mitrmkar
mitrmkar 1,056 Posting Virtuoso

Adding to what's been said, just in case anyone is interested in trying out the code.
This

printf("Enter name (ENTER only will exit) : ");
scanf("%s",str);

will not work as intended, i.e. just pressing ENTER without any other input does not make scanf() return. With the original gets() it has worked. So, fgets() would probably be a good choice there.

Then

ptr = (char *) malloc( strlen(str) ); // starting address of memory
strcpy(ptr,str);

simply corrupts the heap. It should rather be

ptr = malloc( 1 + strlen(str) );
strcpy(ptr,str);

so that there's room for the terminating '\0' character, added by the strcpy() . And related to malloc() , it's good to check that the allocation succeeded i.e. it did not return NULL.

Then, in q_enter() maybe move the if (*str) statement a bit higher so that the 'exit' case is handled properly (no need to go through malloc/strcpy in case the input length is zero).

PS. I think I somewhat agree with what jephthah is saying, but then again, if this original code really is taken from a book titled "C: The Complete Reference" I'm not so sure anymore after all.

Edited by mitrmkar because: n/a
mvmalderen commented: Excellent addition :) +8
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

Edit Preview