Struttura dei dati e algoritmi - Coda

La coda è una struttura dati astratta, in qualche modo simile a Stack. A differenza degli stack, una coda è aperta a entrambe le estremità. Un'estremità viene sempre utilizzata per inserire dati (accodamento) e l'altra viene utilizzata per rimuovere dati (rimozione dalla coda). La coda segue la metodologia First-In-First-Out, ovvero si accederà per primo all'elemento di dati memorizzato per primo.

Un esempio reale di coda può essere una strada a senso unico a una corsia, dove il veicolo entra per primo, esce per primo. Altri esempi del mondo reale possono essere visti come le code alle biglietterie e alle fermate degli autobus.

Rappresentazione in coda

Poiché ora comprendiamo che in coda, accediamo a entrambe le estremità per motivi diversi. Il diagramma seguente riportato di seguito cerca di spiegare la rappresentazione della coda come struttura dati:

Come negli stack, una coda può anche essere implementata utilizzando array, elenchi collegati, puntatori e strutture. Per semplicità, implementeremo le code utilizzando un array unidimensionale.

Operazioni di base

Le operazioni di coda possono comportare l'inizializzazione o la definizione della coda, il suo utilizzo e quindi la sua cancellazione completa dalla memoria. Qui proveremo a capire le operazioni di base associate alle code:

  • enqueue() - aggiungi (archivia) un elemento alla coda.

  • dequeue() - rimuovere (accedere) un elemento dalla coda.

Sono necessarie poche altre funzioni per rendere efficiente l'operazione di coda sopra menzionata. Questi sono -

  • peek() - Ottiene l'elemento all'inizio della coda senza rimuoverlo.

  • isfull() - Controlla se la coda è piena.

  • isempty() - Controlla se la coda è vuota.

In coda, rimuoviamo sempre dalla coda (o accediamo) i dati, indicati da front puntatore e mentre accodiamo (o memorizziamo) i dati nella coda ci aiutiamo rear puntatore.

Impariamo prima le funzioni di supporto di una coda:

sbirciare()

Questa funzione aiuta a vedere i dati in frontdella coda. L'algoritmo della funzione peek () è il seguente:

Algorithm

begin procedure peek
   return queue[front]
end procedure

Implementazione della funzione peek () nel linguaggio di programmazione C -

Example

int peek() {
   return queue[front];
}

è pieno()

Poiché stiamo usando un array a dimensione singola per implementare la coda, controlliamo semplicemente che il puntatore posteriore raggiunga MAXSIZE per determinare che la coda è piena. Nel caso in cui manteniamo la coda in una lista collegata circolare, l'algoritmo sarà diverso. Algoritmo della funzione isfull () -

Algorithm

begin procedure isfull

   if rear equals to MAXSIZE
      return true
   else
      return false
   endif
   
end procedure

Implementazione della funzione isfull () nel linguaggio di programmazione C -

Example

bool isfull() {
   if(rear == MAXSIZE - 1)
      return true;
   else
      return false;
}

è vuoto()

Algoritmo della funzione isempty () -

Algorithm

begin procedure isempty

   if front is less than MIN  OR front is greater than rear
      return true
   else
      return false
   endif
   
end procedure

Se il valore di front è minore di MIN o 0, indica che la coda non è ancora inizializzata, quindi vuota.

Ecco il codice di programmazione C -

Example

bool isempty() {
   if(front < 0 || front > rear) 
      return true;
   else
      return false;
}

Operazione di accodamento

Le code mantengono due puntatori dati, front e rear. Pertanto, le sue operazioni sono relativamente difficili da implementare rispetto a quelle degli stack.

I seguenti passaggi dovrebbero essere eseguiti per accodare (inserire) i dati in una coda:

  • Step 1 - Controlla se la coda è piena.

  • Step 2 - Se la coda è piena, produce un errore di overflow ed esce.

  • Step 3 - Se la coda non è piena, incrementare rear puntatore per indicare il successivo spazio vuoto.

  • Step 4 - Aggiungi elemento dati alla posizione della coda, dove punta la parte posteriore.

  • Step 5 - restituire il successo.

A volte, controlliamo anche se una coda è inizializzata o meno, per gestire eventuali situazioni impreviste.

Algoritmo per l'operazione di accodamento

procedure enqueue(data)      
   
   if queue is full
      return overflow
   endif
   
   rear ← rear + 1
   queue[rear] ← data
   return true
   
end procedure

Implementazione di enqueue () nel linguaggio di programmazione C -

Example

int enqueue(int data)      
   if(isfull())
      return 0;
   
   rear = rear + 1;
   queue[rear] = data;
   
   return 1;
end procedure

Operazione di rimozione dalla coda

L'accesso ai dati dalla coda è un processo di due attività: accedere ai dati dove frontsta puntando e rimuovere i dati dopo l'accesso. Per eseguire i passaggi seguentidequeue operazione -

  • Step 1 - Controlla se la coda è vuota.

  • Step 2 - Se la coda è vuota, produce un errore di underflow ed esce.

  • Step 3 - Se la coda non è vuota, accedere ai dati dove front sta indicando.

  • Step 4 - Incremento front puntatore per puntare al successivo elemento di dati disponibile.

  • Step 5 - Restituire il successo.

Algoritmo per l'operazione di rimozione dalla coda

procedure dequeue
   
   if queue is empty
      return underflow
   end if

   data = queue[front]
   front ← front + 1
   return true

end procedure

Implementazione di dequeue () nel linguaggio di programmazione C -

Example

int dequeue() {
   if(isempty())
      return 0;

   int data = queue[front];
   front = front + 1;

   return data;
}

Per un programma Queue completo in linguaggio di programmazione C, fare clic qui .