stacks queues stl
Naucz się implementacji stosów i kolejek w STL z przykładami.
Stosy i kolejki to dwa kontenery w STL, które mają bardzo podstawowy charakter. Są to najprostsze kontenery, które mają szerokie zastosowanie w programowaniu.
W tym samouczku zobaczymy szczegółową implementację obu tych kontenerów w STL. Przeanalizujemy również różne operacje obsługiwane przez stos i kolejkę z przykładami.
=> Obejrzyj serię prostych szkoleń C ++ tutaj.
Czego się nauczysz:
Półki na książki
Kontener stosowy w STL to rodzaj adapterów do kontenerów. Służy do replikacji struktury danych stosu w C ++. Kontener stosu to zestaw elementów, w których elementy są wstawiane na jednym końcu, a także są usuwane na tym samym końcu.
Ten wspólny punkt dodawania i usuwania jest znany jako „szczyt stosu”.
Graficzne przedstawienie stosu pokazano poniżej.
Jak pokazano na powyższej ilustracji, stos jest kontenerem, w którym elementy są dodawane i usuwane z tego samego końca zwanego wierzchołkiem stosu.
Ponieważ dodawanie i usuwanie odbywa się na tym samym końcu, możemy powiedzieć, że kontener stosu to praca typu LIFO (ostatni wchodzi, pierwszy wychodzi). Oznacza to, że element dodany jako pierwszy będzie ostatnim usuwany.
Aby zaimplementować kontener stosu, musimy dołączyć nagłówek do naszego programu.
#include
Ogólna składnia deklaracji kontenera stosu to:
stack stackName;
Operacje na stosie
Następnie omówmy różne operacje, które obsługują kontener w STL.
- Pchać : operacja wypychania służy do wstawiania elementu do stosu. Ta operacja zawsze dodaje elementy na szczycie stosu.
Rozważmy pusty stack mystack typu integer .
Następnie dodajmy element 1 do stosu.
Następnie dodajemy element 3 do stosu.
Zgodnie z przedstawieniem, w wyniku operacji wypychania, element jest dodawany na szczycie stosu. Po każdej operacji pchania rozmiar stosu jest zwiększany o 1.
- Muzyka pop : operacja pop służy do usunięcia elementu ze stosu. Usunięty element to ten, na który wskazuje górna część stosu. W wyniku operacji pop rozmiar stosu jest zmniejszany o 1.
Zobaczmy, jak wygląda operacja pop:
Rozważmy tajemnicę stosu jak powyżej, w której już zepchnęliśmy 2 elementy.
Teraz wywołajmy funkcję pop (). Po wykonaniu tego wywołania element znajdujący się na szczycie stosu jest usuwany, a „Góra” wskazuje na następny element, jak pokazano poniżej.
Jeśli ponownie wywołasz pop (), następny element (w tym przypadku 1) zostanie usunięty, co spowoduje powstanie pustego stosu.
zautomatyzowane narzędzia testowe dla aplikacji internetowych
- Top : Zwraca najwyższy element stosu.
- pusty : Sprawdza, czy stos jest pusty, czy nie.
- rozmiar: Zwraca rozmiar stosu, czyli liczbę elementów w stosie.
Poniżej podano przykład implementacji stosu, aby lepiej zrozumieć operacje.
#include #include using namespace std; void printStack(stack stk) { while (!stk.empty()) { cout << ' ' << stk.top(); stk.pop(); } cout << '
'; } int main () { stack oddstk; oddstk.push(1); oddstk.push(3); oddstk.push(5); oddstk.push(7); oddstk.push(9); cout << 'The stack is : '; printStack(oddstk); cout << '
Size of stack: ' << oddstk.size(); cout << '
Top of stack: ' << oddstk.top(); cout << '
oddstk.pop() : '; oddstk.pop(); printStack(oddstk); cout<<'
Another pop(): '; oddstk.pop(); printStack(oddstk); return 0; }
Powyższy przykład wyraźnie pokazuje operację wypychania, która generuje stos. Pokazuje również stos po dwóch kolejnych operacjach wyskakujących.
jak uruchomić swf w chrome
W ten sposób widzieliśmy stos i jego operacje w STL. Ponadto w tym samouczku zobaczymy szczegółową implementację jeszcze jednego prostego kontenera STL, którym jest „Kolejka”.
Kolejka
Kolejka to kolejny kontener w STL, który jest również bardzo prosty i przydatny. Kontener kolejki jest repliką struktury danych kolejki w języku C ++. W przeciwieństwie do stosu, w kontenerze kolejki są dwa końce, tj. Przód i tył.
Elementy są dodawane do kolejki z tyłu, a usuwane z przodu kolejki. Generalnie kolejka korzysta z układu typu FIFO (pierwsze weszło, pierwsze wyszło).
Aby zaimplementować kontener kolejki w programie, musimy dołączyć nagłówek w kodzie.
#include
Ogólna składnia deklaracji kolejki to:
queue nazwa_kolejki;
Deklarujemy kontener kolejki w następujący sposób:
Queue myqueue;
Operacje kolejki
Teraz zobaczymy różne operacje obsługiwane przez kolejkę.
- Pchać: Funkcja „push” dodaje element na końcu kolejki, czyli na końcu kolejki.
- Muzyka pop: Funkcja „pop” usuwa pierwszy element kolejki, tj. Element na początku kolejki.
Zrozummy funkcje push i pop kolejki.
Rozważ pustą kolejkę zadeklarowaną powyżej myqueue. Teraz z operacją wciskamy parzystą liczbę 2 do kolejki
myqueue.push (2);
Teraz kolejka będzie wyglądać następująco:
Następnie dodajemy „4” do kolejki wywołując „myqueue.push (4)”.
Teraz kolejka wygląda jak poniżej:
Jak widać powyżej, elementy są wpychane do kolejki od tyłu lub od tyłu.
Teraz uruchommy operację na myqueue.
myqueue.pop ();
Jak widzimy, wywołanie pop () powoduje usunięcie elementu znajdującego się na początku kolejki. Oznacza to, że pierwszy element, który zostanie wprowadzony do kolejki, jest pierwszym elementem, który zostanie z kolejki.
- z przodu: Ta funkcja zwraca odwołanie do pierwszego elementu kolejki.
- z powrotem: Back zwraca odwołanie do ostatniego elementu w kolejce.
- pusty: Sprawdza, czy kolejka jest pusta.
- rozmiar: Zwraca rozmiar kolejki, czyli liczbę elementów w kolejce.
Poniżej podano przykładowy program, który demonstruje operacje używane przez kontener kolejki.
#include #include using namespace std; void printQueue(queue myqueue) { queue secqueue = myqueue; while (!secqueue.empty()) { cout << ' ' << secqueue.front(); secqueue.pop(); } cout << '
'; } int main() { queue myqueue; myqueue.push(2); myqueue.push(4); myqueue.push(6); myqueue.push(8); cout << 'The queue myqueue is : '; printQueue(myqueue); cout << '
myqueue.size() : ' << myqueue.size(); cout << '
myqueue.front() : ' << myqueue.front(); cout << '
myqueue.back() : ' << myqueue.back(); cout << '
myqueue.pop() : '; myqueue.pop(); printQueue(myqueue); return 0; }
Wynik:
Kolejka myqueue to: 2 4 6 8
myqueue.size (): 4
myqueue.front (): 2
myqueue.back (): 8
myqueue.pop (): 4 6 8
Jak pokazano powyżej, najpierw deklarujemy kontener kolejki. Następnie za pomocą operacji wypychania dodajemy do niego pierwsze cztery liczby parzyste. Następnie zdejmujemy element z kolejki i wyświetlamy zmienioną kolejkę.
Wniosek
W ten sposób dotarliśmy do końca tego samouczka dotyczącego stosów i kolejek. Jak już wspomniałem są to najprostsze kontenery jakie mamy w STL. Inną odmianą kontenera kolejki jest „kolejka priorytetowa”.
W naszym nadchodzącym samouczku omówimy więcej na temat kolejki priorytetowej w STL !!
=> Odwiedź tutaj, aby nauczyć się C ++ od podstaw.