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 .