data-structures
Queue

Introduction à la file d'attente

La file d'attente est une structure de données FIFO (premier entré, premier sorti), c'est-à-dire que le premier élément ajouté à la file d'attente sera le premier élément supprimé ("premier sorti").

Prenons l'exemple des clients qui attendent d'être aidés. Alice, Bob et Dan sont tous au supermarché. Alice est prête à payer, alors elle s'approche de la caissière. Alice est maintenant dans la file d'attente. Elle est la seule personne dans la file d'attente, alors elle est à la fois à l'avant et à l'arrière.

Maintenant, la file d'attente ressemble à ceci:

              |-------|
              | Alice | cashier
              |-------|
                ▲   ▲
back of queue ──┘   └── front of queue

Maintenant, Bob et Dan s'approchent du caissier. Ils sont ajoutés à la file d'attente. Alice est toujours à l'avant et Dan est à l'arrière:

              |-------||-------||-------|
              |  Dan  ||  Bob  || Alice | cashier
              |-------||-------||-------|
                ▲                     ▲
back of queue ──┘                     └── front of queue

L'ajout d'une personne à la file d'attente est l'opération de mise en file d'attente. Alice, Bob et Dan ont été mis en file d'attente. Comme le caissier aide chaque client, il sera retiré de la file d'attente. Ceci est l'opération de la file d'attente. Les clients, qui représentent les éléments de données dans notre file d'attente, sont retirés de la file d'attente. Cela signifie que le premier client qui a approché le caissier a été le premier client à être aidé (FIFO).

Implémentation de la file d'attente à l'aide d'un tableau.

La file d'attente suit le FIFO tel que mentionné dans l'introduction. Cinq opérations majeures:

1. Enqueue (x): pousse x à l'arrière de la file d'attente.
2. Dequeue (): fait apparaître un élément à l'avant de la file d'attente.
3. isEmpty (): Recherche si la file d'attente est vide ou non.
4. isFull (): Recherche si la file d'attente est pleine ou non.
5. frontValue (): renvoie la valeur frontale de la file d'attente.

Toutes les opérations sont constantes O (1) temps.

Code :

#include<stdio.h>

#define MAX 4

int front = -1;
int rear = -1;
int a[MAX];

bool isFull() {
  if(rear == MAX-1)
    return true;
  else
    return false;    
}

bool isEmpty() {
  if(rear == -1 && front==-1)
    return true;
  else
    return false;    
}

void enqueue(int data) {
  if (isFull()){
    printf("Queue is full\n");
    return;
  } else if(isEmpty()) {
    front = rear =0;
  } else {
    rear = rear + 1;
    a[rear] = data;      
  }
}
    
void deque(){
  if(isEmpty()){
    printf("Queue is empty\n");
    return;
  } else if(front == rear) {
    front =-1;
    rear =-1;
  } else {
    front = front + 1;
  }
}
    
void print(){
  printf("Elements in Queue are\n");  
  for(int i = front;i<=rear;i++){
    printf("%d ",a[i]);
  }
  printf("\n");
}

int frontValue(){  
  printf("The front element after set of enqueue and dequeue is %d\n", a[front]);
}

int main(){
  deque();     // Queue is empty message will be thrown
  enqueue(10);
  print();
  enqueue(20);
  print();
  enqueue(30);
  print();
  enqueue(40);
  frontValue();
  print();
  enqueue(50);
  frontValue();
  deque();
  deque();
  enqueue(50);
  frontValue();
  print();                    
  return 0;
}

Mise en place d'une file d'attente circulaire

La mémoire est organisée efficacement dans une file d'attente circulaire par rapport à une file d'attente linéaire.

En file d'attente linéaire:

En file d'attente circulaire:

Les espaces restants peuvent être utilisés:

Code pour qu'il fasse pareil:

#include<stdio.h>
#define MAX 10000
int front = -1;
int rear = -1;
int a[MAX]; 


bool isFull() {
  if((rear+1) % MAX == front)
    return true;
  else
    return false;    
}

bool isEmpty() {
  if(rear == -1 && front==-1)
    return true;
  else
    return false;    
}

void enqueue(int data) {
  if (isFull()){
    printf("Queue is full\n");
    return;
  } else if(isEmpty()) {
    front = rear = 0;
  } else {
    rear = (rear+1) % MAX;
    a[rear] = data;
  }
}

void deque() {
  if(isEmpty()){
    printf("Queue is empty\n");
    return;
  } else if(front == rear) {
    front =-1;
    rear =-1;
  } else {
    front = (front+1) % MAX;
  }
}

int frontValue() {
  return(a[front]);
}

int main() {   
  deque(); 
  enqueue(10);
  enqueue(20);
  enqueue(30);       
  enqueue(40);
  enqueue(50);
  frontValue();
  return 0;
}

Toutes les opérations ont une complexité temporelle O (1).

Représentation par liste liée de la file d'attente

La représentation des listes liées est plus efficace en termes de gestion de la mémoire.

Code pour afficher la mise en file d'attente et le retrait dans une file d'attente à l'aide de Linklist en heure O (1).

#include<stdio.h>
#include<malloc.h>

struct node{
    int data;
    node* next;
};

node* front = NULL;
node* rear = NULL;

void enqueue(int data){      //adds element to end
    
    struct node* temp = (struct node*)malloc(sizeof(struct node*));
    temp->data = data;
    temp->next =NULL;
    
    if(front== NULL && rear == NULL){
        front = rear = temp;
        return;
    }
    rear->next = temp;
    rear= temp;
}

void deque(){     //removes element from front
    node* temp = front;
    
    if(front== NULL && rear == NULL){
        return;
    }
    else if (front==rear){
        front =rear = NULL;
    }
    else
    front= front ->next;
    
    free(temp);
}

void print(){
    node* temp = front;
    
    for(; temp != rear; temp=temp->next){
        printf("%d ",temp->data);
    }
    //for printing the rear element
    
        printf("%d ",temp->data);
    printf("\n");
}



int main(){
    
    enqueue(20);
    enqueue(50);
        enqueue(70);
        printf("After set of enques\n");
        print();
        
        deque();
        printf("After 1 deque\n");    
        print();
        
        return 0;    
    
    
}