Стек пен үйме
Стек – тізім элементтерін кірістіру және жою тек жоғарғы деп аталатын бір ұшында орындалатын реттелген тізім. Осы себепті стек «Соңғы шыққан бірінші шығады» (LIFO) деректер құрылымы ретінде қарастырылады. Үйме - ағаштарға негізделген арнайы деректер құрылымы және ол үйме сипаты деп аталатын арнайы сипатты қанағаттандырады. Сондай-ақ, үйме - бұл толық ағаш, яғни ағаштың жапырақтары арасында бос орындар жоқ, яғни толық ағашта ағашқа жаңа деңгей қоспас бұрын әр деңгей толтырылады және берілген деңгейдегі түйіндер келесіден толтырылады. солдан оңға қарай.
Стек дегеніміз не?
Бұрын айтылғандай, стек – элементтер жоғарғы деп аталатын бір ұшынан ғана қосылатын және жойылатын деректер құрылымы. Стектер push және pop деп аталатын екі негізгі әрекетке ғана мүмкіндік береді. Басу әрекеті стектің жоғарғы жағына жаңа элемент қосады. Қалқымалы әрекет элементті стектің жоғарғы жағынан жояды. Стек әлдеқашан толы болса, итеру әрекеті орындалғанда, ол стектің толып кетуі ретінде қарастырылады. Қалқымалы әрекет әлдеқашан бос стекте орындалса, ол стектің төмен ағыны ретінде қарастырылады. Стекте орындалатын операциялар санының аздығына байланысты ол шектеулі деректер құрылымы ретінде қарастырылады. Оған қоса, push және pop әрекеттерінің анықталу тәсіліне сәйкес стекке соңғы қосылған элементтер алдымен стектен шығатыны анық. Сондықтан стек LIFO деректер құрылымы ретінде қарастырылады.
Үйме дегеніміз не?
Бұрын айтылғандай, үйме - үйме сипатын қанағаттандыратын толық ағаш. Үйме сипаты, егер y x-тің еншілес түйіні болса, онда x түйінінде сақталған мән y түйінінде сақталған мәннен үлкен немесе оған тең болуы керек (яғни, мән(x) ≥ мәні(y)). Бұл сипат ең үлкен мәнге ие түйін әрқашан түбірге орналастырылатынын білдіреді. Осы сипатты пайдаланып құрастырылған үйме max-үйме деп аталады. Мұның кері мәнін көрсететін үйме сипатының басқа нұсқасы бар. (яғни мән(x) ≤ мән(y)). Бұл ең кіші мәні бар түйін әрқашан түбірге орналастырылатынын білдіреді, осылайша мин-үйме деп аталады. Минималды (мин-үймелерде) немесе максимумды (максималды) табу, минималды жою (мин-үймелерде) немесе максимумды (макс-үймелерде), ұлғайту (макс) сияқты үймелерде орындалатын операциялардың кең ауқымы бар. -үйінділер) немесе азайтатын (мин-үйінділермен) перне, т.б.
Стек пен үйменің айырмашылығы неде?
Стектер мен үймелердің негізгі айырмашылығы мынада: стек сызықтық деректер құрылымы болса, үйме сызықтық емес деректер құрылымы болып табылады. Стек - бұл LIFO сипатынан кейінгі реттелген тізім, ал үйме - үйме сипатынан кейінгі толық ағаш. Сонымен қатар, стек - бұл push және pop сияқты әрекеттердің шектеулі санын ғана қолдайтын шектеулі деректер құрылымы, ал үйме ең аз немесе максимумды табу және жою, кілтті үлкейту немесе азайту және біріктіру сияқты операциялардың кең ауқымын қолдайды.
