Stos kontra sterta
Stos to uporządkowana lista, w której wstawianie i usuwanie elementów listy może odbywać się tylko na jednym końcu zwanym górą. Z tego powodu stos jest uważany za strukturę danych Last in First out (LIFO). Sterta to specjalna struktura danych oparta na drzewach, która spełnia specjalną właściwość zwaną właściwością sterty. Również sterta jest kompletnym drzewem, co oznacza, że nie ma przerw między liśćmi drzewa tj. w kompletnym drzewie każdy poziom jest wypełniany przed dodaniem nowego poziomu do drzewa, a węzły na danym poziomie są wypełniane z od lewej do prawej.
Co to jest stos?
Jak wspomniano wcześniej, stos to struktura danych, w której elementy są dodawane i usuwane tylko z jednego końca zwanego szczytem. Stosy umożliwiają tylko dwie podstawowe operacje zwane push i pop. Operacja push dodaje nowy element na górę stosu. Operacja pop usuwa element ze szczytu stosu. Jeśli stos jest już pełny, podczas wykonywania operacji wypychania jest to traktowane jako przepełnienie stosu. Jeśli operacja pop jest wykonywana na już pustym stosie, jest ona uważana za niedopełnienie stosu. Ze względu na niewielką liczbę operacji, które można wykonać na stosie, jest on uważany za strukturę danych o ograniczonym dostępie. Dodatkowo, zgodnie ze sposobem zdefiniowania operacji push i pop, jasne jest, że elementy, które zostały dodane do stosu jako ostatnie, wychodzą ze stosu jako pierwsze. Dlatego stos jest uważany za strukturę danych LIFO.
Co to jest sterta?
Jak wspomniano wcześniej, sterta jest kompletnym drzewem spełniającym właściwość sterty. Właściwość sterty stwierdza, że jeśli y jest węzłem potomnym x, to wartość przechowywana w węźle x powinna być większa lub równa wartości przechowywanej w węźle y (tj. value(x) ≥ value(y)). Ta właściwość implikuje, że węzeł o największej wartości będzie zawsze umieszczany u korzenia. Sterta skonstruowana przy użyciu tej właściwości nazywana jest stertą max. Istnieje inna odmiana właściwości sterty, która stanowi odwrotność tego. (tj. wartość(x) ≤ wartość(y)). Oznacza to, że węzeł z najmniejszą wartością byłby zawsze umieszczany u korzenia, co nazywamy kopcem min. Istnieje szeroki zakres operacji wykonywanych na stertach, takich jak znajdowanie minimum (w kopcach min) lub maksimum (w kopcach max), usuwanie minimum (w kopcach min) lub maksimum (w kopcach max), zwiększanie (w kopcach max). - sterty) lub klawisz zmniejszania (w min stertach) itp.
Jaka jest różnica między stosem a stertą?
Główna różnica między stosami a stertami polega na tym, że podczas gdy stos jest liniową strukturą danych, sterta jest nieliniową strukturą danych. Stos jest uporządkowaną listą, która następuje po właściwości LIFO, podczas gdy sterta jest kompletnym drzewem, które następuje po właściwości sterty. Co więcej, stos to ograniczona struktura danych, która obsługuje tylko ograniczoną liczbę operacji, takich jak push i pop, podczas gdy sterta obsługuje szeroki zakres operacji, takich jak znajdowanie i usuwanie minimum lub maksimum, zwiększanie lub zmniejszanie klucza i scalanie.
