Разлика между Stack и Heap

Stack срещу Heap

Stack е подреден списък, в който вмъкването и изтриването на елементи от списъка може да се извърши само в единия край, наречен върха. Поради тази причина, стекът се счита за структура от данни Last in First out (LIFO). Heap е специална структура на данни, която се основава на дървета и тя удовлетворява специално свойство, наречено heap свойство. Също така, една купчина е пълно дърво, което означава, че няма пропуски между листата на дървото, т.е. в пълно дърво всяко ниво се попълва, преди да се добави ново ниво към дървото и възлите в дадено ниво се запълват от Отляво надясно.

Какво е стек?

Както бе споменато по-рано, стека е структура от данни, в която елементите се добавят и премахват само от един край, наречен върх. Стековете позволяват само две основни операции, наречени push и pop. Операцията за натискане добавя нов елемент в горната част на стека. Поп операцията премахва елемент от горната част на стека. Ако стекът вече е пълен, когато се извършва натискане, той се счита за препълване на стека. Ако поп операция се извърши на вече празен стек, тя се счита за подтока на стека. Поради малкия брой операции, които биха могли да бъдат извършени на стек, той се счита за ограничена структура на данни. Освен това, според начина, по който са дефинирани push и pop операциите, е ясно, че елементите, добавени последно в стека, излизат първо от стека. Следователно стекът се счита за LIFO структура на данни.

Какво е Heap?

Както споменахме по-рано, купчината е пълно дърво, което удовлетворява свойството на купчината. Свойството Heap заявява, че ако y е дъщерна възел от x, стойността, съхранявана в възел x, трябва да бъде по-голяма или равна на стойността, съхранявана в възел y (т.е. стойност (x) ≥ стойност (y)). Това свойство предполага, че възелът с най-голяма стойност винаги би бил поставен в корена. Купа, конструирана с помощта на това свойство, се нарича max-heap. Има и друга разновидност на свойството heap, която посочва обратната страна на това. (т.е. стойност (x) ≤ стойност (y)). Това означава, че възелът с най-малката стойност винаги би бил поставен в корена, така наречен min-heap. Има широк спектър от операции, извършвани на купища, като намиране на минимум (в min-купи) или максимален (в max-купи), изтриване на минимум (в min-купи) или максимум (в max-купи), увеличаване (в max -heaps) или намаляващ (в мин. купи) и т.н..

Каква е разликата между Stack и Heap?

Основната разлика между стекове и купища е, че докато стекът е линейна структура на данни, купчината е нелинейна структура на данни. Stack е подреден списък, който следва свойството LIFO, докато heap е пълно дърво, което следва свойството heap. Освен това стека е ограничена структура на данни, която поддържа само ограничен брой операции като push and pop, докато heap поддържа широк спектър от операции, като намиране и изтриване на минимум или максимум, увеличаване или намаляване на ключа и сливане.