Stosy to rodzaj adapterów kontenerowych o działaniu typu LIFO (Last In First Out), w którym na jednym końcu (na górze) dodawany jest nowy element, a element jest usuwany tylko z tego końca. Stack używa hermetyzowanego obiektu jednego z nich wektor lub deque (domyślnie) lub lista (sekwencyjna klasa kontenera) jako kontener bazowy, zapewniający określony zestaw funkcji członkowskich umożliwiających dostęp do jego elementów.
obraz przeceny
Jeśli istnieje zamieszanie w pamiętaniu podstawowej różnicy między stosem a kolejką, po prostu miej prawdziwy przykład tego rozróżnienia, w przypadku stosu, układania książek możemy łatwo wziąć najwyższą książkę, a w przypadku kolejki pamiętaj, kiedy musisz stać z przodu kolejki bankomatu w celu wypłaty gotówki, wówczas pierwsza osoba w pobliżu bankomatu ma pierwszą szansę na wyjęcie pieniędzy z bankomatu. Zatem kolejka działa w trybie FIFO (pierwsze weszło, pierwsze wyszło).
Składnia stosu: -
Aby utworzyć stos, musimy dołączyć plik nagłówkowy do naszego kodu. Następnie używamy tej składni do zdefiniowania std::stack:
| szablon |
Typ – jest typem elementu zawartym w std::stack. Może to być dowolny prawidłowy typ C++ lub nawet typ zdefiniowany przez użytkownika.
Pojemnik – jest typem bazowego obiektu kontenera.
Typy członków: -
typ_wartości – Pierwszy parametr szablonu, T. Oznacza typ elementu.
typ_kontenera — drugi parametr szablonu, Kontener. Oznacza podstawowy typ kontenera.
size_type — typ całkowity bez znaku.
Funkcje powiązane ze stosem to:
pusty() – Zwraca, czy stos jest pusty – Złożoność czasowa: O(1)
size() – Zwraca rozmiar stosu – Złożoność czasowa: O(1)
top() – Zwraca referencję do najwyższego elementu stosu – Złożoność czasowa: O(1)
push(g) – Dodaje element „g” na górze stosu – Złożoność czasowa: O(1)
pop() – Usuwa ostatnio wprowadzony element stosu – Złożoność czasowa: O(1)
C++
lista Java jest pusta
#include> #include> using> namespace> std;> int> main() {> >stack<>int>>stos;> >stack.push(21);>// The values pushed in the stack should be of the same data which is written during declaration of stack> >stack.push(22);> >stack.push(24);> >stack.push(25);> >int> num=0;> >stack.push(num);> >stack.pop();> >stack.pop();> >stack.pop();> > >while> (!stack.empty()) {> >cout << stack.top() <<>' '>;> >stack.pop();> >}> }> |
>
>Wyjście
22 21>
Złożoność czasowa: Złożoność czasowa tego programu wynosi O(N), gdzie N jest całkowitą liczbą elementów na stosie. Pętla while iteruje N razy, usuwając elementy ze stosu i drukując je.
Złożoność przestrzeni: Złożoność przestrzenna tego programu wynosi O(N), gdzie N jest całkowitą liczbą elementów na stosie. Struktura danych stosu wykorzystuje przestrzeń proporcjonalnie do liczby przechowywanych w niej elementów. W tym przypadku maksymalny rozmiar stosu wynosi 5, więc złożoność przestrzeni jest stała i można ją również uznać za O(1).
Wyjaśnienie kodu:
- Dołącz plik nagłówkowy iostream lub do naszego kodu, aby skorzystać z jego funkcji.
- Dołącz plik nagłówkowy stosu do naszego kodu, aby móc korzystać z jego funkcji, jeśli jest już zawarty, to nie ma potrzeby stosowania pliku nagłówkowego stosu, ponieważ ma on już wbudowaną funkcję.
- Dołącz przestrzeń nazw std do naszego kodu, aby używać jej klas bez wywoływania jej.
- Wywołaj funkcję main(). W ramach tej funkcji należy dodać logikę programu.
- Utwórz stos do przechowywania wartości całkowitych.
- Użyj funkcji push(), aby wstawić wartość 21 do stosu.
- Użyj funkcji push(), aby wstawić wartość 22 do stosu.
- Użyj funkcji push(), aby wstawić wartość 24 do stosu.
- Użyj funkcji push(), aby wstawić wartość 25 do stosu.
- Aby wprowadzić wartość zmiennej, użyj zmiennej całkowitej num. Tutaj jego wartość wynosi 0, ale możemy przypisać dowolną wartość całkowitą za pomocą cin>> num.
- Użyj funkcji push(), aby wstawić wartość zmiennej num.
- Użyj funkcji pop(), aby usunąć górny element ze stosu, czyli 25. Górny element ma teraz wartość 24.
- Użyj funkcji pop(), aby usunąć górny element ze stosu, czyli 24. Górny element ma teraz wartość 22.
- Użyj pętli while i funkcji pusty(), aby sprawdzić, czy stos NIE jest pusty. ! jest operatorem NOT. Tak więc, gdy stos nie jest pusty, funkcja pusty() zwróci wartość false, a operator NOT zamieni go na wartość true, a pętla while będzie nadal działać. Ale gdy stos stanie się pusty, funkcja pusty() zwróci wartość true, a operator NOT sprawi, że będzie ona fałszywa i pętla dobiegnie końca.
- Drukowanie bieżącej zawartości stosu na konsoli.
- Wywołaj funkcję pop() na stosie.
- Koniec treści pętli while.
- Koniec treści funkcji main().
Lista funkcji Stosu:
- stack::top() w C++ STL
- stack::empty() i stack::size() w C++ STL
- stack::push() i stack::pop() w C++ STL
- stack::swap() w C++ STL
- stack::emplace() w C++ STL
- Najnowsze artykuły na temat stosu C++