În acest articol, vom discuta despre coada dublă sau deque. Ar trebui să vedem mai întâi o scurtă descriere a cozii.
Ce este o coadă?
O coadă este o structură de date în care ceea ce vine primul va ieși primul și urmează politica FIFO (First-In-First-Out). Inserarea în coadă se face de la un capăt cunoscut sub numele de fundătură sau coadă, întrucât ștergerea se face dintr-un alt capăt cunoscut sub numele de în față sau cap a cozii.
scaner scan java
Exemplul real de coadă este coada de bilete din afara unei săli de cinema, unde persoana care intră prima în coadă primește primul bilet, iar persoana care intră ultima în coadă primește biletul în cele din urmă.
Ce este Deque (sau coadă dublă)
Deque înseamnă coadă dublă. Deque este o structură de date liniară în care operațiunile de inserare și ștergere sunt efectuate de la ambele capete. Putem spune că deque este o versiune generalizată a cozii.
Deși inserarea și ștergerea într-un deque pot fi efectuate la ambele capete, nu respectă regula FIFO. Reprezentarea unui deque este dată după cum urmează -
Tipuri de deque
Există două tipuri de deque -
- Intrare coadă restricționată
- Ieșire coadă restricționată
Coadă restricționată de intrare
În coada restricționată de intrare, operația de inserare poate fi efectuată la un singur capăt, în timp ce ștergerea poate fi efectuată de la ambele capete.
Coadă de ieșire restricționată
În coada restricționată de ieșire, operația de ștergere poate fi efectuată la un singur capăt, în timp ce inserarea poate fi efectuată de la ambele capete.
Operatii efectuate pe deque
Există următoarele operații care pot fi aplicate pe un deque -
- Inserare in fata
- Inserare in spate
- Ștergere în față
- Ștergere în spate
Putem efectua și operațiuni peek în deque împreună cu operațiunile enumerate mai sus. Prin operarea peek, putem obține elementele din față și din spate ale deque-ului. Deci, pe lângă operațiunile de mai sus, următoarele operațiuni sunt, de asemenea, acceptate în deque -
10 din 1 milion
- Ia elementul din față de la deque
- Ia elementul din spate de la deque
- Verificați dacă deque-ul este plin sau nu
- Verifică dacă deque-ul este gol sau nu
Acum, să înțelegem operația efectuată pe deque folosind un exemplu.
Inserare la capătul din față
În această operațiune, elementul este introdus din partea din față a cozii. Înainte de a implementa operația, trebuie mai întâi să verificăm dacă coada este plină sau nu. Dacă coada nu este plină, atunci elementul poate fi introdus din partea din față utilizând condițiile de mai jos -
- Dacă coada este goală, atât din spate, cât și din față sunt inițializate cu 0. Acum, ambele vor indica primul element.
- În caz contrar, verificați poziția față dacă partea frontală este mai mică de 1 (față<1), then reinitialize it by front = n - 1, adică ultimul indice al matricei.
Introducere la capătul din spate
În această operație, elementul este introdus din capătul din spate al cozii. Înainte de a implementa operația, trebuie mai întâi să verificăm din nou dacă coada este plină sau nu. Dacă coada nu este plină, atunci elementul poate fi introdus din partea din spate utilizând condițiile de mai jos -
ciclul de viață sdlc
- Dacă coada este goală, atât din spate, cât și din față sunt inițializate cu 0. Acum, ambele vor indica primul element.
- În caz contrar, creșteți spatele cu 1. Dacă spatele este la ultimul indice (sau dimensiunea - 1), atunci în loc să o creștem cu 1, trebuie să o facem egală cu 0.
Ștergere în partea din față
În această operațiune, elementul este șters din partea frontală a cozii. Înainte de a implementa operația, trebuie mai întâi să verificăm dacă coada este goală sau nu.
Dacă coada este goală, adică front = -1, este condiția de underflow și nu putem efectua ștergerea. Dacă coada nu este plină, atunci elementul poate fi introdus din partea din față utilizând condițiile de mai jos -
Dacă deque are un singur element, setați spate = -1 și față = -1.
Altfel, dacă față este la capăt (adică față = dimensiune - 1), setați față = 0.
Mark Zuckerberg educația
În caz contrar, creșteți partea din față cu 1, (adică față = față + 1).
Ștergere la capătul din spate
În această operațiune, elementul este șters din partea din spate a cozii. Înainte de a implementa operația, trebuie mai întâi să verificăm dacă coada este goală sau nu.
Dacă coada este goală, adică front = -1, este condiția de underflow și nu putem efectua ștergerea.
Dacă deque are un singur element, setați spate = -1 și față = -1.
Dacă spate = 0 (spate este în față), atunci setați spate = n - 1.
În caz contrar, reduceți partea din spate cu 1 (sau, spate = spate -1).
Verificați gol
Această operație este efectuată pentru a verifica dacă deque-ul este gol sau nu. Dacă front = -1, înseamnă că deque-ul este gol.
Verificați complet
Această operație este efectuată pentru a verifica dacă deque-ul este plin sau nu. Dacă față = spate + 1, sau față = 0 și spate = n - 1 înseamnă că deque-ul este plin.
Complexitatea de timp a tuturor operațiilor de mai sus ale deque este O(1), adică constantă.
Aplicații ale deque
- Deque poate fi folosit atât ca stivă, cât și ca coadă, deoarece acceptă ambele operațiuni.
- Deque poate fi folosit ca un verificator de palindrom înseamnă că dacă citim șirul de la ambele capete, șirul ar fi același.
Implementarea deque
Acum, să vedem implementarea deque în limbajul de programare C.
cate orase SUA
#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; } Ieșire:
Deci, asta e totul despre articol. Sper că articolul vă va fi util și informativ.