double ended queue c with examples
Podrobný výukový program pro deque nebo dvojitou frontu v C ++. Výukový program vysvětluje, co je Deque, základní operace, implementace a aplikace v C ++ a Java:
Oboustranná fronta nebo jednoduše nazývaná „Deque“ je zobecněná verze fronty.
Rozdíl mezi Queue a Deque spočívá v tom, že nedodržuje přístup FIFO (First In, First Out). Druhou vlastností Deque je, že můžeme vkládat a odebírat prvky z předních i zadních konců.
=> Přečtěte si sérii školení Easy C ++
Co se naučíte:
- Oboustranná klasifikace front
- Základní dotykové operace
- a ilustrace
- a implementace
- Aplikace
- Závěr
- Doporučené čtení
Oboustranná klasifikace front
Deque lze klasifikovat takto:
Omezený dotykový vstup; V omezeném vstupu lze mazání provádět z obou konců, ale vkládání lze provádět pouze na zadním konci fronty.
Deque s omezením výstupu: Ve frontě s omezeným výstupem lze vkládání provádět z obou konců, ale mazání se provádí pouze na jednom konci, tj. Předním konci fronty.
Můžeme také implementovat zásobníky a fronty pomocí deque.
Základní dotykové operace
Následuje základní operace, které lze provést na deque.
- vložte přední: Vložte nebo přidejte položku na přední stranu deque.
- insertLast: Vložte nebo přidejte položku na zadní stranu deque.
- deleteFront: Odstraňte nebo odeberte položku z přední části fronty.
- smazat poslední: Odstraňte nebo odeberte položku ze zadní části fronty.
- getFront: Načte přední položku v deque.
- getLast: Načte poslední položku ve frontě.
- je prázdný: Zkontroluje, zda je deque prázdný.
- je plný: Zkontroluje, zda je deque plný.
a ilustrace
Prázdný deque je znázorněn následovně:
co je soubor torrentu a jak jej mohu otevřít
Dále vložíme prvek 1 vpředu.
Nyní vložíme prvek 3 vzadu.
Dále přidáme prvek 5 na přední stranu a při zvýšení přední body na 4.
Poté vložíme prvky 7 vzadu a 9 vpředu. Deque bude vypadat, jak je znázorněno níže.
Dále odstraníme prvek zepředu.
Vidíme tedy, že když jsou prvky vloženy zepředu, přední pozice se sníží, zatímco se zvýší, když je prvek odstraněn. U zadního konce je pozice pro vložení zvýšena a snížena pro vyjmutí .
a implementace
100 ++ dotyková implementace
Můžeme implementovat deque v C ++ pomocí polí i propojeného seznamu. Kromě toho má STL (Standard Template Library) třídu „deque“, která implementuje všechny funkce pro tuto datovou strukturu.
Implementace pole deque byla uvedena níže. Jelikož se jedná o frontu s dvěma konci, použili jsme pro implementaci kruhová pole.
#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ýstup:
Vložte prvek 1 na zadní konec
vložte prvek 3 na zadní straně
zadní prvek deque 3
Po deleterear, zadní = 1
vkládací prvek 5 na předním konci
přední prvek deque 5
Po odstranění přední, přední = 1
Přepočítání implementace Java
Deque rozhraní v Javě „java.util.Deque“ je odvozeno z rozhraní „java.util.Queue“. Deque lze použít jako frontu (First In, First Out) nebo zásobník (Last In, First Out). Tyto implementace fungují rychleji než propojený seznam.
co je plán testování v testování softwaru
Níže je uvedena hierarchie rozhraní Deque v Javě.
Musíme si zapamatovat několik bodů o rozhraní Deque v Javě:
- Implementace není bezpečná pro vlákna, protože neexistuje žádná externí synchronizace.
- Deque nepodporuje souběžnost více vlákny.
- Implementace Deque pomocí polí neumožňuje použití prvků NULL.
- Pole mohou růst podle požadavků, přičemž dvě nejdůležitější funkce jsou kapacita bez omezení a podpora měnitelného pole.
Následují různé metody podporované rozhraním Deque:
jak vytvořit projekt v zatmění
| Nedělej. | Metoda | Popis |
|---|---|---|
| 7 | iterátor () | Vrátí iterátor deque. |
| 1 | přidat (prvek) | Přidá prvek do ocasu. |
| dva | addFirst (prvek) | Přidá prvek do hlavy / zepředu. |
| 3 | addLast (prvek) | Přidá prvek do ocasu / zezadu. |
| 4 | nabídka (prvek) | Přidá prvek do ocasu; vrací booleovskou hodnotu, která označuje, zda bylo vložení úspěšné. |
| 5 | offerFirst (prvek) | Přidá prvek do hlavy; vrací booleovskou hodnotu, která označuje, zda bylo vložení úspěšné. |
| 6 | offerLast (prvek) | Přidá prvek do ocasu; vrací booleovskou hodnotu, která označuje, zda bylo vložení úspěšné. |
| 8 | descendingIterator () | Vrátí iterátor, který má v opačném pořadí pro tento deque. |
| 9 | tlačit (prvek) | Přidá prvek do hlavy deque. |
| 10 | pop (prvek) | Odebere prvek z hlavy deque a vrátí jej. |
| jedenáct | removeFirst () | Odebere prvek v čele deque. |
| 12 | removeLast () | Odebere prvek na konci deque. |
| 13 | hlasování() | Načte a odebere první prvek deque (představovaný hlavičkou deque); vrátí NULL, pokud je deque prázdný. |
| 14 | pollFirst () | Načte a odebere první prvek tohoto deque; vrátí null, pokud je tento deque prázdný. |
| patnáct | pollLast () | Načte a odebere poslední prvek tohoto deque; vrátí null, pokud je tento deque prázdný. |
| 16 | nahlédnout () | Načte hlavu (první prvek deque) fronty představované tímto deque; vrátí null, pokud je tento deque prázdný. Poznámka: Tato operace neodstraní prvek. |
| 17 | peekFirst () | Načte první prvek tohoto deque; vrátí null, pokud je tento deque prázdný. Poznámka: Tato operace neodstraní prvek. |
| 18 | nahlédnoutPoslední () | Načte poslední prvek tohoto deque nebo vrátí null, pokud je tento deque prázdný. Poznámka: Tato operace neodstraní prvek. |
Následující implementace Java demonstruje různé operace popsané výše.
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ýstup:
A (11, 7, 3, 1, 5, 9, 13)
Standardní Iterátor
11 7 3 1 5 9 13
Reverzní Iterátor
13 9 5 1 3 7 11
Prohlédněte si 11.
Po nahlédnutí: (11, 7, 3, 1, 5, 9, 13)
Pop 11
After pop: (7, 3, 1, 5, 9, 13)
Obsahuje prvek 3 ?: true
Deque po odstranění prvního a posledního prvku: (3, 1, 5, 9)
Ve výše uvedeném programu jsme použili rozhraní Deque v Javě a definovali jsme deque celočíselných prvků. Poté jsme na tomto deque provedli různé operace a na výstupu se zobrazí výsledky těchto operací.
Aplikace
Deque lze použít v některých z následujících aplikací.
# 1) Časový algoritmus: Algoritmus plánování, „Algoritmus plánování A-steal“, implementuje plánování úkolů pro různé procesory v systému s více procesory. Tato implementace používá deque a procesor dostane první prvek z deque k provedení.
# 2) Vrátit zpět seznam aktivit: V softwarových aplikacích máme mnoho akcí. Jeden je „zpět“. Když jsme akci vrácení provedli mnohokrát, všechny tyto akce se uloží do seznamu. Tento seznam je udržován jako deque, abychom mohli snadno přidávat / odebírat položky z jakéhokoli konce.
# 3) Odebrat položky po nějaké době: Aplikace obnovují položky v jejich seznamu, jako jsou aplikace se seznamem skladových položek atd. Tyto aplikace po nějaké době položky odstraní a také vloží nové položky. To se provádí pomocí deque.
Závěr
Deque je fronta s dvojitým zakončením, která nám umožňuje přidávat / odebírat prvky z obou konců fronty, tj. Zepředu i zezadu. Deque lze implementovat pomocí polí nebo propojených seznamů. Máme však také třídu STL (Standard Template Library), která implementuje různé operace Deque.
V Javě máme rozhraní Deque, které se dědí z rozhraní fronty k implementaci Deque. Kromě základních standardních operací Deque podporuje toto rozhraní různé další operace, které lze na Deque provádět.
Deque se obecně používá pro aplikace, které vyžadují přidání / odebrání prvků z obou konců. Většinou se také používá při plánování procesorů ve víceprocesorových systémech.
=> Podívejte se na kompletní sérii školení C ++