Jaką strukturę danych można zrealizować, korzystając jedynie z wymienionych poniżej metod:
push(arg) – dodaje element |
pop() – usuwa ostatnio dodany element |
peek() – zwraca ostatnio dodany element bez usuwania |
isEmpty() – sprawdza czy istnieją dane w strukturze |
Stos to jedna z najbardziej podstawowych i jednocześnie użytecznych struktur danych. Wszystkie wymienione metody - push, pop, peek oraz isEmpty - są klasycznymi operacjami definiującymi właśnie stos (czyli tzw. LIFO, czyli Last-In-First-Out). Oznacza to, że ostatni element, który został dodany do stosu, będzie pierwszym usuniętym. Z mojego doświadczenia wynika, że stosy są bardzo często wykorzystywane w praktyce, na przykład przy realizacji algorytmów rekurencyjnych (zarówno w kodzie, jak i na niższym poziomie, jak stos wywołań funkcji w pamięci programu), co jest zgodne ze standardami języków programowania, takich jak C, Java czy Python. W praktycznych zastosowaniach stosów używa się m.in. przy sprawdzaniu poprawności nawiasów w wyrażeniach matematycznych, przy parsowaniu kodu, cofnięciach operacji w edytorach tekstu czy realizacji algorytmu przeszukiwania w głąb (DFS). Co ciekawe, stos można łatwo zaimplementować zarówno na tablicach dynamicznych, jak i na listach jednokierunkowych. Dobre praktyki branżowe zalecają, aby stos wykorzystywać zawsze tam, gdzie potrzebny jest szybki dostęp do ostatnio dodanego elementu i nie zachodzi potrzeba dostępu w inny sposób. Moim zdaniem, zrozumienie działania stosu to fundament dla każdego, kto serio podchodzi do programowania i algorytmiki.
Pomyłka przy tym pytaniu jest dość zrozumiała, bo wiele osób myli dostępne operacje ze strukturą, którą zamierzają użyć. Metody push, pop, peek i isEmpty wskazują wyraźnie na stos, jednak nietrudno ulec wrażeniu, że można je zastosować także w tablicy czy nawet kolejce. Problem w tym, że tablica daje bezpośredni dostęp do dowolnego elementu (indeksowanie), a tych operacji tutaj nie mamy — bez get(index) czy set(index, value) nie da się użyć jej w typowy sposób, więc zamienia się bardziej w zwykły pojemnik, niż prawdziwą tablicę. Kolejka natomiast wymaga operacji typu enqueue (dodanie na koniec) i dequeue (usunięcie z początku), czyli tzw. FIFO (First-In-First-Out), czego tutaj nie zrealizujesz samymi push i pop - one zawsze odnoszą się do końca struktury, nie do jej początku. Drzewo binarne to już zupełnie inna para kaloszy: wymaga rozbudowanych operacji na węzłach i gałęziach, a dostępne tu metody nawet nie zbliżają się do tego typu funkcjonalności — nie ma dodawania dzieci, przeszukiwania czy sprawdzania położenia w strukturze. Typowym błędem jest też utożsamianie samych nazw operacji z ogólną strukturą danych, bez zastanowienia się, jaki dokładnie model dostępu do danych one umożliwiają. Warto zapamiętać, że jeśli dostępne masz tylko push, pop, peek i isEmpty, to jesteś w świecie stosu - i tylko jego.