[ Pobierz całość w formacie PDF ]
void pop() { c.pop_back(); }
value_type& top() { return c.back(); }
const value_type& top() const { return c.back(); }
};
template
bool operator==(const stack&,
const stack&);
template
10.1. STOSY 405
bool operator
const stack&);
...// (inne operatory porownania)
}
Poniższa część tego podrozdzialu zawiera szczególowy opis pól oraz operacji.
Definicje typu
stack::value_type
" Rodzaj elementów umieszczonych w kontenerze.
" Skladowa równoważna jest skladowej container::value_type.
stack::size_type
" Typ calkowity bez znaku, określający rozmiar umieszczonych elementów.
" Skladowa równoważna jest skladowej container::size_type.
stack::container_type
" Rodzaj kontenera.
Funkcje skladowe
stack::stack ()
" Konstruktor domyślny.
" Tworzy pusty stos.
explicit stack::stack (const Container& cont)
" Tworzy stos inicjalizowany elementami umieszczonymi w obiekcie cont.
" Kopiowane są wszystkie elementy umieszczone w kontenerze cont.
size_type stack::size () const
" Zwraca bieżącą liczbę elementów.
" W celu sprawdzenia, czy stos jest pusty, używaj funkcji skladowej o nazwie empty(),
ponieważ jej dzialanie może być szybsze.
bool stack::empty () const
" Zwraca wartość logiczną, określającą, czy stos jest pusty (nie zawiera elementów).
" Funkcja skladowa równoważna konstrukcji postaci stack::size()==0, lecz może
dzialać od niej szybciej.
void stack::push (const value_type& elem)
" Wstawia jako pierwszy element stosu kopię elementu, określonego przez wartość elem.
value_type& stack::top ()
const value_type& stack::top () const
" Obie postaci funkcji skladowej zwracają kolejny element stosu. Będzie nim element
wstawiony jako ostatni (po wszystkich innych elementach stosu).
" Przed wywolaniem funkcji skladowej należy upewnić się, że stos zawiera jakiekol-
wiek elementy (size()>0). W innym przypadku jej dzialanie jest nieokreślone.
406 10. KONTENERY SPECJALNE
" Funkcja skladowa w pierwszej postaci przeznaczona jest dla stosów, które nie są
określone jako statyczne (nonconstant) i zwraca referencję. Dlatego też możliwe jest
zmodyfikowanie kolejnego elementu jeszcze w chwili, gdy jest on umieszczony na
stosie. Do ciebie należy podjęcie decyzji, czy jest to dobry styl programowania.
void stack::pop ()
" Usuwa kolejny element stosu. Będzie nim element wstawiony jako ostatni (po wszyst-
kich innych elementach stosu).
" Funkcja nie zwraca wartości. W celu przetworzenia kolejnego elementu musisz wcze-
śniej wywolać funkcję skladową top().
" Przed wywolaniem funkcji skladowej należy upewnić się, że stos zawiera jakiekolwiek
elementy (size()>0). W innym przypadku jej dzialanie jest nieokreślone.
bool comparison (const stack& stack1, const stack& stack2)
" Zwraca wynik porównania dwóch stosów tego samego rodzaju.
" comparison może być określony w jeden z poniższych sposobów:
operator ==
operator !=
operator
operator >
operator
operator >=
" Dwa stosy są jednakowe w przypadku, gdy zawierają taką samą liczbę identycz-
nych elementów umieszczonych w tej samej kolejności (porównanie każdych dwóch
odpowiadających sobie elementów musi dawać w rezultacie wartość true).
" W celu sprawdzenia, czy jeden stos jest mniejszy od drugiego, oba porównywane są
leksykograficznie. Więcej informacji zostalo umieszczonych na stronie 338 wraz
z opisem algorytmu o nazwie lexicographical_compare().
10.1.4. Klasa st>su defini>waneg> przez użytk>wnika
Standardowa klasa stack preferuje szybkość dzialania nad wygodę oraz bezpieczeństwo
użytkowania. Nie jest to tym, co zazwyczaj ja uważam za najlepsze podejście. Dlatego też
napisalem wlasną klasę stosu. Ma ona dwie zalety:
1. pop() zwraca kolejny element.
2. pop() oraz top() zwraca wyjątek w przypadku, gdy stos jest pusty.
Dodatkowo pominąlem wszystkie funkcje skladowe, które nie są niezbędne dla zwyklego
użytkownika stosu, jak chociażby operacje porównania. Moja klasa stosu zdefiniowana
zostala w następujący sposób:
//cont/Stack.hpp
/* ************************************************************
* Stack.hpp
* - bezpieczniejsza oraz bardziej wygodna klasa stosu
* ************************************************************/
#ifndef STACK_HPP
#define STACK_HPP
10.1. STOSY 407
#include
#include
template
class Stack {
protected:
std::deque c; // kontener zawierajacy elementy
public:
/* klasa wyjatku dla funkcji składowych pop() oraz top() wywolanych w przypadku pustego stosu
*/
class ReadEmptyStack : public std::exception {
public:
virtual const char* what() const throw() {
return "proba odczytania pustego elementu";
}
};
// liczba elementow
typename std::deque::size_type size() const {
return c.size();
}
// czy stos jest pusty?
bool empty() const {
return c.empty();
}
// umiesc element na stosie [ Pobierz całość w formacie PDF ]
zanotowane.pl doc.pisz.pl pdf.pisz.pl akte20.pev.pl
void pop() { c.pop_back(); }
value_type& top() { return c.back(); }
const value_type& top() const { return c.back(); }
};
template
bool operator==(const stack&,
const stack&);
template
10.1. STOSY 405
bool operator
const stack&);
...// (inne operatory porownania)
}
Poniższa część tego podrozdzialu zawiera szczególowy opis pól oraz operacji.
Definicje typu
stack::value_type
" Rodzaj elementów umieszczonych w kontenerze.
" Skladowa równoważna jest skladowej container::value_type.
stack::size_type
" Typ calkowity bez znaku, określający rozmiar umieszczonych elementów.
" Skladowa równoważna jest skladowej container::size_type.
stack::container_type
" Rodzaj kontenera.
Funkcje skladowe
stack::stack ()
" Konstruktor domyślny.
" Tworzy pusty stos.
explicit stack::stack (const Container& cont)
" Tworzy stos inicjalizowany elementami umieszczonymi w obiekcie cont.
" Kopiowane są wszystkie elementy umieszczone w kontenerze cont.
size_type stack::size () const
" Zwraca bieżącą liczbę elementów.
" W celu sprawdzenia, czy stos jest pusty, używaj funkcji skladowej o nazwie empty(),
ponieważ jej dzialanie może być szybsze.
bool stack::empty () const
" Zwraca wartość logiczną, określającą, czy stos jest pusty (nie zawiera elementów).
" Funkcja skladowa równoważna konstrukcji postaci stack::size()==0, lecz może
dzialać od niej szybciej.
void stack::push (const value_type& elem)
" Wstawia jako pierwszy element stosu kopię elementu, określonego przez wartość elem.
value_type& stack::top ()
const value_type& stack::top () const
" Obie postaci funkcji skladowej zwracają kolejny element stosu. Będzie nim element
wstawiony jako ostatni (po wszystkich innych elementach stosu).
" Przed wywolaniem funkcji skladowej należy upewnić się, że stos zawiera jakiekol-
wiek elementy (size()>0). W innym przypadku jej dzialanie jest nieokreślone.
406 10. KONTENERY SPECJALNE
" Funkcja skladowa w pierwszej postaci przeznaczona jest dla stosów, które nie są
określone jako statyczne (nonconstant) i zwraca referencję. Dlatego też możliwe jest
zmodyfikowanie kolejnego elementu jeszcze w chwili, gdy jest on umieszczony na
stosie. Do ciebie należy podjęcie decyzji, czy jest to dobry styl programowania.
void stack::pop ()
" Usuwa kolejny element stosu. Będzie nim element wstawiony jako ostatni (po wszyst-
kich innych elementach stosu).
" Funkcja nie zwraca wartości. W celu przetworzenia kolejnego elementu musisz wcze-
śniej wywolać funkcję skladową top().
" Przed wywolaniem funkcji skladowej należy upewnić się, że stos zawiera jakiekolwiek
elementy (size()>0). W innym przypadku jej dzialanie jest nieokreślone.
bool comparison (const stack& stack1, const stack& stack2)
" Zwraca wynik porównania dwóch stosów tego samego rodzaju.
" comparison może być określony w jeden z poniższych sposobów:
operator ==
operator !=
operator
operator >
operator
operator >=
" Dwa stosy są jednakowe w przypadku, gdy zawierają taką samą liczbę identycz-
nych elementów umieszczonych w tej samej kolejności (porównanie każdych dwóch
odpowiadających sobie elementów musi dawać w rezultacie wartość true).
" W celu sprawdzenia, czy jeden stos jest mniejszy od drugiego, oba porównywane są
leksykograficznie. Więcej informacji zostalo umieszczonych na stronie 338 wraz
z opisem algorytmu o nazwie lexicographical_compare().
10.1.4. Klasa st>su defini>waneg> przez użytk>wnika
Standardowa klasa stack preferuje szybkość dzialania nad wygodę oraz bezpieczeństwo
użytkowania. Nie jest to tym, co zazwyczaj ja uważam za najlepsze podejście. Dlatego też
napisalem wlasną klasę stosu. Ma ona dwie zalety:
1. pop() zwraca kolejny element.
2. pop() oraz top() zwraca wyjątek w przypadku, gdy stos jest pusty.
Dodatkowo pominąlem wszystkie funkcje skladowe, które nie są niezbędne dla zwyklego
użytkownika stosu, jak chociażby operacje porównania. Moja klasa stosu zdefiniowana
zostala w następujący sposób:
//cont/Stack.hpp
/* ************************************************************
* Stack.hpp
* - bezpieczniejsza oraz bardziej wygodna klasa stosu
* ************************************************************/
#ifndef STACK_HPP
#define STACK_HPP
10.1. STOSY 407
#include
#include
template
class Stack {
protected:
std::deque c; // kontener zawierajacy elementy
public:
/* klasa wyjatku dla funkcji składowych pop() oraz top() wywolanych w przypadku pustego stosu
*/
class ReadEmptyStack : public std::exception {
public:
virtual const char* what() const throw() {
return "proba odczytania pustego elementu";
}
};
// liczba elementow
typename std::deque::size_type size() const {
return c.size();
}
// czy stos jest pusty?
bool empty() const {
return c.empty();
}
// umiesc element na stosie [ Pobierz całość w formacie PDF ]