Tablice dynamiczne
Obecnie zamierzamy zmienić kontrakt, obowiązujący w naszej implementacji stosu. Chcemy, aby nie zawierała już żadnego sztywnego ograniczenia co do ilości informacji, które będzie można umieścić na stosie. Chcemy, by można było zapisywać na nim tak dużo liczb, aż wypełnią one całą dostępną pamięć komputera.
Jednak nasz program nie może niepotrzebnie rezerwować ogromnych ilości pamięci ("na zapas"). Dlatego z początku nasz stos będzie zajmował stosunkowo mało miejsca, natomiast za każdym razem, gdy okaże się, że nie ma już na nim miejsca na kolejne liczby, powiększymy jego rozmiar o pewien stały czynnik, np. 2. Oczywiście nie będziemy już potrzebować metody IsFull sprawdzającej, czy na stosie jest jeszcze miejsce na kolejna liczbę. Poza tym interfejs stosu będzie dokładnie taki sam, jak w omówionej w poprzednim paragrafie implementacji, bazującej na "zwyczajnej" (a ściślej mówiąc: automatycznej) tablicy liczb całkowitych.
Nasza nowa implementacja stosu składa się z kilku nowych elementów. Przede wszystkim definiujemy prywatną funkcję pomocniczą Grow, wykorzystywaną wewnętrznie przez stos do powiększania swojego rozmiaru w sytuacji, gdy brakuje już na nim miejsca na nowe liczby. Informację o bieżącej pojemności stosu przechowujemy prywatnej zmiennej _capacity. Aby ułatwić sobie testowanie naszej nowej implementacji przyjmiemy, że początkowa pojemność stosu wynosi 1 -- dzięki temu stos powiększy się niemal natychmiast po uruchomieniu programu.
const int initStack = 1;
class IStack
{
public:
IStack (); // utwórz pusty stos
~IStack ();
void Push ( int i ); // dodaj liczbę na szczyt stosu
int Pop (); // zdejmij liczbę ze szczytu stosu
int Top () const; // co jest na szczycie stosu?
bool IsEmpty () const; // czy stos jest pusty?
private:
void Grow ();
int * _arr; // adres pierwszego elementu tablicy
int _capacity; // bieżący rozmiar tablicy
int _top; // ilość elementów na stosie
};
|
Proszę zwrócić uwagę na to, że tym razem zmienną _arr zadeklarowano nie jako nazwę tablicy, lecz jako wskaźnik do liczby całkowitej. Tablicę tworzoną dynamicznie na stercie za pośrednictwem operatora new musimy zadeklarować jako zmienną wskaźnikową.
Tablicę o domniemanym rozmiarze initStack tworzymy na stercie w konstruktorze, a usuwamy w destruktorze klasy IStack:
IStack::IStack ()
: _top (0), _capacity (initStack)
{
_arr = new int [initStack]; // utwórz tablicę (przydziel pamięć) na stercie
}
IStack::~IStack ()
{
delete []_arr; // usuń tablicę z pamięci komputera (zwolnij pamięć)
}
|
W ten sposób wprowadziliśmy nowy rodzaj zależności pomiędzy obiektami. Każdy obiekt klasy IStack nie tylko ma dostęp do tablicy _arr, ale wręcz jest jej właścicielem. W języku C++ relację A jest właścicielem B wyrażamy poprzez użycie zmiennej wskaźnikowej, wskazującej na B. Mówmy, że obiekt A jest właścicielem obiektu B, jeżeli A jest odpowiedzialny za usunięcie obiektu B (i zwolnienie w ten sposób wszystkich zasobów, przydzielonych B). Temat ten przedstawimy bardziej szczegółowo podczas omawiana technik zarządzania zasobami.
Rys. 1. Relacja "A jest właścicielem B".
Załóżmy, że w pewnej chwili stos jest już całkowicie zapełniony. W jaki sposób można umieścić na nim jeszcze jedną liczbę? Odpowiedź jest prosta: wywołując specjalną, prywatną metodę Grow, która powiększy rozmiar tablicy _arr. Po wykonaniu tej czynności można powrócić do realizacji standardowej implementacji metody Push:
void IStack::Push (int i)
{
assert (_top <= _capacity);
if (_top == _capacity)
Grow ();
_arr [_top] = i;
++_top;
}
|
Przyjrzyjmy się bliżej działaniu metody Grow. Realizowany przez nią algorytm składa się z pięciu kroków:
void IStack::Grow ()
{
// komunikat diagnostyczny -- usunąć w ostatecznej implementacji!!!
cout << "Podwajanie stosu o rozmiarze: " << _capacity << ".\n";
// utwórz na stercie nową tablicę
int * arrNew = new int [2 * _capacity];
// skopiuj wszystkie elementy
for (int i = 0; i < _capacity; ++i)
arrNew [i] = _arr [i];
_capacity = 2 * _capacity;
// zwolnij pamięć, zajmowaną przez starą tablicę
delete []_arr;
// zapisz adres nowej tablicy w składowej _arr
_arr = arrNew;
}
|
Instrukcja przypisania
_arr = arrNew; |
powoduje modyfikację wartości zmiennej wskaźnikowej. Jej efektem jest zmiana obiektu, wskazywanego przez _arr -- po jej wykonaniu zmienna _arr wskazuje bowiem na ten sam obiekt, na który w danej chwili wskazuje zmienna arrNew. Jest to jedyna operacja, której nie można wykonać, stosując referencje. Zwróćmy uwagę na to, że zastosowanie operatora przypisania (=) do zmiennych wskaźnikowych nie powoduje zmiany zawartości wskazywanych przez nie obiektów. Żeby zmienić zawartość obiektów, musielibyśmy posłużyć się operatorem wyłuskania,
*_arr = *arrNew; |
lub operatorem indeksowania
_arr [0] = arrNew [0]; |
Implementacja pozostałych metod nie nastręcza specjalnych trudności. Koniecznie zwróćmy jednak uwagę na to, że zmienną _arr posługujemy się tak, jak nazwą tablicy, mimo zadeklarowania jej jako zmiennej wskaźnikowej.
int IStack::Pop ()
{
// Nie wolno pobierać liczb z pustego stosu
assert (_top > 0);
--_top;
return _arr [_top];
}
int IStack::Top () const
{
// Metodę Top wolno wywoływać tylko wtedy, gdy stos nie jest pusty
assert (_top > 0);
return _arr [_top - 1];
}
bool IStack::IsEmpty () const
{
assert (_top >= 0); // sprawdzamy, czy zmienna _top spełnia kontrakt stosu
return _top == 0;
}
|
Oto prosty program testowy, w którym wymusza się kilkakrotne powiększanie rozmiaru tablicy _arr.
int main ()
{
IStack stack;
for (int i = 0; i < 5; ++i)
{
cout << "Push " << i << endl;
stack.Push (i);
}
for (int j = 0; j < 5; ++j)
{
cout << "Pop " << stack.Pop () << endl;
}
}
|