In questo articolo discuteremo della coda a doppia estremità o deque. Dovremmo prima vedere una breve descrizione della coda.
Cos'è una coda?
Una coda è una struttura dati in cui ciò che arriva per primo uscirà per primo e segue la politica FIFO (First-In-First-Out). L'inserimento nella coda avviene da un'estremità denominata estremità posteriore o il coda, mentre la cancellazione viene eseguita da un'altra estremità nota come fine frontale o il Testa della coda.
bloccare gli annunci su YouTube Android
L'esempio reale di coda è la coda per i biglietti fuori da una sala cinematografica, dove la persona che entra per prima in coda riceve per prima il biglietto e la persona che entra per ultima in coda riceve il biglietto per ultima.
Cos'è una Deque (o coda a doppia estremità)
La deque sta per Double Ended Queue. Deque è una struttura dati lineare in cui le operazioni di inserimento ed eliminazione vengono eseguite da entrambe le estremità. Possiamo dire che la deque è una versione generalizzata della coda.
Sebbene l'inserimento e l'eliminazione in una deque possano essere eseguiti su entrambe le estremità, non segue la regola FIFO. La rappresentazione di una deque è data come segue:
Tipi di deque
Esistono due tipi di deque:
- Ingresso coda limitata
- Coda limitata in uscita
Ingresso coda limitata
Nella coda con restrizioni di input, l'operazione di inserimento può essere eseguita solo da un'estremità, mentre l'eliminazione può essere eseguita da entrambe le estremità.
Coda di output limitata
Nella coda con restrizioni di output, l'operazione di eliminazione può essere eseguita solo da un'estremità, mentre l'inserimento può essere eseguito da entrambe le estremità.
Operazioni eseguite su deque
Sono le seguenti operazioni che possono essere applicate su una deque:
- Inserimento sul davanti
- Inserimento sul retro
- Cancellazione al fronte
- Cancellazione al retro
Possiamo anche eseguire operazioni di visualizzazione nella deque insieme alle operazioni elencate sopra. Attraverso l'operazione peek possiamo ottenere gli elementi anteriori e posteriori della deque. Pertanto, oltre alle operazioni di cui sopra, in deque sono supportate anche le seguenti operazioni:
sommatore pieno
- Prendi l'oggetto in primo piano dalla deque
- Prendi l'oggetto posteriore dalla deque
- Controlla se la deque è piena oppure no
- Controlla se la deque è vuota o meno
Ora capiamo l'operazione eseguita su deque utilizzando un esempio.
Inserimento nella parte anteriore
In questa operazione l'elemento viene inserito dal front-end della coda. Prima di eseguire l'operazione dobbiamo verificare se la coda è piena oppure no. Se la coda non è piena, l'elemento può essere inserito dal front-end utilizzando le condizioni seguenti:
- Se la coda è vuota, sia posterior che front vengono inizializzati con 0. Ora entrambi punteranno al primo elemento.
- Altrimenti verificare la posizione del frontale se il frontale è inferiore a 1 (front<1), then reinitialize it by front = n - 1 , ovvero l'ultimo indice dell'array.
Inserimento nella parte posteriore
In questa operazione l'elemento viene inserito dal fondo della coda. Prima di eseguire l'operazione dobbiamo verificare nuovamente se la coda è piena oppure no. Se la coda non è piena, l'elemento può essere inserito dalla parte posteriore utilizzando le seguenti condizioni:
- Se la coda è vuota, sia posterior che front vengono inizializzati con 0. Ora entrambi punteranno al primo elemento.
- Altrimenti, incrementa la parte posteriore di 1. Se la parte posteriore è all'ultimo indice (o dimensione - 1), invece di aumentarla di 1, dobbiamo renderla uguale a 0.
Cancellazione nella parte anteriore
In questa operazione l'elemento viene eliminato dal front-end della coda. Prima di eseguire l'operazione dobbiamo verificare se la coda è vuota oppure no.
cos'è Maven
Se la coda è vuota, cioè front = -1, è la condizione di underflow e non possiamo eseguire l'eliminazione. Se la coda non è piena, l'elemento può essere inserito dal front-end utilizzando le condizioni seguenti:
Se la deque ha un solo elemento, impostare posterior = -1 e front = -1.
Altrimenti se davanti è alla fine (ciò significa davanti = taglia - 1), imposta davanti = 0.
durata di Java
Altrimenti incrementa la parte anteriore di 1 (ovvero, anteriore = anteriore + 1).
Eliminazione nella parte posteriore
In questa operazione, l'elemento viene eliminato dalla parte posteriore della coda. Prima di eseguire l'operazione dobbiamo verificare se la coda è vuota oppure no.
Se la coda è vuota, cioè front = -1, è la condizione di underflow e non possiamo eseguire l'eliminazione.
Se la deque ha un solo elemento, impostare posterior = -1 e front = -1.
Se posteriore = 0 (la parte posteriore è davanti), impostare posteriore = n - 1.
Altrimenti, decrementa la parte posteriore di 1 (o, parte posteriore = parte posteriore -1).
Controlla vuoto
Questa operazione viene eseguita per verificare se la deque è vuota o meno. Se front = -1 significa che la deque è vuota.
Controlla pieno
Questa operazione viene eseguita per verificare se la deque è piena o meno. Se anteriore = posteriore + 1, oppure anteriore = 0 e posteriore = n - 1 significa che la deque è piena.
La complessità temporale di tutte le operazioni della deque di cui sopra è O(1), cioè costante.
Applicazioni della deque
- Deque può essere utilizzato sia come stack che come coda, poiché supporta entrambe le operazioni.
- Deque può essere usato come controllo palindromo significa che se leggessimo la stringa da entrambe le estremità, la stringa sarebbe la stessa.
Attuazione della deque
Ora vediamo l'implementazione di deque nel linguaggio di programmazione C.
vikas divyakirti
#include #define size 5 int deque[size]; int f = -1, r = -1; // insert_front function will insert the value from the front void insert_front(int x) { if((f==0 && r==size-1) || (f==r+1)) { printf('Overflow'); } else if((f==-1) && (r==-1)) { f=r=0; deque[f]=x; } else if(f==0) { f=size-1; deque[f]=x; } else { f=f-1; deque[f]=x; } } // insert_rear function will insert the value from the rear void insert_rear(int x) { if((f==0 && r==size-1) || (f==r+1)) { printf('Overflow'); } else if((f==-1) && (r==-1)) { r=0; deque[r]=x; } else if(r==size-1) { r=0; deque[r]=x; } else { r++; deque[r]=x; } } // display function prints all the value of deque. void display() { int i=f; printf('
Elements in a deque are: '); while(i!=r) { printf('%d ',deque[i]); i=(i+1)%size; } printf('%d',deque[r]); } // getfront function retrieves the first value of the deque. void getfront() { if((f==-1) && (r==-1)) { printf('Deque is empty'); } else { printf('
The value of the element at front is: %d', deque[f]); } } // getrear function retrieves the last value of the deque. void getrear() { if((f==-1) && (r==-1)) { printf('Deque is empty'); } else { printf('
The value of the element at rear is %d', deque[r]); } } // delete_front() function deletes the element from the front void delete_front() { if((f==-1) && (r==-1)) { printf('Deque is empty'); } else if(f==r) { printf('
The deleted element is %d', deque[f]); f=-1; r=-1; } else if(f==(size-1)) { printf('
The deleted element is %d', deque[f]); f=0; } else { printf('
The deleted element is %d', deque[f]); f=f+1; } } // delete_rear() function deletes the element from the rear void delete_rear() { if((f==-1) && (r==-1)) { printf('Deque is empty'); } else if(f==r) { printf('
The deleted element is %d', deque[r]); f=-1; r=-1; } else if(r==0) { printf('
The deleted element is %d', deque[r]); r=size-1; } else { printf('
The deleted element is %d', deque[r]); r=r-1; } } int main() { insert_front(20); insert_front(10); insert_rear(30); insert_rear(50); insert_rear(80); display(); // Calling the display function to retrieve the values of deque getfront(); // Retrieve the value at front-end getrear(); // Retrieve the value at rear-end delete_front(); delete_rear(); display(); // calling display function to retrieve values after deletion return 0; } Produzione:
Quindi, questo è tutto sull'articolo. Spero che l'articolo ti sarà utile e informativo.