Programmando Facile

Strutture Dati – La Coda (Queue)

Continuiamo con le strutture dati, nel precedente articolo vi ho parlato di Stack, oggi vi farò vedere invece come funziona una coda e vi darò la sua implementazione in C tramite Array. Una Coda (Queue) è una struttura dati che si basa sul principio del Fifo (first in – first out, il primo ad entrare è il primo ad uscire).

Una sua implementazione può essere vista tramite Array:

Le intestazioni salvate in un file chiamato queue.h

void enqueue(int *q,int *tail, int element);
int dequeue(int *q,int *head);
int full(int tail,const int size);
int empty(int head,int tail);
void init(int *head, int *tail);

L’algoritmo della Coda salvatelo in un file chiamato queue.c

/*initialize queue pointer*/
void init(int *head, int *tail)
{
     *head = *tail = 0;
}
/* enqueue an element
   precondition: the queue is not full
*/
void enqueue(int *q,int *tail, int element)
{
    q[(*tail)++] = element;
}
/* dequeue an element
   precondition: queue is not empty*/
int dequeue(int *q,int *head)
{
     return q[(*head)++];
}
/* report queue is full nor not
   return 1 if queue is full, otherwise return 0*/
int full(int tail,const int size)
{
    return tail == size ? 1 : 0;
}

/* report queue is empty or not
  return 1 if the queue is empty, otherwise return 0*/
int empty(int head, int tail)
{
     return head == tail ? 1 : 0;
}

Infine il programma di prova della coda salvatelo in un file chiamato testqueue.c

#include
#include
#include "queue.h"
#define size 3
void main(){
   int head,tail,element;
   int queue[size];
   // initialize queue
   init(&head,&tail);
   // enqueue elements
   while(full(tail,size) != 1){
      element = rand();
      printf("enqueue element %d\n",element);
      enqueue(queue,&tail,element);
      printf("head=%d,tail=%d\n",head,tail);
      //press enter to enqueue more
      getchar();
   }
   printf("queue is full\n");
   // dequeue elements from
   while(!empty(head,tail)){
     element = dequeue(queue,&head);
     printf("dequeue element %d \n",element)
     //press enter to pop more
     getchar();
   }
   printf("queue is empty\n");
   getchar();
}