Różnica między stosem a stosem

Stack vs Heap

Stos to uporządkowana lista, w której wstawianie i usuwanie elementów listy można wykonać tylko na jednym końcu zwanym górną. Z tego powodu stos jest uważany za strukturę danych Last in First out (LIFO). Sterta to specjalna struktura danych oparta na drzewach i spełniająca specjalną właściwość o nazwie właściwość sterta. Ponadto sterta jest kompletnym drzewem, co oznacza, że ​​nie ma przerw między liśćmi drzewa, tj. W pełnym drzewie każdy poziom jest wypełniany przed dodaniem nowego poziomu do drzewa, a węzły na danym poziomie są wypełniane z z lewej na prawą.

Co to jest stos?

Jak wspomniano wcześniej, stos jest strukturą danych, w której elementy są dodawane i usuwane tylko z jednego końca zwanego górną. Stosy umożliwiają tylko dwie podstawowe operacje zwane push i pop. Operacja wypychania dodaje nowy element na górze stosu. Operacja pop usuwa element ze szczytu stosu. Jeśli stos jest już pełny, po wykonaniu operacji wypychania uważa się go za przepełnienie stosu. Jeśli operacja pop jest wykonywana na już pustym stosie, jest to uważane za niedopełnienie stosu. Ze względu na niewielką liczbę operacji, które można wykonać na stosie, jest to uważane za ograniczoną strukturę danych. Ponadto, zgodnie ze sposobem, w jaki zdefiniowane są operacje push i pop, jasne jest, że elementy, które zostały dodane do stosu jako ostatnie, najpierw wychodzą ze stosu. Dlatego stos jest uważany za strukturę danych LIFO.

Co to jest Kupa?

Jak wspomniano wcześniej, sterta jest kompletnym drzewem, które spełnia właściwość sterty. Właściwość Heap 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 będzie umieszczony w katalogu głównym. Sterty zbudowane przy użyciu tej właściwości są nazywane stertą maksymalną. Istnieje inna odmiana właściwości sterty, która podaje odwrotność tego. (tj. wartość (x) ≤ wartość (y)). Oznacza to, że węzeł o najmniejszej wartości zawsze będzie umieszczony w katalogu głównym, tak zwany min-stos. Istnieje szeroki zakres operacji wykonywanych na stosach, takich jak wyszukiwanie minimum (w min-stertach) lub maksimum (w maks. Stertach), usuwanie minimum (w min-stertach) lub maksimum (w maks. Stertach), zwiększanie (w maks. -heaps) lub klawisz malejący (w min-hałdach itp.).

Jaka jest różnica między stosem a stosem?

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ą podążającą za właściwością LIFO, natomiast sterta jest kompletnym drzewem podążającym za właściwością sterty. Ponadto stos jest ograniczoną strukturą danych, która obsługuje tylko ograniczoną liczbę operacji, takich jak push i pop, podczas gdy sterta obsługuje szeroki zakres operacji, takich jak wyszukiwanie i usuwanie minimum lub maksimum, zwiększanie lub zmniejszanie klucza i scalanie.