Стек

Стекийн энгийн дүрслэл

Компьютерийн шинжлэх ухаан-д Стек буюу 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" аргууд нь адил үр дүнг үзүүлнэ.

Хэрэгжүүлэлт

Стекийг олон аргаар нэвтрүүлж болох боловч ихэвчлэн шугаман массив, эсвэл нэг холбоост жагсаалтыг ашиглана.

Шугаман массив

Массив ашиглан зохион байгуулсан стек статикаар тодорхойлогддог.

Холбоост жагсаалт

Стекийг массиваар илэрхийлэх үед хэмжээ нь тогтмол тодорхойлогддог учир өөрчлөх боломжгүй, зөвхөн нийт өгөгдлийн хэмжээг гарцаагүй мэдэж байх тохиолдолд массив ашиглан тодорхойлох нь тохиромжтой. Гэвч зарим бодлогын хувьд хадгалагдах өгөгдлийн хэмжээг урьдчилан хэлж мэдэхгүй тохиолдлууд байдаг. Энэ тохиолдолд нэг холбоост жагсаалтаар илэрхийлэх нь гарцаагүй юм. Стекийг жагсаалтаар илэрхийлснээр түүний хэмжээ нь бодлогын нөхцлөөс хамаарч програм ажиллах үед динамикаар өөрчлөгдөх боломжтой.

Стекийн шаардлага

Хэдийгээр стек нь маш хязгаарлагдмал үйлдэлтэй боловч компьютерийн програмчлалд чухал үүрэгтэй өгөгдлийн бүтцүүдийн нэг юм. Тухайлбал ямар нэг ажлын явцад өөр зүйл хийхээр түр хойшлуулах, эсвэл програм бүхэлдээ ийм зарчмаар ажиллах зэрэг олон алгоритмд стек үндсэн үүрэг гүйцэтгэнэ. Жишээ нь CALL, RETURN зэрэг функцэд стекийг ашигладаг байна.

Стекийг массив ашиглан нэвтрүүлэх

Стекийг олон янзын аргаар нэвтрүүлж болох боловч ихэвчлэн шугаман массив, эсвэл нэг холбоост жагсаалт ашигладаг. Массив ашиглах стекийг ихэвчлэн гараар тодорхойлж өгдөг. Дараах Stack классын зарлалтаар MaxSize хэмжээтэй stack массив, стекийн оройг тодорхойлох top хувьсагч болон стекд элемент хийх push(), стекээс элемэнт авах pop() функц бусад туслах функцүүдийн хамт тодорхойллоо. Stack массивыг заагчаар тодорхойлсноор динамик ойгоос new операторын тусламжтайгаар MaxSize хэмжээтэй зайг Stack классын обьект зарлах үед нөөцлөн авна. Энэ нь хэдийгээр заагч ашиглаж байгаа боловч хувиарлалт хийснээс хойш түүний хэмжээ MaxSize-аас хэтрэхгүй тул статикаар тодорхойлогдож байна.

Стекийн хэрэглээ:

• Хаалтын баланс шалгах алгоритм Стек ашиглан энэ асуудлыг шийдвэрлэх нь хамгийн тохиромжтой. Тэмдэгтүүдийн цувааны эхнээс тэмдэг бүрийг уншин, нээх хаалт тааралдах бүрд түнийг стекд хийх ба хаах хаалт таарвал стекээс нэг элемент авч харгалзах нээх хаалт эсэхийг шалган, зөв тохиолдол цааш үргэлжлүүлэн шалгана. Өөрөөр хэлбэл нээх хаалтнууд стекд орсон дарааллын эсрэг дарааллаар харгалзан хаах хаалтууд байх ёстой.

• Арифметик илэрхийлэл Арифметикийн илэрхийлэл бодоход үйлдлийн тэмдэгүүдийн гүйцэтгэх дараарллыг баримтлах ёстой. Өөрөөр хэлбэл эхлээд хаалтан дахь үйлдлийг, дараа нь зэрэг дэвшүүлэх үйлдлийг, дараа нь үржих ба хуваах, эцэст нь нэмэх ба хасах гэсэн дарааллаар гүйцэтгэдэг. Жишээ нь: 3*(2+1)*2-8/(9-5)=2*9-8/4=16

Компьютерийн шинжлэх ухааны өгөгдөлийн бүтэцүүдийн нэг нь стек бөгөөд хийсвэрээр тодорхойлогддог мөн аргийг чөлөөтэй хэрэгжүүлдэг бөгөөд ерөнхийдөө шугаман жигсаалтын төрөл гэж тодорхойлж болох ба pop(элемент авах) ба push( элемент хийх) гэсэн үндсэн үйлдэлүүдээс гадна бусад туслах функцуудыг стекийн орой гэх нэг төгсгөлд гүйцэтгэдэг.

функцын түлхүүр үг:

  init: -> Stack
  push: N x Stack -> Stack
  top: Stack -> (N U ERROR)
  pop: Stack -> Stack
  isempty: Stack -> Boolean

утгазүй:

  top(init()) = ERROR
  top(push(i,s)) = i
  pop(init()) = init()
  pop(push(i, s)) = s
  isempty(init()) = true
  isempty(push(i, s)) = false

Програмчлалын бодлого

Илэрхийллийн хаалтны баланс шалгах алгоритм

Алгоритмын зорилго нь: тэмдэгтүүдийн дараалалд (),{},[] гэсэн хаалтууд оролцохбөгөөд нээх (,{,[ бүрт харгалзан хаах хаалт),},] байгаа эсэхийг шалгах юм. Баланслагдсан буюу зөв хаагдсан хаалтуудын цуваа •() •{}{} •({[]()}[]) Баланслаагүй буюу буруу хаагдсан хаалтуудын цуваа •) •[ •{[}] Алгоритмын хэрэгжүүлэлт нь: Тэмдэгтүүдийн цувааны эхлэлээс тэмдэгт бүрийг уншин, нээх хаалт таарах бүрт түүнийг стект хийх ба хаах хаалт тааралдвал стекээс нэг элемэнт авч харгалзах нээх хаалт мөн эсэхийг шалган, зөв тохиолдолд цааш үргэлжлүүлэн шалгана. 2.Арифметик илэрхийлэл бодох Арифметик илэрхийллийг бодохдоо үйлдлийн тэмдэгүүдийн гүйцэтгэгдэх дарааллыг баримтлах ѐстой. Өөрөөр хэлбэл аливаа илэрхийллийг бодохдоо өндөр зэрэглэл бүхий үйлдлээс эхлэн гүйцэтгэж, үр дүнг нь санан дараачийн үйлдэлд ашиглах замаар алхам алхамаар гүйцэтгэдэг Илэрхийлэлд олон янзын үйлдлүүд болон давхар хаалтууд оролцохын хэрээр алхамын тоо ихэсч, засварын утга нэмэгдэнэ. Ийм илэрхийллийг бодох програмын алгоритмыг зохиох хялбар биш байдаг. Харин ийм илэрхийллийг хялбар бодох польш тэмдэглээ гэсэн арга байдаг. Үйлдлүүдийн тэмдгийг операндын эхэнд (prefix) ба хойно (postfix)бичих аргыг Польшийн математикч Лукашевич дэвшүүлсэн. Польш тэмдэглэгээний нэг онцлог бол хаалт ашигладаггүй. Ердийн бичлэгийн үед үйлдлийн гүйцэтгэгдэх дарааллыг хаалтын тусламжтай тодорхойлдог. Польш тэмдэглэгээнд хаалт байхгүй бөгөөд үйлдлийн тэмдгийн байрлалаар гүйцэтгэгдэх дараалал нь тодорхойлогддог. +AB -CD *EF /GH A+B C-D E*F G/H AB+ CD- EF* GH/ A+B*C=A+[*BC]=ABC*+ (A+B)*C=[AB+]*C=AB+C* (A+B)/(C-D)=[AB+]/[CD-]=AB+CD- Польш (prefix) тэмдэглэгээ A+B*C=A+[*BC]=+A*BC (A+B)*C=[+AB]*C=*+ABC (A+B)/(C-D)=[+AB]/[-CD]=/+AB-CD Үүний давуу тал нь аливаа илэрхийллийн завсрын утгуудыг стект хадгалан илэрхийллийг (тэмдэг бүрийг) зөвхөн нэг удаа уншин хялбархан аргаар бодож болдогт оршино.