Стек: Засвар хоорондын ялгаа
Content deleted Content added
No edit summary |
No edit summary |
||
Мөр 1:
[[Image:Data stack.svg|thumb|200px|right|Стекийн энгийн дүрслэл]]
[[Компьютерийн шинжлэх ухаан]]-д '''Стек''' буюу '''Stack''' нь онцгой үүрэгтэй [[өгөгдлийн бүтэц|өгөгдлийн бүтцийн]] төрөл буюу цуглуулга юм. Стекийн үндсэн үйлдлүүд нь ''pop'' буюу элемент гаргах болон ''push'' буюу элемент нэмэх бөгөөд эдгээр үйлдлүүдийг стекийн орой гэх нэг төгсгөлд гүйцэтгэдэг. Стект хамгийн сүүлд орсон элемент хамгийн эхэнд гардаг учраас компьютерийн ухаанд стекийг [[LIFO]] (Last In First Out) бүтэц гэж бас нэрлэдэг. Push болон Pop аргын үндсэн шинж нь стекийн элемэнтүүдийн зүй тогтолтой байдгийг илэрхийлдэг. Стекээс элемент устгах нь нөгөө талаараа шинэ элемэнтэд орон зай бий болгож байгаа хэрэг юм. Ингэснээр хамгийн доор байгаа элемент нь хамгийн удаан оршин байх юм. Үндсэн үйлдлүүдээс гадна ''Peek'' буюу шагайх аргыг хэрэгжүүлсэн байдаг. Энэхүү арга нь хамгийн дээд талын элементийг устгалгүйгээр утгыг нь буцаадаг арга юм.
Стек нь багтаамж хязгаартай байх үед ашиглагддаг. Хэрэв стек нь дүүрэн ба дахиж элемент нэмэх зай байхгүй бол тухай стек нь overflow хэлбэрт шилжинэ. Pop арга нь стекийн хамгийн дээд талаас эхлэн элементүүдийг устгадаг ба устгасаар стекийн хамгийн доод талд ирэхэд өөр ямар нэгэн устгах элемэнтгүй болж стек нь underflow хэлбэрт шилжинэ.
Стек нь цөөхөн тооны арга ашигладаг хязгаарлагдмал өгөгдлийн бүтэц юм. Push болон Pop аргын үндсэн шинж нь стекийн элемэнтүүдийн зүй тогтолтой байдгийг илэрхийлдэг. Стекээс элемент устгах нь нөгөө талаараа шинэ элемэнтэд орон зай бий болгож байгаа хэрэг юм. Ингэснээр хамгийн доор байгаа элемент нь хамгийн удаан оршин байх юм.
Стек гэхийг бухал, овоолох, юмыг давхарлаж тавих гэж орчуулж болно.
==Түүх==
Стек гэдэг ойлголтыг анх 1946 онд Алан Тюринг нээжээ. Үүнээс 10 орчим жилийн дараа буюу 1955 онд Германы Клаус Самелсон болон Фридрих Бауэр нар стекийн тухай ойлголтыг мөн тусдаа нээж 1957 онд патент авчээ. Мөн л үүнтэй зэрэгцэн стекийг Австралийн [[Чарльз Леонард Хамблин]] 1957 оны эхний хагасд нээж байв.
==Хийсвэр тодорхойлолт==
Стек гэдэг нь компьютерийн шинжлэх ухааны нэгэн энгийн өгөгдлийн бүтэц бөгөөд үүнийг хийсвэр байдлаар илэрхийлэх боломжтой, эсвэл эсвэл шугаман жигсаалтын хэлбэрээр орой хэсгээсээ нэмж хасдаг байдалтайгаар тодорхойлж болно.
VDM буюу Vienna Development Method-аар стекийг тодорхойлох нь:
Function signatures:
init: -> Stack
push: N x Stack -> Stack
top: Stack -> (N U ERROR)
pop: Stack -> Stack
isempty: Stack -> Boolean
(үүнд N индекс нь элемэнтийг зааж (энэ тохиолдолд натурал тоог зааж байна), U индекс нь холбоог зааж байна)
Semantics:
top(init()) = ERROR
top(push(i,s)) = i
pop(init()) = init()
pop(push(i, s)) = s
isempty(init()) = true
isempty(push(i, s)) = false
==Нэмэлт арга==
Стекэд Push болон Pop аргаас гадна олон төрлийн өөр аргууд байдаг. Жишээ нь: "top of stack", "peek". Эдгээр аргууд нь стекийн хамгийн дээр байгаа элемэнтийг устгалгүйгээр харах боломжийг олгодог. Push болон Pop аргаар энэхүү үйлдлийг хийх боломжтой учир эдгээр аргууд нь тийм ч хэрэгтэй арга биш юм. Стек нь Underflow буюу элементгүй хоосон хэлбэрт байхад "Stack top" болон "Pop" аргууд нь адил үр дүнг үзүүлнэ.
==Хэрэгжүүлэлт==
| |||