Funkcja deque C ++
Elementy są często dodawane z tyłu i usuwane z przodu w normalnej kolejce. Natomiast możemy dodać i usunąć komponenty z przodu iz tyłu deque. Wdrożenie deque w C ++ można wykonać za pomocą tablicy lub listy połączonej.
Poniżej znajduje się lista implementacji tablicy Deque. Wykorzystaliśmy okrągłe tablice do ich wdrożenia, ponieważ jest to kolejka podwójna. Podwójna kolejka jest szybsza i bardziej wydajna niż jakakolwiek inna kolejka, jeśli chodzi o dodawanie i usuwanie komponentów z obu końców.
Reprezentacja Deque
Czasochłonne aspekty wykonywania różnych procesów deque obejmują:
- Dotarcie do elementów: O (1)
- Dodanie lub usuwanie elementu O (n)
- Dodanie lub usunięcie składników na początku końca (1)
Rodzaje deque
Sprawdźmy typy związane z deque w c++.
Wejście ograniczone deque
Wejście jest ograniczone na jednym końcu, ale dozwolone na pozostałych dwóch.
Wyjście ograniczone deque
W tym deque wyjście jest zabronione na jednym końcu, ale wstawienie jest dozwolone na obu końcach.
Tworzenie funkcji deque C ++
Musimy najpierw dołączyć plik nagłówka deque, aby wygenerować deque w c++.
#włączaćPo zaimportowaniu tego pliku można użyć następującej składni do wygenerowania deque:
# Deque deque-name;Typ danych, który chcielibyśmy przechowywać w deque, jest wskazany przez typ obiektu w tym przypadku. Na przykład: int, float, string itp. Deque-name to zmienna nazwa danych, z których będziemy używać.
Inicjowanie funkcji deque
W C ++ funkcja deque można zainicjować na następujący sposób:
DequeDeque
Obie te metody są stosowane do inicjalizacji deque. W obu tych nazwach deque „ARR” jest inicjowany wartościami całkowitymi 1, 3, 7, 0, 5, 8.
Metody deque
Poniżej znajdują się metody deque:
- Wstawić(): Dodaje nowy element i oddaje iterator z pierwszym z nowo dodanych elementów jako punkt.
- Rbegin (): Generuje odwrotny iterator wskazujący ostatnią wartość Deque.
- Rozdzierać(): Generuje odwrotny iterator z początkową pozycją przed pochodzeniem deque.
- Cbegin (): Zwraca stały iterator, który zawsze wskazuje na pierwszy element kontenera; W rezultacie iteratora można wykorzystać tylko do przemierzania deque i nie być modyfikowanym.
- Największy rozmiar(): Liczba elementów, które może zatrzymać pojemnik deque, jest zwracana przez tę funkcję.
- Przydzielać(): Służy do przypisania wartości do pojemnika deque, który jest taki sam lub inny.
- Zmień rozmiar(): Funkcja używana do modyfikacji rozmiaru deque.
- Push_back (): Za pomocą tej funkcji komponenty można dodać z tyłu w deque.
- Przód(): Służy w odniesieniu do początkowego elementu kontenera deque.
- Z powrotem(): Służy w odniesieniu do ostatniego elementu deque pojemnika.
- Jasne(): Służy do wyczyszczenia wszystkich elementów z Deque poprzez zmniejszenie jego rozmiaru do 0.
- Usuwać(): Używane do usuwania obiektów z pojemnika z określonego punktu lub zakresu.
- Deque :: pusta (): Służy do ustalenia, czy deque jest pusty.
- Operator =: Służy do przydzielenia nowych danych do kontenera i wymiany starych.
- Operator[]: Używane w odniesieniu do elementu w operatorze w określonym miejscu.
- Na(): Używane do odwołania się do komponentu obecnego w lokalizacji określonej jako parametr funkcji.
- Zamieniać(): Ta funkcja służy do wymiany deques tego samego typu danych.
- Zaczynać(): Służy do zapewnienia iteratora wskazującego na początkowy obiekt pojemnika deque.
- Emplace_front (): Nowy element jest wstawiany do pojemnika deque za pomocą tej funkcji. Początek deque jest zmieniany w celu zawierania dodatkowego komponentu.
- Emplace_back (): Służy do dodania nowej wartości do pojemnika deque. Nowy komponent jest zawarty na końcu deque.
Deque struktura danych
Sprawdźmy szczegóły struktury danych deque w następnym rozdziale:
Procedury na deque
Kroki te należy wykonać przed przeprowadzeniem kolejnych operacji:
Krok 1: Weź tablicę N-wymiarową (deque). W pierwszej pozycji umieść dwa wskaźniki i ustaw z przodu = -1 i tył = 0.
Ustaw tablicę deque i wskaźniki.
Wstawienie z przodu
Krok 1: Ta akcja dodaje komponent z przodu. Sprawdź lokalizację frontu.
Jeśli front jest mniejszy niż 5, zresetuj przód do N-1 (ostatni indeks).
Krok 2: W razie potrzeby zmniejszyć przód o 1. Teraz dodaj nowy klucz N do tablicy [Front]. Załóżmy, że n = 6.
Wstawienie z tyłu
Krok 1: Ta akcja dodaje element w rzadkim. Upewnij się, że tablica nie jest pełna.
Krok 2: Jeśli kolejka jest pełna, zresetuj tylną wartość do 0 (r = 0). W przeciwnym razie podnieś rzadkie o 1.
Krok 3: W tablicy [tył] dodaj nowy klucz 6.
Wyjmij z przodu
Krok 1: Element z przodu jest usuwany podczas procesu. Upewnij się, że deque nie jest pusty.
Krok 2: Usunięcie nie jest możliwe, jeśli deque jest pusta (front = -1) (warunek podlegania pod premetem). Ustaw tylko przód = -1 i tył = -1 Jeśli deque składa się z jednego elementu, takiego jak front = tył. Przypisz wartość do przodu (z przodu = 0), jeśli przód znajduje się na końcu (przód = n - 1). Jeśli nie, ustaw przedni na przód = przód+1.
Wyjmij z tyłu
Krok 1: Element na końcu jest usuwany podczas procesu. Upewnij się, że deque nie jest pusty.
Krok 2: Usunięcie nie jest możliwe, jeśli deque jest pusta (front = -1) (warunek podlegania pod premetem). Ustaw z przodu = -1 i tył = -1, jeśli deque ma tylko jeden element (przód = tył). W przeciwnym razie kontynuuj następujące kroki. Przejdźmy do przodu, tył = n - 1, jeśli tył znajduje się z przodu (tył = 0). Jeśli nie, ustaw rzadki = rzadki 1.
Przykład 1: Tworzenie deque
W tym przykładzie tworzymy deque. Najpierw dołączamy nasze pliki nagłówka „#include” i #include, gdzie #include poleca preprocesorowi, aby dołączyć plik nagłówka iostream i deque, który zawiera wszystkie funkcje programu.
#włączać#włączać
za pomocą przestrzeni nazw Std;
void display_deque (deque);
int main ()
Deque myDeque 4, 2, 7, 5, 8;
Cout << "mydeque values are = ";
for (int var: myDeque)
Cout << var << ", ";
powrót 0;
Następnie opisujemy funkcję wyświetlania _deque, która służy do wykonywania wartości deque, które do niej przypisujemy.
Przechodząc do naszej głównej funkcji, int main () wskazuje, że nasza funkcja musi zwrócić wartość całkowitą na końcu wykonania, co robimy, zwracając 0 na wniosek programu, stosując jednolitą inicjalizację „Deque myDeque 4, 2, 7 , 5,8 ”. W tym „int” jest typ danych, które przypisaliśmy, a myDeque to nazwa, której użyliśmy dla naszego deque. Przypisaliśmy wartości liczb całkowitych do deque o nazwie MyDeque, które są 4, 2, 7, 5, 8. Aby wyświetlić nasz deque, użyliśmy pętli dla ustalonego rozmiaru. A następnie nacisnęliśmy przycisk RUN lub F7, aby uzyskać wyjście programu.
Przykład 2: Dodanie większej liczby wartości do deque
W tym przykładzie dodajemy więcej wartości do deque. Po dodaniu wymaganych plików nagłówka dla tego programu przechodzimy do naszej głównej funkcji typu danych liczb całkowitych „Deque var 0, 1, 2”. W tym „int” jest typ danych, które przypisaliśmy, a „var” to nazwa, której użyliśmy dla naszego deque. Przypisujemy wartości liczb całkowitych do deque o nazwie „var”, które wynoszą 0, 1 i 2. Następnie pchamy dwa elementy, element 8 z przodu deque i elementu 5 na końcu deque, za pomocą funkcji push_front () i push_back (). Tak więc, co mamy, to 8, 0, 1 i 5.
#włączać#włączać
za pomocą przestrzeni nazw Std;
int main ()
deque var 0, 1, 2;
Cout << "Initial Deque values are: ";
dla (const int & var: var)
Cout << var << ", ";
var.push_back (5);
var.push_front (8);
Cout << "\nFinal Deque values are: ";
dla (const int & var: var)
Cout << var << ", ";
powrót 0;
Po zakończeniu kodowania tego przykładu kompilujemy go i wykonujemy w dowolnym kompilatorze. Wynik przedstawia oczekiwane dane wyjściowe poprzedniego kodu.
Przykład 3: Aktualizacja elementów w określonych indeksach
W tym przykładzie aktualizujemy wartości w deque po włączeniu plików nagłówka „#include” i „#Include” dla tego kodu wykonywalnego.
#włączać#włączać
za pomocą przestrzeni nazw Std;
int main ()
deque var = 1, 2;
Cout << "Initial Deque values are: ";
dla (const int & var: var)
Cout << var << ", ";
var.przy (0) = 3;
var.przy (1) = 4;
Cout << "\nUpdated Deque values are: ";
dla (const int & var: var)
Cout << var << ", ";
powrót 0;
Teraz idziemy w kierunku naszej głównej funkcji, w której po raz pierwszy zainicjowaliśmy nasz deque o nazwie „var” z wartościami 1 i 2. Następnie używamy pętli do wyświetlania wartości naszego zainicjowanego deque. Aby zaktualizować wartości deque, używamy funkcji at (jak wiemy, funkcja AT () jest używana w odniesieniu do określonej pozycji w deque) przy indeksie 0 i 1, przypisując nowe wartości do „var”. Są to 3 i 4. Następnie nasz zaktualizowany dequeue to 3 i 4. Po przygotowaniu kodu kompilujemy go za pomocą dowolnego narzędzia kompilatora. Oto pożądane dane wyjściowe naszego kodu:
Przykład 4: Używanie iteratora do usunięcia wartości
W tym przykładzie używamy iteratorów, aby uzyskać dostęp do elementów w deque. Obiekt, który wskazuje na element wewnątrz pojemnika, nazywa się iteratorem.
#włączać#włączać
za pomocą przestrzeni nazw Std;
int main ()
deque var 0, 3, 5, 8;
deque :: iterator var_iter;
var_iter = var.zaczynać();
int First_element = *var_iter;
Cout << "var[0] = " << first_element << endl;
var_iter = var.początek () + 1;
int element_index1 = *var_iter;
Cout << "var[1] = " << element_index1 << endl;
var_iter = var.end () - 1;
int last_element = *var_iter;
Cout << "var[2] = " << last_element;
powrót 0;
Deque można iterować zarówno do przodu, jak i do tyłu za pomocą deque :: cbegin i deque :: Cend i na oba sposoby za pomocą deque :: crbegin i deque :: Crend.
Początkowo stworzyliśmy iterator, który może wskazywać na deque liczb całkowitych o nazwie „var”. Następnie wskazaliśmy na następujące elementy za pomocą iteratora „var_inter”. Iterator, który metoda początkowa () zwraca punkty do pierwszego elementu. „Begin () + 1” generuje iterator przy użyciu indeksu elementu 1 jako jego punktu wyjścia. Jak widać, używamy var.end () - 1 zamiast var.koniec().
Wynika to z faktu, że iterator metody end () łączy się z iteratorem, który mija ostatni element. Aby uzyskać ostatni element, odejmujemy 1. Używamy operatora pośredniego *, aby uzyskać wartość elementu po użyciu inter_var, aby wskazać go.
Operacje Deque
Podstawowe operacje, które można przeprowadzić na Deque, są następujące:
- InsertFront jest zwykle używany do dodawania lub wstawienia czegoś z przodu deque.
- Wstaw lub dodaj coś na końcu deque za pomocą wstawka Komenda.
- deletefront służy do usuwania elementu z przodu kolejki, usuwając go.
- Usuń final w tym elemencie należy usunąć lub przenieść do końca kolejki.
- Uzyskaj pierwszy element w deque za pomocą Getfront metoda.
- Uzyskaj ostatni element w kolejce za pomocą Getlast metoda.
- jest pusty służy do sprawdzenia, czy deque jest null.
- jest pełna służy do ustalenia, czy deque jest pełny.
Wniosek
Deque jest największą opcją, ponieważ jest szybszy i pomaga kodowi działać szybciej. Deque działa lepiej dla sekwencji dziennika. Ten artykuł oparty jest na wdrożeniu deque i jego głównych metodach, które pomagają nam modyfikować deque zgodnie z naszymi potrzebami. Naszym celem jest wyjaśnienie deque i jego metod, a także przykładami, jak używać deque i kiedy go używać. Narzędziem, którego użyliśmy do wdrożenia kodu, jest kompilator C ++. Podjęliśmy szczere wysiłki, aby ten samouczek był jak najwyżej i jak najważniejszy dla ciebie.