Struktury danych/Stosy

Z Wikibooks, biblioteki wolnych podręczników.

[edytuj] Zastosowanie

Stos jest dobrym rozwiązaniem, gdy gromadząc jakieś dane przeprowadzamy operacje najpierw na tych najnowszych (ostatnio dodanych), a gdy te nie są nam już potrzebne, to zabieramy się za te nieco starsze.

Dobrym przykładem jest tu stos talerzy, ułożonych jeden na drugim, które - załóżmy - przypadło nam zmywać. W pierwszej kolejności zabierzemy się za talerz na samej górze. Gdy już go wyczyścimy to odłożymy na bok i weźmiemy następny - tak do ostatniego który jest na samym dnie stosu.

[edytuj] Opis

Zważywszy na kolejność dodawania i usuwania elementów ze stosu, struktura ta określana jest jako LIFO (ang. Last In First Out - Ostatni na wejściu, Pierwszy na wyjściu).

Schemat
(element 1 dodany został jako pierwszy, następnie dodano 2, 3 .. n

[edytuj] Operacje na stosie

• push() - wrzuca nowy element na szczyt stosu
• pop() - zdejmuje element ze szczytu stosu zwracając jego wartość

[edytuj] Implementacja

Do implementacji stosu o stałym rozmiarze n wystarczy n-elementowa tablica i jedna zmienna, która będzie przetrzymywać aktualną liczbę elementów.

[edytuj] Python

Do emulacji działania stosu wykorzystamy listę i dwie jej metody: append() oraz pop().

stos = [] # tworzymy listę

stos.append(1) # metoda append() działa identycznie jak opisywany push()
stos.append(2)
stos.append(3)

# w tym momencie na stosie są 3 elementy
print "Na stosie sa " + str(len(stos)) + " elementy"

x = stos.pop() # zdejmujemy przed chwilą dodane elementy ze stosu
y = stos.pop()
z = stos.pop()

[edytuj] C/C++

#define STOS_MAX 10 // stos 10-elementowy

int stos[STOS_MAX];
szczyt=0;

push(element) {
	if(szczyt < STOS_MAX) {
		/* wrzuć na stos */
		stos[szczyt] = element;
		szczyt++;
	}
	else {
		/* stos jest już pełny */
		...
	}
}

pop() {
	if(szczyt != 0) {
		/* zdejmij ze stosu */
		szczyt--;
		return stos[szczyt];
	}
	else {
		/* stos jest już pusty */
		...
	}

}

[edytuj] Pascal (FPC)

const 
	StosMax = 10; //Stos 10 elementowy
	
var
	stos : array[1..StosMax] of integer;
	szczyt : integer = 0; 
	
procedure push(element : integer);
begin
	if szczyt < StosMax then
		begin
			//wrzuć na stos
			stos[szczyt] := element;
			Inc(szczyt);
                        stos:=0;
		end
	else
		begin
			//Stos jest pełny
		end;
end;
	
function pop : integer;
begin
	if szczyt <> 0 then 
		begin
			//zdejmij ze stosu
			Inc(szczyt);
			pop := stos[szczyt];
		end
	else
		begin
			//Stos jest pusty
		end;
end;

[edytuj] Dodatkowe informacje

[edytuj] Ćwiczenia

Do zrobienia: Rozwinąć opis Implementacja w języku Pascal Implementacja w języku Java