Menu

Podwójnie zakończona kolejka (Deque) w C ++ z przykładami

  • Główny
  • Inny
  • Podwójnie zakończona kolejka (Deque) w C ++ z przykładami

double ended queue c with examples

Szczegółowy samouczek dotyczący Deque lub Double-ended Queue w C ++. Samouczek wyjaśnia, czym jest Deque, podstawowe operacje, implementacja C ++ i Java oraz aplikacje:

Podwójnie zakończona kolejka lub po prostu nazywana „Deque” to uogólniona wersja kolejki.

Różnica między Queue i Deque polega na tym, że nie jest on zgodny z podejściem FIFO (First In, First Out). Drugą cechą Deque jest to, że możemy wstawiać i usuwać elementy zarówno z przodu, jak iz tyłu.

=> Przeczytaj serię szkoleń Easy C ++

Podwójnie zakończona kolejka (Deque) w C ++

Czego się nauczysz:

Klasyfikacja w kolejce z podwójnym zakończeniem

Deque można sklasyfikować w następujący sposób:

Ograniczone wprowadzanie dotykowe; W przypadku ograniczonego wejścia, kasowanie można wykonać z obu końców, ale wstawienie może nastąpić tylko z tyłu kolejki.

Deque z ograniczeniem mocy: W kolejce z ograniczonym wyjściem wstawianie może odbywać się z obu końców, ale kasowanie odbywa się tylko z jednego końca, tj. Z przodu kolejki.

Stosy i kolejki możemy również implementować za pomocą deque.

Podstawowe operacje dotykowe

Poniżej przedstawiono podstawowe operacje, które można wykonać na deque.

  • wstawić przód: Wstaw lub dodaj element z przodu deque.
  • wstaw Ostatnia: Wstaw lub dodaj element z tyłu deque.
  • deleteFront: Usuń lub usuń element z początku kolejki.
  • usuń ostatni: Usuń lub usuń element z tyłu kolejki.
  • getFront: Pobiera przednią pozycję w deque.
  • getLast: Pobiera ostatnią pozycję w kolejce.
  • jest pusty: Sprawdza, czy deque jest pusty.
  • jest pełna: Sprawdza, czy deque jest pełny.

i ilustracji

Pusty deque jest reprezentowany w następujący sposób:

Powrót recount

Następnie wstawiamy element 1 z przodu.

jak zainstalować mavena w eclipse

Włożyć element 1 z przodu

Teraz wstawiamy element 3 z tyłu.

Włożyć element 3 z tyłu

Następnie dodajemy element 5 do przodu i po zwiększeniu punktów na froncie do 4.

Element 5 do przodu

Następnie wstawiamy elementy 7 z tyłu i 9 z przodu. Deque będzie wyglądać tak, jak pokazano poniżej.

elementy 7 z tyłu i 9 z przodu

Następnie usuńmy element z przodu.

Usuń element z przodu

W ten sposób widzimy, że kiedy elementy są wstawiane z przodu, pozycja przednia jest zmniejszana, podczas gdy jest zwiększana, gdy element jest usuwany. W przypadku tylnego końca pozycja jest zwiększana przy wkładaniu i zmniejszana przy wyjmowaniu .

i wdrożenie

100 ++ touch Implementacja

Możemy zaimplementować deque w C ++ używając tablic oraz połączonej listy. Poza tym biblioteka standardowych szablonów (STL) ma klasę „deque”, która implementuje wszystkie funkcje dla tej struktury danych.

Tablica implementacji deque została podana poniżej. Ponieważ jest to kolejka dwustronna, do implementacji użyliśmy tablic cyklicznych.

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

Wynik:

Włożyć element 1 na tylnym końcu

włożyć element 3 z tyłu

tylna soczewka deque 3

Po usunięciu, tył = 1

najlepsze darmowe oprogramowanie do tworzenia kopii zapasowych dla systemu Windows 10 2017

wkładanie elementu 5 na przednim końcu

element przedni deque 5

Po usunięciu frontu przód = 1

i wyjście

Ponowne przeliczanie implementacji Java

Interfejs deque w Javie „java.util.Deque” wywodzi się z interfejsu „java.util.Queue”. Deque może być używany jako kolejka (First In, First Out) lub jako stack (Last In, First Out). Te implementacje działają szybciej niż połączona lista.

Poniżej podano hierarchię interfejsu Deque w Javie.

Hierarchia dla interfejsu Deque w Javie

Musimy pamiętać o kilku punktach dotyczących interfejsu Deque w Javie:

  • Implementacja nie jest bezpieczna wątkowo, ponieważ nie ma zewnętrznej synchronizacji.
  • Deque nie obsługuje współbieżności przez wiele wątków.
  • Deque zaimplementowane przy użyciu tablic nie zezwala na użycie elementów NULL.
  • Macierze mogą rosnąć zgodnie z wymaganiami, przy czym pojemność wolna od ograniczeń i obsługa macierzy o zmiennym rozmiarze to dwie najważniejsze cechy.

Poniżej przedstawiono różne metody obsługiwane przez interfejs Deque:

Nie.metodaOpis
7iterator ()Zwraca iterator dla deque.
jedenadd (element)Dodaje element do ogona.
dwaaddFirst (element)Dodaje element do głowy / przodu.
3addLast (element)Dodaje element do ogona / tyłu.
4oferta (element)Dodaje element do ogona; zwraca wartość logiczną wskazującą, czy wstawienie się powiodło.
5offerFirst (element)Dodaje element do głowy; zwraca wartość logiczną wskazującą, czy wstawienie się powiodło.
6offerLast (element)Dodaje element do ogona; zwraca wartość logiczną wskazującą, czy wstawienie się powiodło.
8descendingIterator ()Zwraca iterator, który ma odwrotną kolejność dla tego deque.
9push (element)Dodaje element do głowy deque.
10pop (element)Usuwa element z głowy deque i zwraca go.
jedenaścieremoveFirst ()Usuwa element na czele deque.
12removeLast ()Usuwa element na końcu deque.
13głosowanie()Pobiera i usuwa pierwszy element deque (reprezentowany przez głowę deque); zwraca NULL, jeśli deque jest pusty.
14pollFirst ()Pobiera i usuwa pierwszy element tego deque; zwraca null, jeśli ten deque jest pusty.
piętnaściepollLast ()Pobiera i usuwa ostatni element tego deque; zwraca null, jeśli ten deque jest pusty.
16zerkać()Pobiera głowę (pierwszy element deque) kolejki reprezentowanej przez ten deque; zwraca null, jeśli ten deque jest pusty.
Uwaga: ta operacja nie usuwa elementu.
17peekFirst ()Pobiera pierwszy element tego deque; zwraca null, jeśli ten deque jest pusty.
Uwaga: ta operacja nie usuwa elementu.
18peekLast ()Pobiera ostatni element tego deque lub zwraca null, jeśli ten deque jest pusty.
Uwaga: ta operacja nie usuwa elementu.

Poniższa implementacja języka Java demonstruje różne operacje omówione powyżej.

c # pytania do wywiadu i odpowiedzi dla odświeżających
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); } }

Wynik:

Oraz [11, 7, 3, 1, 5, 9, 13]

Iterator standardowy
11 7 3 1 5 9 13
Iterator odwrotny
13 9 5 1 3 7 11

Podgląd 11
Po zerknięciu: [11, 7, 3, 1, 5, 9, 13]

Pop 11
Po pop: [7, 3, 1, 5, 9, 13]

Zawiera element 3 ?: prawda

Deque po usunięciu pierwszego i ostatniego elementu: [3, 1, 5, 9]

Deque Java Output

W powyższym programie wykorzystaliśmy interfejs Deque języka Java i zdefiniowaliśmy rozkład elementów całkowitoliczbowych. Następnie wykonaliśmy różne operacje na tym deque i wyświetlamy wyniki tych operacji.

Aplikacje

Deque może być używany w niektórych z poniższych zastosowań.

# 1) Algorytm planowania: Algorytm planowania, „algorytm planowania kradzieży”, implementuje planowanie zadań dla różnych procesorów w systemie wieloprocesorowym. Ta implementacja używa deque, a procesor pobiera pierwszy element z deque do wykonania.

# 2) Cofnij listę działań: W aplikacjach mamy wiele działań. Jednym z nich jest „cofnij”. Kiedy wielokrotnie wykonywaliśmy akcję cofania, wszystkie te akcje są przechowywane na liście. Ta lista jest utrzymywana jako deque, dzięki czemu możemy łatwo dodawać / usuwać wpisy z dowolnego końca.

# 3) Usuń wpisy po pewnym czasie: Aplikacje odświeżają wpisy na swojej liście, takie jak aplikacje z listą pozycji giełdowych itp. Te aplikacje usuwają wpisy po pewnym czasie, a także wstawiają nowe wpisy. Odbywa się to za pomocą deque.

Wniosek

Deque to kolejka dwustronna, która pozwala nam dodawać / usuwać elementy z obu końców, tj. Z przodu iz tyłu, kolejki. Deque można zaimplementować za pomocą tablic lub połączonych list. Jednak mamy również klasę Standard Template Library (STL), która implementuje różne operacje Deque.

W Javie mamy interfejs Deque, który jest dziedziczony z interfejsu kolejki do implementacji Deque. Poza podstawowymi standardowymi operacjami Deque, ten interfejs obsługuje różne inne operacje, które można wykonać w Deque.

Deque jest zwykle używany w aplikacjach, które wymagają dodawania / usuwania elementów z obu końców. Jest również używany głównie do planowania procesorów w systemach wieloprocesorowych.

=> Sprawdź całą serię szkoleń C ++

rekomendowane lektury

^