Queues in C language


#Queues #language

Queued data structures operate on the so-called FIFO logic – first in, first out – and retrieval is done in the order of insertion. The purpose of this article is to allow the reader to understand the use of queues in C language. To explain the algorithm, we chose to use a simply linked list to facilitate understanding even by beginners in C language.

  • Requirements

  • Definition

  • Model building a queue element

  • Queue operations

    • Startup

    • Inserting element in the queue

    • Remove queue element

    • Show queue

    • Data retrieval at the beginning of the queue

  • Complete example

    • row.h

    • fila_function.h

    • row.c

  • See too

Requirements

For this article, you will need to know the data types, structures, the use of typedef, pointers, user functions, simply linked lists and double linked lists.

Definition

The queue is a data structure which stores the data in FIFO (First In First Out) order, in Portuguese First to Enter First to Exit. Data recovery will be done in the order of insertion.

For our explanation, we will use a simply linked list. The insertion in the queue occurs in the normal order. The first element in the queue will be the first element entered; therefore, your position is at the beginning of the queue.


Model building a queue element

To establish one of the elements of the queue, the type struct. The queue element will contain a given field and a pointer Following which must be of the same type as the element. Otherwise, it will not be able to point to the element and will allow access to the next element.

typedef struct elementoLista {       
    char *dado;       
    struct elementoLista *seguinte;       
}elemento;

To control the queue, it is best to save certain elements: the first element, the last element and the number of elements. Use another structure for this, but there is no obligation, since variables can be used.

typedef struct ListaDetectada{       
  elemento *fim;       
  int tamanho;      
} Fila;

Queue operations

Startup

Function model:

void inicialização (fila * sequência);

The procedure must be done before any other operation in the queue. The start and end hands are positioned on the NULL value and the size is 0.

Occupation:

void inicialização (Fila * sequência){       
  sequência-> início = NULL;       
  sequência->fim = NULL;       
  sequência->tamanho = 0;       
}

Inserting element in the queue

see the insertion algorithm and registration of elements:

  • Declaration of elements to be inserted
  • Memory allocation for the new element
  • Filling in the content of the data field
  • Updating the start pointer to the first element (top of the row)
  • End pointer update (will serve for insertion at the end of the row)
  • Queue size update

Function model:

int inserir (Fila * sequência, elemento * atual, char *dado);

The first image shows the start of the insertion, whose list is 1 after insertion.

In the queue, the element to be retrieved is the first to be inserted. For this, the insertion will always be done at the end of the queue. This is the normal order of insertion (1st, 2nd, 3rd, etc.).

Occupation:

int inserir (Fila * sequência, elemento * atual, char *dado){       
  elemento *novo_elemento;       
  if ((novo_elemento = (elemento *) malloc (sizeof (elemento))) == NULL)       
    return -1;       
  if ((novo_elemento-> dado = (char *) malloc (50 * sizeof (char)))       
      == NULL)       
    return -1;       
  strcpy (novo_elemento->dado, dado);       

  if(atual== NULL){       
    if(sequência->tamanho == 0)       
      sequência->fim = novo_elemento;       
    novo_elemento->seguinte = sequência->início;       
    sequência-> início = novo_elemento;       
  }else {       
    if(atual->seguinte == NULL)       
      sequência->fim = novo_elemento;       
    novo_elemento->seguinte = atual->seguinte;       
    atual->seguinte = novo_elemento;       
  }       
  sequência->tamanho++;       
  return 0;       
}

Remove queue element

To remove an element from the queue, simply delete the element to which the start pointer points. This operation does not allow to recover the data at the beginning of the queue (first die), but just remove it.

Function model:

int remover (Fila * sequência);

The function returns the value -1 in case of failure. Otherwise, the returned value will be 0.

Phases: pointer remove_elem will contain the address of the first element, the start pointer will point to the second element (after deleting the first element, the second will move to the beginning of the queue) and the size of the queue will lose one unit.

Occupation:

int remover (Fila * sequência){       
  elemento *remov_elemento;       
  if (sequência->tamanho == 0)       
    return -1;       
  remov_elemento = sequência->início;       
  sequência->início = sequência->início->seguinte;       
  free (remov_elemento->dado);       
  free (remov_elemento);       
  sequência->tamanho--;       
  return 0;       
}

Show queue

To display the entire queue, you need to position yourself at the beginning of the queue (using the start pointer). Then, using the next hand of each element, the row will be traversed from the first to the last element. The stop condition is given by the size of the queue.

Occupation:

void exibir (Fila *sequência){       
  elemento *atual;       
  int i;       
   atual = sequência->início;       

  for(i=0;i<sequência->tamanho;++i){       
    printf(" %s ", atual->dado);       
    atual = atual->seguinte;       
  }       
}

Data retrieval at the beginning of the queue

To retrieve the data at the beginning of the queue without removing it, we will use a macro which reads the data from the beginning of the queue using the start pointer.

#define fila_dado(sequência)  sequência->início->dado

Complete example

row.h

/*      fila.h       */
typedef struct elementoLista{         
char *dado;         
struct elementoLista *seguinte;       
} Elemento;       
typedef struct ListaDetectada{         
Elemento *início;  Elemento *fim;  int tamanho;       
} Fila;

/* inicialização */       
void inicialização (fila * sequência);       
/* Inserir*/       
int inserir (fila * sequência, elemento * atual, char *dado);       

/* Remover*/       
int remover (fila * sequência);       

/* FirstInFirstOut */       
#define fila_dado(sequência) 
sequência->início->dado       

/* Exibir a fila */       
void exibir (fila *sequência);

fila_function.h

/*      fila_function.h       */
void inicialização (fila * sequência){         
sequência->início = NULL;         
sequência->fim = NULL;         
sequência->tamanho = 0;       }

/* inserir (adicionar) um elemento na fila */       
int inserir (fila * sequência, elemento * atual, char *dado){         
Elemento *novo_elemento;         
if ((novo_elemento = (elemento *) malloc (sizeof (elemento))) == NULL)
return -1;         
if ((novo_elemento->dado = (char *) malloc (50 * sizeof (char))) == NULL)
return -1;         
strcpy (novo_elemento->dado, dado);         
if(atual == NULL){           
if(sequência->tamanho == 0)             
sequência->fim = novo_elemento;           
novo_elemento->seguinte = sequência->início;           
sequência-> início = novo_elemento;         
}
else 
{           
if(atual->seguinte == NULL)             
sequência->fim = novo_elemento;           
novo_elemento->seguinte = atual->seguinte;           
atual-> seguinte = novo_elemento;         }         
sequência->tamanho++;         
return 0;       
}

/* remover (eliminar) elemento da fila */       
int remover (fila * sequência){         
Elemento *remov_elemento;         
if (sequência->tamanho == 0)           
return -1;         
remov_elemento = sequência->início;         
sequência-> início = sequência->início->seguinte;         
free (remov_elemento->dado);         
free (remov_elemento);         
sequência->tamanho--;         
return 0;       
}

/* exibição da fila */       
void exibir (fila *sequência){         
Elemento *atual;         
int i;         
atual = sequência->início;         
for(i=0;i<sequência->tamanho;++i){           
printf(" %s ", atual->dado);           
atual = atual->seguinte;         
}       
}

row.c

/*      fila.c       */
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include "fila.h"
#include "fila_function.h"
int main (){          
Fila *sequência;         
char *nome;         
if ((sequência = (fila *) malloc (sizeof (fila))) == NULL)           
return -1;         
if ((nome = (char *) malloc (50 * sizeof (char))) == NULL)           
return -1;         
inicialização (sequência);         
printf ("Inserir uma palavra:");         
scanf ("%s", nome);         
inserir (sequência, sequência->fim, nome);         
printf ("A fila (%de elementos)n",sequência->tamanho);         
printf("nInício de la fila [ ");         
exibir (sequência);     

/*primeiro elemento inserido será exibido */         
printf(" ] fim de la filann");         
printf ("Inserir uma palavra:");         
scanf ("%s", nome);         
Inserir (sequência, sequência->fim, nome);         
printf ("A fila (%de elementos)n",sequência->tamanho);         
printf("nInício da fila [ ");         
exibir (sequência);      

/*primeiro elemento inserido será exibido */         
printf(" ] fim da filann");         
printf ("Inserir uma palavra:");         
scanf ("%s", nome);         
Inserir (sequência, sequência->fim, nome);         
printf ("A fila (%de elementos)n",sequência->tamanho);         
printf("nInício de la fila [ ");         
exibir (sequência);      

/*primeiro elemento inserido será exibido */         
printf(" ] fim da filann");         
printf ("nO primeiro elemento inserido (FirstInFirstOut) [ %s ] será removido",
fila_dado(sequência));         
printf ("nO primeiro elemento inserido é removidon");         
remover (sequência);              

/*remoção do primeiro elemento inserido*/         
printf ("A fila (%d elementos): n",sequência->tamanho);         
printf("nInício da fila [ ");         
exibir (sequência);         
printf(" ] fim da filann");         
return 0;       
}

See too

Lists simply linked

Double-linked lists

Circular lists

The batteries

Photo: © Everypixel.

Related Posts

Leave a Reply

Your email address will not be published. Required fields are marked *