Menu

Oboustranný front (Deque) v C ++ s príkladmi

  • Hlavná
  • Iné
  • Oboustranný front (Deque) v C ++ s príkladmi

double ended queue c with examples

Vyskúšajte Náš Nástroj Na Odstránenie Problémov

Podrobný výukový program pre fronty Deque alebo Double-End v C ++. Výukový program vysvetľuje, čo je Deque, základné operácie, implementácia a aplikácie v C ++ a Java:

Dvojitý koniec frontu alebo jednoducho „Deque“ je zovšeobecnená verzia frontu.

Rozdiel medzi frontom a deque je v tom, že sa neriadi prístupom FIFO (prvý vstup, prvý výstup). Druhou vlastnosťou Deque je, že môžeme vkladať a vyberať prvky z predných aj zadných koncov.

=> Prečítajte si sériu školení Easy C ++

Oboustranný front (Deque) v C ++

Čo sa dozviete:

Klasifikácia dvojitého konca frontu

Deque možno klasifikovať nasledovne:

Vstup s obmedzeným dotykom; Pri vstupe s obmedzením je možné odstránenie vykonať z obidvoch koncov, ale vloženie je možné vykonať iba na zadný koniec frontu.

Deque s obmedzením výstupu: Vo fronte s obmedzením výstupu je možné vkladanie vykonať z oboch koncov, ale vymazanie sa vykoná iba na jednom konci, t. J. Prednom konci frontu.

Môžeme tiež implementovať stohy a fronty pomocou deque.

Základné dotykové operácie

Nasledujú základné operácie, ktoré je možné vykonať pri deque.

  • vložiť predok: Vložte alebo pridajte položku na začiatok dekády.
  • insertLast: Vložte alebo pridajte položku na koniec dekády.
  • deleteFront: Odstráňte alebo odstráňte položku z prednej časti frontu.
  • odstrániť ako posledné: Odstráňte alebo odstráňte položku zo zadnej časti frontu.
  • getFront: Načíta predný predmet v deque.
  • getLast: Načíta poslednú položku vo fronte.
  • je prázdny: Skontroluje, či je štít prázdny.
  • je plný: Skontroluje, či je dekáda plná.

a ilustrácia

Prázdny deque je znázornený takto:

Spätné prepočítanie

najlepší bezplatný prevodník súborov youtube na mp3

Ďalej vložíme prvok 1 spredu.

Vložte prvok 1 spredu

Teraz vložíme prvok 3 zozadu.

Vložte prvok 3 zozadu

Ďalej pridáme prvok 5 na predok a po zvýšení predné body na 4.

Prvok 5 smerom dopredu

Potom vložíme prvky 7 vzadu a 9 spredu. Deque bude vyzerať, ako je uvedené nižšie.

prvky 7 vzadu a 9 vpredu

Ďalej odstránime prvok spredu.

Odstráňte prvok spredu

Vidíme teda, že keď sú prvky vložené spredu, predná poloha je zmenšená, zatiaľ čo sa zvyšuje, keď je prvok odstránený. Pri zadnom konci je poloha zväčšená pre vloženie a zmenšená pre vybratie .

a implementácia

100 ++ dotyková implementácia

Môžeme implementovať deque v C ++ pomocou polí ako aj prepojeného zoznamu. Okrem toho má Štandardná knižnica šablón (STL) triedu „deque“, ktorá implementuje všetky funkcie pre túto dátovú štruktúru.

Implementácia poľa deque bola uvedená nižšie. Pretože ide o front s obojstranným využitím, na implementáciu sme použili kruhové polia.

kedy by sa malo vykonať regresné testovanie
#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; }

Výkon:

Vložte prvok 1 na zadný koniec

vložte prvok 3 na zadnom konci

zadný prvok deque 3

Po uplynutí času vzadu = 1

vkladací prvok 5 na prednom konci

predný prvok deque 5

Po odstránení spredu, spredu = 1

a výstup

Prepočítanie implementácie Java

Deque rozhranie v Jave „java.util.Deque“ je odvodené z rozhrania „java.util.Queue“. Deque možno použiť ako front (prvý vstup, prvý výstup) alebo stoh (posledný vstup, prvý výstup). Tieto implementácie fungujú rýchlejšie ako prepojený zoznam.

Ďalej je uvedená hierarchia rozhrania Deque v Jave.

Hierarchia pre rozhranie Deque v Jave

Musíme si spomenúť na niekoľko bodov o rozhraní Deque v Jave:

  • Implementácia nie je bezpečná pre vlákna, pretože neexistuje žiadna externá synchronizácia.
  • Deque nepodporuje súbežnosť viacerými vláknami.
  • Dequeho implementácia pomocou polí neumožňuje použitie prvkov NULL.
  • Polia sa môžu zväčšovať podľa požiadaviek, dvoma najdôležitejšími vlastnosťami sú kapacita bez obmedzení a podpora zmeniteľného poľa.

Nasledujú rôzne metódy podporované rozhraním Deque:

najlepší program na otváranie súborov XML
Nie.MetódaPopis
7iterátor ()Vráti iterátor deque.
1pridať (prvok)Pridá prvok do chvosta.
dvaaddFirst (prvok)Pridá prvok k hlave / predku.
3addLast (prvok)Pridáva prvok do chvosta / zozadu.
4ponuka (prvok)Pridá prvok do chvosta; vráti boolovskú hodnotu označujúcu, či bolo vloženie úspešné.
5offerFirst (prvok)Pridá prvok do hlavy; vráti boolovskú hodnotu označujúcu, či bolo vloženie úspešné.
6offerLast (prvok)Pridá prvok do chvosta; vráti boolovskú hodnotu označujúcu, či bolo vloženie úspešné.
8descendingIterator ()Vráti iterátor, ktorý má opačné poradie pre tento deque.
9push (prvok)Pridá prvok do hlavy deque.
10pop (prvok)Odstráni prvok z hlavy deque a vráti ho.
jedenásťremoveFirst ()Odstráni prvok v čele dekády.
12removeLast ()Odstráni prvok na konci chvosta dekády.
13anketa ()Načíta a odstráni prvý prvok deque (predstavovaný hlavičkou deque); vráti NULL, ak je deque prázdny.
14pollFirst ()Načíta a odstráni prvý prvok tohto deque; vráti null, ak je tento deque prázdny.
pätnásťpollLast ()Načíta a odstráni posledný prvok tohto deque; vráti null, ak je tento deque prázdny.
16nahliadnuť ()Načíta hlavu (prvý prvok deque) frontu predstavovaného týmto deque; vráti null, ak je tento deque prázdny.
Poznámka: Táto operácia neodstráni prvok.
17peekFirst ()Načíta prvý prvok tohto deque; vráti null, ak je tento deque prázdny.
Poznámka: Táto operácia neodstráni prvok.
18peekLast ()Načíta posledný prvok tohto deque alebo vráti null, ak je tento deque prázdny.
Poznámka: Táto operácia neodstráni prvok.

Nasledujúca implementácia Java demonštruje rôzne operácie diskutované vyššie.

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); } }

Výkon:

A (11, 7, 3, 1, 5, 9, 13)

Štandardný iterátor
11 7 3 1 5 9 13
Reverzný iterátor
13 9 5 1 3 7 11

Nakuknite 11.
Po nahliadnutí: (11, 7, 3, 1, 5, 9, 13)

Pop
Po pop: (7, 3, 1, 5, 9, 13)

Obsahuje prvok 3 ?: pravda

Deque po odstránení prvého a posledného prvku: (3, 1, 5, 9)

Deque Java Output

Vo vyššie uvedenom programe sme použili rozhranie Deque Java a definovali sme deque celočíselných prvkov. Potom sme na tomto deque vykonali rôzne operácie a na výstupe sa zobrazia výsledky týchto operácií.

Aplikácie

Deque možno použiť v niektorých z nasledujúcich aplikácií.

# 1) Algoritmus plánovania: Algoritmus plánovania, „Algoritmus plánovania A-steal“, implementuje plánovanie úloh pre rôzne procesory v systéme s viacerými procesormi. Táto implementácia využíva deque a procesor dostane prvý prvok z deque na vykonanie.

# 2) Vrátiť späť zoznam aktivít: V softvérových aplikáciách máme veľa akcií. Jeden je „späť“. Ak sme akciu vrátenia vykonali viackrát, všetky tieto akcie sa uložia do zoznamu. Tento zoznam je vedený ako prehľad, aby sme mohli ľahko pridávať a odstraňovať položky z ktoréhokoľvek konca.

# 3) Odstrániť záznamy po nejakom čase: Aplikácie obnovujú položky v ich zozname, ako sú aplikácie so zoznamom skladových položiek atď. Tieto aplikácie po určitom čase položky odstránia a tiež vložia nové položky. To sa deje pomocou deque.

Záver

Deque je front s dvojitým zakončením, ktorý nám umožňuje pridávať / odstraňovať prvky z oboch koncov, tj. Spredu a zozadu, frontu. Deque je možné implementovať pomocou polí alebo prepojených zoznamov. Máme však aj triedu STL (Standard Template Library), ktorá implementuje rôzne operácie Deque.

V Jave máme rozhranie Deque, ktoré sa dedí z rozhrania frontu na implementáciu Deque. Okrem základných štandardných operácií Deque toto rozhranie podporuje rôzne ďalšie operácie, ktoré je možné v Deque vykonávať.

Deque sa všeobecne používa pre aplikácie, ktoré vyžadujú pridanie / odstránenie prvkov na oboch koncoch. Najčastejšie sa používa aj pri plánovaní procesorov vo viacprocesorových systémoch.

=> Vyskúšajte kompletnú sériu školení v C ++

Odporúčané čítanie

^