Разлика между стека и купчината

2024 Автор: Mildred Bawerman | [email protected]. Последно модифициран: 2023-12-16 08:37

Stack vs Heap

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

Какво е Stack?

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

Какво е Heap?

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

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

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