Która struktura danych może być zaimplementowana przy wykorzystaniu jedynie wymienionych metod?

Wyjaśnienie

Przedstawione w pytaniu metody (push(arg), pop(), peek() oraz isEmpty()) są charakterystyczne dla implementacji struktury danych znanej jako stos (ang. stack). Stos działa zgodnie z zasadą LIFO (Last In, First Out), co oznacza, że element, który został dodany jako ostatni, zostanie usunięty jako pierwszy.

Analiza poszczególnych metod:

• push(arg): Dodaje nowy element na wierzchołek (szczyt) stosu.
• pop(): Usuwa element z wierzchołka stosu, jednocześnie zwracając jego wartość.
• peek(): Zwraca wartość elementu znajdującego się na wierzchołku stosu, ale go nie usuwa.
• isEmpty(): Sprawdza, czy stos nie zawiera żadnych elementów (czy jest pusty).

Dlaczego poprawną odpowiedzią jest stos?

Stos jest jedyną strukturą danych spośród wymienionych, która do swojej podstawowej i pełnej implementacji wykorzystuje wyłącznie te cztery metody. Ograniczają one dostęp tylko do elementu na szczycie, co jest fundamentalną cechą stosu.

Dlaczego pozostałe odpowiedzi są nieprawidłowe?

• A. Tablica: Umożliwia bezpośredni dostęp do każdego elementu za pomocą jego indeksu (np. tablica[i]). Wymaga to operacji, których wymienione metody nie zapewniają.

• C. Kolejka FIFO (First In, First Out): Działa na zasadzie "pierwszy wszedł, pierwszy wyszedł". Wymaga dwóch oddzielnych operacji:

  • enqueue: dodawanie elementu na koniec kolejki.
  • dequeue: usuwanie elementu z początku kolejki. Metody stosu (push i pop) operują tylko na jednym końcu struktury (na szczycie).

• D. Drzewo binarne: Jest to złożona, nieliniowa struktura danych. Jej obsługa wymaga operacji do nawigacji między węzłami (np. przesuwanie się do lewego lub prawego "dziecka") oraz wstawiania elementów w określonym porządku, czego podane metody nie umożliwiają.

Przykład działania stosu:

Poniższy przykład ilustruje, jak zmienia się zawartość stosu po wykonaniu kolejnych operacji: