data-structures
Coda

Introduzione alla coda

La coda è una struttura di dati FIFO (first-in, first-out), ovvero il primo elemento aggiunto alla coda sarà il primo elemento rimosso ("first out").

Prendiamo in considerazione l'esempio dei clienti che aspettano di essere aiutati. Alice, Bob e Dan sono tutti al supermercato. Alice è pronta a pagare, quindi si avvicina alla cassa. Alice è ora in coda. È l'unica persona in coda, quindi è sia nella parte anteriore che nella parte posteriore.

Ora, la coda ha questo aspetto:

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

Ora Bob e poi Dan si avvicinano al cassiere. Sono aggiunti alla coda. Alice è ancora al fronte e Dan è sul retro:

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

L'aggiunta di una persona alla coda è l'operazione di accodamento. Alice, Bob e Dan sono stati accodati. Quando il cassiere aiuta ogni cliente, verrà rimosso dalla coda. Questa è l'operazione di rimozione. I clienti, che rappresentano gli elementi di dati nella nostra coda, vengono esclusi dalla coda della coda. Ciò significa che il primo cliente che si è avvicinato al cassiere è stato il primo cliente ad essere aiutato (FIFO).

Implementazione della coda usando l'array.

La coda segue FIFO come menzionato nell'introduzione. Cinque operazioni principali:

1. Enqueue (x): spinge x sul retro della coda.
2. Dequeue (): apre un elemento dalla parte anteriore della coda.
3. isEmpty (): trova se la coda è vuota o meno.
4. isFull (): trova se la coda è piena o meno.
5. frontValue (): restituisce il valore anteriore della coda.

Tutte le operazioni sono costanti O (1) tempo.

Codice :

#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;
}

Implementazione di una coda circolare

La memoria è organizzata in modo efficiente in una coda circolare rispetto alla coda lineare.

In coda lineare:

In coda circolare:

Gli spazi rimanenti possono essere utilizzati:

Codice per fare lo stesso:

#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;
}

Tutte le operazioni hanno O (1) complessità temporale.

Rappresentazione della lista collegata della coda

La rappresentazione della lista collegata è più efficiente in termini di gestione della memoria.

Codice per mostrare enqueue e deque in una coda usando Linklist in tempo 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;    
    
    
}