Stos (informatyka)
Stos jest jedną z najważniejszych struktur danych w informatyce. Aby zrozumieć jak działa stos, pomyśl o talii kart do gry, która jest zakryta. Możemy tylko łatwo uzyskać dostęp do karty, która jest na wierzchu. Kiedy chcemy spojrzeć na wierzchnią kartę, możemy zrobić dwie rzeczy: możemy ją podejrzeć, ale pozostawić na stosie, lub możemy ją odczepić. Kiedy odrywamy górny obiekt, zdejmujemy go ze stosu. Jeśli chcemy dodać kolejną kartę na wierzch stosu, to ją przesuwamy.
Stos jest nazywany kolekcją typu LIFO (last-in-first-out). Oznacza to, że ostatnia rzecz, którą dodaliśmy (wepchnęliśmy) jest pierwszą rzeczą, która zostaje wyciągnięta (wysunięta). Jeśli ostatnią kartą, którą położyliśmy na naszym stosie kart był as, to pierwszą kartą, którą ściągnęliśmy z wierzchu jest ten sam as.
Dwie akcje na stosie: push i pop.
Historia
Stos został po raz pierwszy zaproponowany w 1955 r., a następnie opatentowany w 1957 r. przez Niemca Friedricha L. Bauera. Ta sama koncepcja została opracowana niezależnie, mniej więcej w tym samym czasie, przez Australijczyka Charlesa Leonarda Hamblina.
Inne operacje
W nowoczesnych językach komputerowych, stos jest zwykle implementowany z większą liczbą operacji niż tylko "push" i "pop". Niektóre implementacje posiadają funkcję, która zwraca aktualną długość stosu. Inną typową operacją pomocniczą jest "top" (znana również jako "peek"), która może zwrócić bieżący najwyższy element stosu bez jego usuwania. Inną popularną operacją jest "dup", która tworzy kopię elementu na szczycie stosu.
Powiązane strony
- Maszyna do układania w stos
