Stos i sterta w C++

We współczesnym programowaniu główny akcent jest położony na używanie danego języka oraz jego frameworków i bibliotek. Zawierają one gotowe klasy i metody wyręczając programistę, aby nie musiał całej aplikacji budować od podstaw. Nie mniej ważną rzeczą jest jednak umiejętność implementacji struktur danych, która pozwala zrozumieć ich dzialanie. Wśród nich ważne miejsce zajmują stos (ang. stack) oraz sterta (ang. heap) zwana także w polskiej literaturze także stogiem lub kopcem.

Stos

Możliwości implementacyjnych jest wiele. Jeżeli potrzebujemy specjalnego stosu, to możemy go łatwo zaimplementować. Stos jest kolejką typu LIFO (last in first out), co oznaczą, że dostęp do elementów jakie on przechowuje jest jedynie od wierzchołka, czyli pierwszego wolengo miejsca na stosie. Aby położyć element na wierchołku stosu potrebn jest funkcja push(a), gdzie a jest elementem. Pobranie ze stosu dokonuje się poprzez funkcję nazywaną zwyczajowo pop(a). Każda z tych funkcji powinna oczywiście zwracać kod błędu w przypadku wystąpienia sytuacji niepożądanej. Taką sytuacją może być np. próba pobrania ze stosu elementu w sytucji, gdy stos jest pusty, albo też próba odłożenia na stosie elementu, gdy stos jest już pełen (to jest stack overflow). Prosty przykład implementacji stosu może wyglądać tak:

#include<iostream>

using namespace std;

const int STACK_LENGTH = 20;

enum state{
	STACK_EMPTY = 0,
	STACK_FULL = 1,
	OK = 2;
}

template<class Type> class STACK{
	
private:
	Type t[STACK_LENGTH];
	int stack_peak;
public:
	STACK(){
		stack_peak = 0;
	}
	
	void clear(){
		stack_peak = 0;
	}
	
	int push(Type a);
	int pop (Type&amp; a);
	int StackState();
}

Nie bez powodu użyłem tu klasy szablonowej , ponieważ pozawala ona na uniwersalne zastosowanie takiego stosu podczas wywołania klasy STACK jedynie podajemy typ danych np:

STACK<string> // dla napisów
STACK<double> // dla liczb zmiennoprzecinkowych

Sterta

Sterta jest strukturą o innej filozofii działania niż stos, choć też operuje na globalnie nieuporządkowanym zbiorze danych. Lokanie elementy sterty są uporządkowane w pewien sposób, ponieważ jest ona drzewem binarnym. Drzewo to sterta realizuje poprzez ustawianie elementów od jego góry (korzenia) oraz od lewej strony do prawej. Największy element znajduje się zatem zawsze na pierwszym miejscu sterty. Implementacja sterty może wyglądać tak:

#include<iostream>

using namespace std;

class Heap{

private:
	int* t;
	int count; // liczba elementów

public:
	Heap(int elMax){
	t = new int[elMax + 1];
	count = 0;
	}
	
	void push(int a);
	int handle();
	void moveUp();
	void moveDown();
	void write();
}

Można także użyć gotowej klasy, zaimplementowanej w bibliotece STL języka o czym będzie mowa dalej.

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *