2.1. Co to jest stos?
Stos jest to
struktura danych, w której dostęp do danych jest możliwy tylko do jednego elementu, zwanego wierzchołkiem. Stos jest określany mianem LIFO (Last In First Out), czyli
ostatni wchodzący element jest pierwszym wychodzącym.
2.2. Operacje na stosie
Stos w STL'u posiada następujące operacje:
2.3. Jak wykorzystywać adapter stosu w C++
Aby móc skorzystać ze stosu w C++, należy dołączyć plik nagłówkowy:
Kolejnym krokiem, jaki musimy wykonać jest utworzenie stosu. Zapis uogólniony wygląda tak:
std::stack < TYP_DANYCH > nazwa_stosu;
Stos może przechowywać dowolny typ danych - mogą być to typy, które już znasz czyli:
std::stack < int > stos1;
std::stack < std::string > stos2;
Mogą to być również struktury danych lub klasy, które utworzysz:
struct SDane
{
int liczba;
std::string tekst;
};
class CKlasa
{
private:
SDane dane[ 2 ];
public:
SDane & DajDane( int indeks )
{
return dane[ indeks ];
}
};
std::stack < SDane > stos3;
std::stack < CKlasa > stos4;
Jak widać utworzenie stosu dowolnego typu danych jest proste i sprowadza się do napisania jednej linijki. W dalszej części tego rozdziału będą opisane metody za pomocą których możesz wykonywać wcześniej już wspomniane operacje na stosie.
2.4. Umieszczanie nowego elementu na stosie (metoda: push)
Metoda
push służy do umieszczenia nowego elementu na szczycie stosu.
void push( const TYP_DANYCH & wartosc );
Standardowa złożoność obliczeniowa metody:
O(1).
2.4.1. Przykład
#include <stack>
int main()
{
std::stack < int > stosLiczb;
stosLiczb.push( 123 );
stosLiczb.push( 12 );
stosLiczb.push( 55 );
return 0;
}
2.5. Odczytywanie i modyfikacja szczytowej wartości na stosie (metoda: top)
Metoda
top służy do odczytania lub modyfikacji wartości umieszczonej na szczycie stosu.
TYP_DANYCH & top();
Standardowa złożoność obliczeniowa metody:
O(1).
2.5.1. Przykład
#include <stack>
#include <iostream>
#include <conio.h>
int main()
{
std::stack < int > stosLiczb;
std::cout << "Podaj liczbe: ";
int liczba;
std::cin >> liczba;
stosLiczb.push( liczba );
std::cout << "Ostatnia liczba na stosie to: " << stosLiczb.top() << std::endl;
stosLiczb.top() *= 2;
std::cout << "Zmodyfikowalem liczbe na stosie" << std::endl;
std::cout << "Ostatnia liczba na stosie to: " << stosLiczb.top() << std::endl;
stosLiczb.top() = 1234;
std::cout << "Zmodyfikowalem liczbe na stosie" << std::endl;
std::cout << "Ostatnia liczba na stosie to: " << stosLiczb.top() << std::endl;
getch();
return 0;
}
2.6. Pobranie informacji o ilości elementów na stosie(metoda: size)
Metoda
size zwraca ilość elementów aktualnie znajdujących się na stosie.
size_type size() const;
Standardowa złożoność obliczeniowa metody:
O(1).
2.6.1. Przykład
#include <stack>
#include <iostream>
#include <conio.h>
int main()
{
std::stack < int > stosLiczb;
int liczba = 0;
do
{
std::cout << "Podaj liczbe (0 - konczy wprowadzanie liczb): ";
liczba = 0;
std::cin >> liczba;
if( liczba != 0 ) stosLiczb.push( liczba );
} while( liczba != 0 );
std::cout << "Na stosie znajduje sie " << stosLiczb.size() << " liczb." << std::endl;
getch();
return 0;
}
2.7. Sprawdzanie czy stos jest pusty (metoda: empty)
Metoda
empty sprawdza, czy stos jest pusty.
bool empty() const;
Standardowa złożoność obliczeniowa metody:
O(1).
2.7.1. Przykład
#include <stack>
#include <iostream>
#include <conio.h>
int main()
{
std::stack < int > stosLiczb;
if( stosLiczb.empty() )
{
std::cout << "Stos jest pusty." << std::endl;
} else
{
std::cout << "Na stosie znajduje sie przynajmniej jeden element." << std::endl;
}
stosLiczb.push( 1234 );
stosLiczb.push( 124 );
stosLiczb.push( 34 );
stosLiczb.push( 4 );
if( stosLiczb.empty() )
{
std::cout << "Stos jest pusty." << std::endl;
} else
{
std::cout << "Na stosie znajduje sie przynajmniej jeden element." << std::endl;
}
getch();
return 0;
}
2.8. Zdejmowanie istniejącego elementu ze stosu (metoda: pop)
Metoda
pop służy do zdjęcia istniejącego elementu ze szczytu stosu.
void pop();
Standardowa złożoność obliczeniowa metody:
O(1).
2.8.1. Przykład
#include <stack>
#include <iostream>
#include <conio.h>
int main()
{
std::stack < int > stosLiczb;
int liczba = 0;
do
{
std::cout << "Podaj liczbe (0 - konczy wprowadzanie liczb): ";
liczba = 0;
std::cin >> liczba;
if( liczba != 0 ) stosLiczb.push( liczba );
} while( liczba != 0 );
std::cout << "Liczby zdjete ze stosu: ";
while( stosLiczb.empty() == false )
{
std::cout << stosLiczb.top() << ", ";
stosLiczb.pop();
}
getch();
return 0;
}
2.9. Zaawansowane wykorzystywanie adaptera stosu
Adapter stosu w STL'u ma znacznie większe możliwości niż te, które do tej pory zobaczyłeś. Adapter STL'a umożliwia nam zmianę mechanizmu zarządzającego danymi bez potrzeby wprowadzania modyfikacji w całym programie. W rzeczywistości szablon STL'a zdefiniowany jest następująco:
namespace std
{
template < typename typZmiennej, typename kontenerDanych >
class stack
{
};
}
Aby adapter stosu był łatwy w użyciu, twórcy STL'a dopisali linijkę, która dostarczy programiście kontener danych o najwyższej wydajności, jaki jest dostępny w STL'u. Linijka o której mowa wygląda następująco:
template < typename typZmiennej, typename kontenerDanych = deque < typZmiennej > >
class stack;
Dzięki powyższemu zapisowi kompilator wie, że jeśli nie podamy drugiego parametru, to użyje on domyślnego kontenera, którym dla stosu w STL'u jest
deque. Zgodnie z powyższym - poniższe dwa zapisy są sobie równoważne:
std::stack < int > mojStos1;
std::stack < int, std::deque < int > > mojStos2;
Ponieważ programiści chcą być leniwi to używają krótszego zapisu, a ci początkujący często nie zdają sobie sprawy o tym, że istnieje jeszcze jeden parametr dla adaptera stosu.
2.9.1. Po co tworzy się własne kontenery?
Pisząc własne programy może się zdarzyć tak, że będziesz chciał użyć własnego kontenera do obsługi stosu, a nie STL'owego. Pierwsze co zrobiłby początkujący programista, to wykonałby następującą zmianę:
std::stack < int > mojStos;
CMojStos mojStos;
Rozwiązanie takie jest oczywiście poprawne, jednak pozostali programiści pracujący w tym samym projekcie musieliby poznać jak jest zbudowana klasa CMojStos i jakie daje metody. Co więcej prawdopodobnie nie będą oni zainteresowani zgłębianiem tajników klasy, którą utworzyłeś i użyją do tego celu STL'a, który może być znacznie wolniejszy od Twojego rozwiązania. Co więc zrobić, aby Twój kod był użyteczny i stosowany w programie? Należy napisać własny kontener, który podmienisz w linijce tworzącej stos. Kontener ten będzie jednocześnie uniwersalny dla dowolnego typu danych, więc będzie mógł być wykorzystywany wielokrotnie w programie do różnych celów.
2.9.2. Zanim zabierzesz się za tworzenie własnego kontenera
Tworzenie kontenerów wiąże się z umiejętnością tworzenia
szablonów klas. Jeśli nie wiesz co to są szablony i jak się je tworzy, to warto prędzej czy później poczytać o nich, bowiem nigdy nie wiadomo kiedy się na nie natkniesz. Poniżej przedstawię tylko zarys szablonu klasy, który musi być zaimplementowany aby nasz kontener mógł zostać użyty w adapterze STL'a. Pamiętaj, że zmieniając kontener zmieniasz złożoność obliczeniową każdej z funkcji. Tworząc własny kontener możesz zaszkodzić wydajności programu, ponieważ Twój kontener może być wolniejszy od domyślnego STL'owego kontenera. Warto również go gruntownie przetestować pod kątem wszystkich operacji, żeby się nie okazało, że użycie Twojego kontenera powoduje np. wieszanie się całej aplikacji.
2.9.3. Jak utworzyć własny kontener do adaptera stosu?
Poniższy kod jest wzorem, który można wykorzystać przy tworzeniu własnej implementacji kontenera, który będzie mógł współpracować z adapterem stosu STL'a.
#include <stack>
template < typename typZmiennej >
class CKontenerStosu
{
public:
typedef typZmiennej value_type;
typedef typZmiennej & reference;
typedef const typZmiennej & const_reference;
typedef int size_type;
void push_back( const_reference zmienna ) { }
void pop_back( void ) { }
bool empty( void ) const { }
size_type size( void ) const { }
reference back( void ) { }
CKontenerStosu( void ) { }
CKontenerStosu( const CKontenerStosu & skopiuj ) { }
~CKontenerStosu( void ) { }
};
int main()
{
std::stack < int, CKontenerStosu < int > > mojStos;
mojStos.push( 12 );
mojStos.pop();
mojStos.empty();
mojStos.size();
mojStos.top();
return 0;
}
Warto w tym miejscu dodać, że do powyższego szablonu klasy możesz dodawać własne zmienne i funkcje. Adapter stosu będzie widział jednak tylko i wyłącznie funkcje, które zostały wyszczególnione w powyższym przykładzie co oznacza, że nie możesz nazwać inaczej funkcji publicznych, służących do wykonywania wyszczególnionych operacji.