Stack vs Heap
Стек нь жагсаалтын зүйлүүдийг оруулах, устгахыг зөвхөн дээд талын нэг төгсгөлд хийх боломжтой эрэмбэлэгдсэн жагсаалт юм. Энэ шалтгааны улмаас стекийг хамгийн сүүлд гарсан (LIFO) өгөгдлийн бүтэц гэж үздэг. Нуруулга гэдэг нь мод дээр суурилсан тусгай өгөгдлийн бүтэц бөгөөд нуруулдан үл хөдлөх хөрөнгө гэж нэрлэгддэг тусгай шинж чанарыг хангадаг. Мөн овоолго нь бүрэн мод бөгөөд энэ нь модны навчны хооронд ямар ч цоорхой байхгүй, өөрөөр хэлбэл бүрэн модонд шинэ түвшин нэмэхээс өмнө түвшин бүрийг дүүргэж, өгөгдсөн түвшний зангилаануудыг дүүргэдэг гэсэн үг юм. зүүнээс баруун тийш.
Стек гэж юу вэ?
Өмнө дурьдсанчлан стек гэдэг нь дээд хэсэг гэж нэрлэгддэг зөвхөн нэг төгсгөлөөс элементүүдийг нэмж хасдаг өгөгдлийн бүтэц юм. Стекүүд нь түлхэх, поп гэсэн хоёр үндсэн үйлдлийг зөвшөөрдөг. Түлхэх үйлдэл нь стекийн дээд хэсэгт шинэ элемент нэмнэ. Поп үйлдэл нь стекийн дээд хэсгээс элементийг устгадаг. Хэрэв стек аль хэдийн дүүрсэн бол түлхэх үйлдлийг гүйцэтгэх үед үүнийг стек халилт гэж үзнэ. Хэрэв поп үйлдлийг аль хэдийн хоосон стек дээр гүйцэтгэсэн бол стекийн дутуу урсгал гэж үзнэ. Стек дээр хийж болох үйлдлүүдийн тоо цөөн байдаг тул үүнийг хязгаарлагдмал өгөгдлийн бүтэц гэж үздэг. Нэмж хэлэхэд, түлхэх болон поп үйлдлүүдийг тодорхойлсон арга барилын дагуу стект хамгийн сүүлд нэмэгдсэн элементүүд стекээс эхлээд гарах нь тодорхой байна. Тиймээс стекийг LIFO өгөгдлийн бүтэц гэж үздэг.
Heap гэж юу вэ?
Өмнө дурьдсанчлан овоо бол овоолгын шинж чанарыг хангасан бүрэн мод юм. Heap шинж чанар нь хэрэв y нь x-ийн хүүхэд зангилаа бол x зангилаанд хадгалагдсан утга нь y зангилаанд хадгалагдсан утгаас их буюу тэнцүү байх ёстой (жишээ нь: утга(x) ≥ утга(y)) байх ёстой. Энэ шинж чанар нь хамгийн их утгатай зангилаа үргэлж үндэс дээр байрлана гэсэн үг юм. Энэ шинж чанарыг ашиглан босгосон овоолгыг max-heap гэж нэрлэдэг. Үүний урвуу талыг илэрхийлсэн овоолгын шинж чанарын өөр нэг хувилбар бий. (өөрөөр хэлбэл утга(x) ≤ утга(y)). Энэ нь хамгийн бага утгатай зангилаа үргэлж үндэс дээр байрлана гэсэн үг бөгөөд үүнийг min-heap гэж нэрлэдэг. Хамгийн бага (мин-овоолтоор) эсвэл хамгийн их (макс-овоолтоор) олох), хамгийн бага (мин-овоолтоор) эсвэл хамгийн ихийг (макс-овоолтоор) устгах, нэмэгдүүлэх (макс) гэх мэт олон төрлийн үйлдлүүд овоолго дээр хийгддэг. -овоо) эсвэл багасгах (мин-овоолон) товчлуур гэх мэт.
Стек болон овоо хоёрын ялгаа нь юу вэ?
Стек болон овоо хоёрын гол ялгаа нь стек нь шугаман өгөгдлийн бүтэц байхад овоо нь шугаман бус өгөгдлийн бүтэц юм. Stack нь LIFO шинж чанарыг дагасан эрэмбэлэгдсэн жагсаалт бөгөөд овоо нь овоолгын шинж чанарыг дагасан бүрэн мод юм. Цаашилбал, стек нь хязгаарлагдмал өгөгдлийн бүтэц бөгөөд түлхэх болон поп зэрэг хязгаарлагдмал тооны үйлдлийг дэмждэг бол овоо нь хамгийн бага эсвэл дээд хэмжээг олох, устгах, түлхүүрийг нэмэгдүүлэх, багасгах, нэгтгэх зэрэг өргөн хүрээний үйлдлүүдийг дэмждэг.
