Stos vs Heap
Stos to uporządkowana lista, na której wstawianie i usuwanie elementów listy może odbywać się tylko na jednym końcu zwanym wierzchołkiem. Z tego powodu stos jest traktowany jako struktura danych Last in First Out (LIFO). Sterta to specjalna struktura danych oparta na drzewach i spełniająca 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 całym 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 wierzchołkiem. Stosy pozwalają tylko na dwie podstawowe operacje zwane push i pop. Operacja wypychania dodaje nowy element na górę stosu. Operacja pop usuwa element ze szczytu stosu. Jeśli stos jest już pełny, wykonanie operacji wypychania jest traktowane jako przepełnienie stosu. Jeśli operacja pop jest wykonywana na już pustym stosie, jest to traktowane jako niedomiar stosu. Ze względu na małą liczbę operacji, które można wykonać na stosie, jest on traktowany jako ograniczona struktura danych. Dodatkowo, zgodnie ze sposobem zdefiniowania operacji push i pop, jasne jest, że elementy, które zostały dodane jako ostatnie w stosie, wychodzą ze stosu jako pierwsze. Dlatego stos jest uważany za strukturę danych LIFO.
Co to jest Heap?
Jak wspomniano wcześniej, sterta jest pełnym drzewem, które spełnia 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. Wartość (x) ≥ wartość (y)). Ta właściwość oznacza, że węzeł o największej wartości zawsze byłby umieszczony w katalogu głównym. Sterta skonstruowana przy użyciu tej właściwości nazywana jest stertą maksymalną. Istnieje inna odmiana właściwości sterty, która stanowi odwrotność tego. (tj. wartość (x) ≤ wartość (y)). Oznacza to, że węzeł o najmniejszej wartości zawsze byłby umieszczany w korzeniu, zwany w ten sposób stertą min. Istnieje szeroki zakres operacji wykonywanych na stertach, takich jak znajdowanie minimum (w stertach min) lub maksimum (w stertach max), usuwanie minimum (w stertach min) lub maksimum (w stertach maksymalnych),klawisz zwiększania (w maksymalnych stosach) lub zmniejszania (w minimalnych stosach) itp.
Jaka jest różnica między Stack i Heap?
Główna różnica między stosami i stertami polega na tym, że podczas gdy stos jest liniową strukturą danych, sterta jest nieliniową strukturą danych. Stos jest uporządkowaną listą występującą po właściwości LIFO, podczas gdy sterta jest kompletnym drzewem, które następuje po właściwości sterty. Ponadto stos jest ograniczoną strukturą danych, która obsługuje tylko ograniczoną liczbę operacji, takich jak wypychanie 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.
