A queue is a collection of data, in this collection the first element added(enqueue) to the queue, will be the first one to be removed this operation is named dequeue(Wikipedia).

300px-Data_Queue.svg

In this post I show you how implement a very simple static queue without using memory allocation

Global delaration

#define MAXROW  20 //number item into queue
#define MAXCOL 120 

char queue[MAXROW][MAXCOL];
int Startq,Endq;
char Ow,full;

Initialization a Queue

//init a queue, if OWold is 1, it will overwrite oldest item
void initQ(char OWold)
{
   memset(queue ,0,sizeof(queue));//clear queue
   Startq=0;//start queue
   Endq=0;//end queue
   full=0;//1 if queue is full
   Ow=OWold;
   return;
}

Use EnqueueQ function to add a item at the end of queue or DequeueQ function to remove oldest item from queue

void Increase(int *p)
{
  (*p)++;
  *p=(*p)%MAXROW;
  return;
}

// Add s in to queue, return last index if ok otherwise -1
int EnqueueQ(char* s)
{

    if(full && !Ow)
        return -1;//Error if queue is full
    if (strlen(s)>MAXCOL)//truncate row
        s[MAXCOL]=0;
    sprintf(queue[Endq],"%s",s);
    Increase(&Endq);

   if(Endq==Startq)//check if queue is full
        full=1;

    if(Endq==Startq && full && Ow)
        Increase(&Startq);//overwrite old item

    return Endq;//return last index item
}
// remove from queue oldest element and pass it into s argument
int DequeueQ(char* s)
{
    if(Startq!=Endq || full)
    {
       strcpy(s,queue[Startq]);
       Increase(&Startq);
       if(full)
          full=0;
       return Startq;
    }
    return -1;
}

In this example we will try to enqueue 25 elements even if the capacity is 20 elements

void TestQueue()
{
   char s[100],i;
   initQ(0);//Init queue without overwrite old item
   //initQ(1);//Use this initialization to overwrite old item

   for (i=0;i<25;i++)    
   {        
      sprintf (s,"row %10d",i);        
      if(EnqueueQ(s)==-1)           
         printf ("Not Addedded %s\n",s);//buffer is full        
      else           
         printf ("    Addedded %s\n",s);    
   }    
    while(DequeueQ(s)>-1)
       printf("%s\n",s);
   printf("END\n");

}

See also:Dictionary with int key and string vslue

Advertisements