Pytanie 1
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 |
A. kolejka
B. tablica
C. stos
D. drzewo binarne
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.
