double ended queue c with examples
Un tutorial detaliat despre coada Deque sau Double-ended în C ++. Tutorialul explică ce este Deque, operațiuni de bază, implementare și aplicații C ++ și Java:
Coada terminată dublă sau numită pur și simplu „Deque” este o versiune generalizată a cozii.
Diferența dintre Coadă și Deque este că nu urmează abordarea FIFO (First In, First Out). A doua caracteristică a Deque este că putem introduce și elimina elemente de la capetele din față sau din spate.
=> Citiți seria Easy C ++ Training
Ce veți învăța:
- Clasificare coadă dublă
- Operații tactile de bază
- și Ilustrație
- și implementare
- Aplicații
- Concluzie
- Lectură recomandată
Clasificare coadă dublă
Deque poate fi clasificat după cum urmează:
Intrare la atingere restricționată; În limită de intrare, ștergerea se poate face de la ambele capete, dar inserarea se poate face numai la capătul din spate al cozii.
Deque restricționat la ieșire: În coada restricționată la ieșire, inserarea se poate face de la ambele capete, dar ștergerea se face doar la un capăt, adică la capătul frontal al cozii.
De asemenea, putem implementa stive și cozi folosind deque.
Operații tactile de bază
Următoarele sunt operațiile de bază care pot fi efectuate pe deque.
- introduceți fața: Introduceți sau adăugați un element în partea din față a deque.
- inserare Ultima: Introduceți sau adăugați un articol în partea din spate a deque.
- deleteFront: Ștergeți sau eliminați elementul din partea din față a cozii.
- șterge ultima: Ștergeți sau eliminați elementul din spatele cozii.
- getFront: Preluează elementul frontal în deque.
- getLast: Preluează ultimul element din coadă.
- este gol: Verifică dacă deque-ul este gol.
- e plin: Verifică dacă deque-ul este plin.
și Ilustrație
Un deque gol este reprezentat după cum urmează:
cum se deschid fișiere torrentate mac
Apoi, inserăm elementul 1 în față.
Acum, introducem elementul 3 în spate.
Apoi, adăugăm elementul 5 în față și când sunt incrementate punctele frontale la 4.
Apoi, introducem elementele 7 în spate și 9 în față. Deque va arăta așa cum se arată mai jos.
Apoi, să eliminăm un element din față.
Astfel, vedem că atunci când elementele sunt inserate în față, poziția din față este decrementată în timp ce este incrementată când un element este îndepărtat. Pentru partea din spate, poziția este incrementată pentru inserare și decrementată pentru îndepărtare .
și implementare
Implementare 100 ++ touch
Putem implementa un deque în C ++ folosind matrici, precum și o listă legată. În afară de aceasta, Biblioteca de șabloane standard (STL) are o clasă „deque” care implementează toate funcțiile pentru această structură de date.
Implementarea matricei deque a fost dată mai jos. Deoarece este o coadă dublă, am folosit matricele circulare pentru implementare.
modele de cicluri de viață de dezvoltare software cascadă
#include using namespace std; #define MAX_size 10 // Maximum size of array or Dequeue // Deque class class Deque { int array(MAX_size); int front; int rear; int size; public : Deque(int size) { front = -1; rear = 0; this->size = size; } // Operations on Deque: void insertfront(int key); void insertrear(int key); void deletefront(); void deleterear(); int getFront(); int getRear(); // Check if Deque is full bool isFull()front == rear+1); // Check if Deque is empty bool isEmpty(){ return (front == -1); } }; // Insert an element at front of the deque void Deque::insertfront(int key) { if (isFull()) { cout << 'Overflow!!
' << endl; return; } // If queue is initially empty,set front=rear=0; start of deque if (front == -1) { front = 0; rear = 0; } else if (front == 0) // front is first position of queue front = size - 1 ; else // decrement front 1 position front = front-1; array(front) = key ; // insert current element into Deque } // insert element at the rear end of deque void Deque ::insertrear(int key) { if (isFull()) { cout << ' Overflow!!
' << endl; return; } // If queue is initially empty,set front=rear=0; start of deque if (front == -1) { front = 0; rear = 0; } else if (rear == size-1) // rear is at last position of queue rear = 0; else // increment rear by 1 position rear = rear+1; array(rear) = key ; // insert current element into Deque } // Delete element at front of Deque void Deque ::deletefront() { if (isEmpty()) { cout << 'Queue Underflow!!
' << endl; return ; } // Deque has only one element if (front == rear) { front = -1; rear = -1; } else // back to initial position if (front == size -1) front = 0; else // remove current front value from Deque;increment front by 1 front = front+1; } // Delete element at rear end of Deque void Deque::deleterear() { if (isEmpty()) { cout << ' Underflow!!
' << endl ; return ; } // Deque has only one element if (front == rear) { front = -1; rear = -1; } else if (rear == 0) rear = size-1; else rear = rear-1; } // retrieve front element of Deque int Deque::getFront() { if (isEmpty()) { cout << ' Underflow!!
' << endl; return -1 ; } return array(front); } // retrieve rear element of Deque int Deque::getRear() { if(isEmpty() || rear < 0) { cout << ' Underflow!!
' << endl; return -1 ; } return array(rear); } //main program int main() { Deque dq(5); cout << 'Insert element 1 at rear end
'; dq.insertrear(1); cout << 'insert element 3 at rear end
'; dq.insertrear(3); cout << 'rear element of deque ' << ' ' << dq.getRear() << endl; dq.deleterear(); cout << 'After deleterear, rear = ' << dq.getRear() << endl; cout << 'inserting element 5 at front end
'; dq.insertfront(5); cout << 'front element of deque ' << ' ' << dq.getFront() << endl; dq.deletefront(); cout << 'After deletefront, front = ' << dq.getFront() << endl; return 0; } Ieșire:
Introduceți elementul 1 la capătul din spate
introduceți elementul 3 la capătul din spate
elementul posterior al deque 3
După ștergere, spate = 1
introducând elementul 5 la capătul frontal
elementul frontal al deque 5
După deletefront, front = 1
Recontarea implementării Java
Interfața deque din Java, „java.util.Deque” este derivată din interfața „java.util.Queue”. Deque poate fi folosit ca o coadă (First In, First Out) sau ca o stivă (Last In, First Out). Aceste implementări funcționează mai repede decât lista conectată.
Mai jos este ierarhia pentru interfața Deque în Java.
Trebuie să ne amintim câteva puncte despre interfața Deque în Java:
- Implementarea nu este sigură de fir, deoarece nu există sincronizare externă.
- Deque nu acceptă concurența de mai multe fire.
- Deque implementat folosind matrice nu permite utilizarea elementelor NULL.
- Tablourile sunt permise să crească conform cerințelor, capacitatea fără restricții și suportul redimensionabil pentru matrice fiind cele mai importante două caracteristici.
Următoarele sunt diferitele metode acceptate de interfața Deque:
cum să redați fișiere .mkv
| Nu face. | Metodă | Descriere |
|---|---|---|
| 7 | iterator () | Returnează un iterator pentru deque. |
| 1 | add (element) | Adaugă un element la coadă. |
| Două | addFirst (element) | Adaugă un element în cap / față. |
| 3 | addLast (element) | Adaugă un element în coadă / spate. |
| 4 | oferta (element) | Adaugă un element la coadă; returnează o valoare booleană pentru a indica dacă inserarea a avut succes. |
| 5 | offerFirst (element) | Adaugă un element în cap; returnează o valoare booleană pentru a indica dacă inserarea a avut succes. |
| 6 | offerLast (element) | Adaugă un element la coadă; returnează o valoare booleană pentru a indica dacă inserarea a avut succes. |
| 8 | descendingIterator () | Returnează un iterator care are ordinea inversă pentru acest deque. |
| 9 | împinge (element) | Adaugă un element la capul deque. |
| 10 | pop (element) | Elimină un element din capul deque și îl returnează. |
| unsprezece | removeFirst () | Îndepărtează elementul din capul deque. |
| 12 | removeLast () | Îndepărtează elementul de la coada deque. |
| 13 | sondaj () | Preluează și elimină primul element al deque (reprezentat de capul deque); returnează NULL dacă deque-ul este gol. |
| 14 | pollFirst () | Preluează și elimină primul element al acestui deque; returnează nul dacă acest deque este gol. |
| cincisprezece | pollLast () | Preluează și elimină ultimul element al acestui deque; returnează nul dacă acest deque este gol. |
| 16 | arunca o privire() | Preluează capul (primul element al deque) cozii reprezentate de acest deque; returnează nul dacă acest deque este gol. Notă: Această operație nu elimină elementul. |
| 17 | peekFirst () | Preluează primul element al acestui deque; returnează nul dacă acest deque este gol. Notă: Această operație nu elimină elementul. |
| 18 | peekLast () | Preluează ultimul element al acestui deque sau returnează nul dacă acest deque este gol. Notă: Această operație nu elimină elementul. |
Următoarea implementare Java demonstrează diferitele operații discutate mai sus.
import java.util.*; class Main { public static void main(String() args) { Deque deque = new LinkedList (); // We can add elements to the queue in various ways deque.add(1); // add to tail deque.addFirst(3); deque.addLast(5); deque.push(7); //add to head deque.offer(9); deque.offerFirst(11); deque.offerLast(13); System.out.println('The deque : ' + deque + '
'); // Iterate through the queue elements. System.out.println('Standard Iterator'); Iterator iterator = deque.iterator(); while (iterator.hasNext()) System.out.print(' ' + iterator.next()); // Reverse order iterator Iterator reverse = deque.descendingIterator(); System.out.println('
Reverse Iterator'); while (reverse.hasNext()) System.out.print(' ' + reverse.next()); // Peek returns the head, without deleting // it from the deque System.out.println('
Peek ' + deque.peek()); System.out.println('After peek: ' + deque); // Pop returns the head, and removes it from // the deque System.out.println('
Pop ' + deque.pop()); System.out.println('After pop: ' + deque); // We can check if a specific element exists // in the deque System.out.println('
Contains element 3?: ' + deque.contains(3)); // We can remove the first / last element. deque.removeFirst(); deque.removeLast(); System.out.println('Deque after removing ' + 'first and last elements: ' + deque); } } Ieșire:
Și (11, 7, 3, 1, 5, 9, 13)
Iterator standard
11 7 3 1 5 9 13
Iterator invers
13 9 5 1 3 7 11
Peek 11
După o privire: (11, 7, 3, 1, 5, 9, 13)
Pop 11
După pop: (7, 3, 1, 5, 9, 13)
Conține elementul 3 ?: adevărat
Decupați după eliminarea primului și ultimului element: (3, 1, 5, 9)
În programul de mai sus, am folosit interfața Deque din Java și am definit un deque de elemente întregi. Apoi am efectuat diverse operații pe acest deque și am afișat rezultatele acestor operații.
Aplicații
Deque poate fi utilizat în unele dintre următoarele aplicații.
# 1) Algoritm de programare: Un algoritm de planificare, „Algoritm de planificare A-fură” implementează programarea sarcinilor pentru diferiți procesoare din sistemul multiprocesor. Această implementare folosește deque și procesorul primește primul element din deque pentru execuție.
# 2) Anulați lista activităților: În aplicațiile software, avem multe acțiuni. Unul este „anula”. Când am efectuat de multe ori acțiunea de anulare, toate aceste acțiuni sunt stocate într-o listă. Această listă este menținută ca un deque, astfel încât să putem adăuga / elimina cu ușurință intrări din orice capăt.
# 3) Eliminați intrările după ceva timp: Aplicațiile reîmprospătează intrările din lista lor, cum ar fi aplicațiile care enumeră intrările de stoc etc. Aceste aplicații elimină intrările după un timp și, de asemenea, inserează intrări noi. Acest lucru se face folosind un deque.
Concluzie
Deque este o coadă cu două capete care ne permite să adăugăm / eliminăm elemente de la ambele capete, adică din față și din spate, ale cozii. Deque poate fi implementat folosind tablouri sau liste legate. Cu toate acestea, avem și o clasă Standard Template Library (STL) care implementează diferitele operațiuni ale Deque.
În Java, avem o interfață Deque care este moștenită de la interfața cozii pentru a implementa Deque. În afară de operațiunile standard de bază ale Deque, această interfață acceptă diverse alte operații care pot fi efectuate pe Deque.
Deque este utilizat în general pentru aplicații care necesită adăugarea / îndepărtarea de elemente de la ambele capete. Este, de asemenea, utilizat în cea mai mare parte în programarea procesoarelor din sistemele cu mai multe procesoare.
=> Verificați seria completă de formare C ++