Дараалал: Засвар хоорондын ялгаа

Content deleted Content added
No edit summary
No edit summary
Мөр 1: Мөр 1:
[[Image:Data Queue.svg|thumb|300px|right|ЭОЭГ (Эхэлж-Орвол-Эхэлж-Гарна) зарчимтай дарааллын дүрслэл]]
[[Image:Data Queue.svg|thumb|300px|right|ЭОЭГ (Эхэлж-Орвол-Эхэлж-Гарна) зарчимтай дарааллын дүрслэл]]
[[Компьютерийн шинжлэх ухаан]]д дараалал гэдэг нь [[өгөгдөлийн хийсвэр төрөл]] болон [[өгөгдлийн цуглуулга]] юм. Энэ нь өгөгдлийг цэгцэлж дэс дараалалд нь оруулахад тусладаг ба дараах зарчимтай. Нэмэгдэж орсон өгөгдөл нь дарааллын төгсгөлд орох буюу ''энкюү'' эсвэл хасагдах нэгж нь дарааллын урд байрлах буюу ''дэкюү''. Өөрөөр хэлбэл дараалалд элемэнт нэмэгдвэл эхний элемэнт устана гэсэн үг бөгөөд дараалалд орж ирэхээс өмнө байсан элемэнтүүд нь устгагдсан байх ёстой гэсэн шаардлагыг тавьдаг ([[FIFO]]). Ихэвчлэн урд талын эсвэл [[пийк]] үйлдэл хийгдсэн бол дарааллын урд байрлах элемэнтийн утгыг устгахгүйгээр буцаадаг. Дараалал нь [[шугаман өгөгдлийн бүтэц]] болон [[хийсвэрлэлттэй дараалл]]ын цуглуулгын жишээ юм.<br />
[[Компьютерийн шинжлэх ухаан]]д '''Дараалал''' гэдэг нь [[өгөгдлийн бүтэц]] болон [[өгөгдлийн цуглуулга]] юм. Энэ нь өгөгдлийг цэгцэлж дэс дараалалд нь оруулахад тусладаг ба дараах зарчимтай. Нэмэгдэж орсон өгөгдөл нь дарааллын төгсгөлд орох буюу ''энкюү'' эсвэл хасагдах нэгж нь дарааллын урд байрлах буюу ''дэкюү''. Өөрөөр хэлбэл дараалалд элемэнт нэмэгдвэл эхний элемэнт устана гэсэн үг бөгөөд дараалалд орж ирэхээс өмнө байсан элемэнтүүд нь устгагдсан байх ёстой гэсэн шаардлагыг тавьдаг ([[FIFO]]). Ихэвчлэн урд талын эсвэл [[пийк]] үйлдэл хийгдсэн бол дарааллын урд байрлах элемэнтийн утгыг устгахгүйгээр буцаадаг. Дараалал нь [[шугаман өгөгдлийн бүтэц]] болон [[хийсвэрлэлттэй дараалл]]ын цуглуулгын жишээ юм.<br />


Дараалал нь компьтерийн шинжлэх ухаан, мэдээлэлийн хэрэгсэл, мөн судалгааны ажил зэрэгт ашиглагддаг. Ингэхдээ өгөгдөл, хүн, болон обектүүдыг компьютерт өгөгдлийн нэгж хэлбэрээр хадгалж аван дараа нь шаардлагатай үед дуудаж ажиллуулдаг. Энэ нь ерөнхийдөө буферийн функцтэй төстэй. <br />
Дараалал нь компьтерийн шинжлэх ухаан, мэдээлэлийн хэрэгсэл, мөн судалгааны ажил зэрэгт ашиглагддаг. Ингэхдээ өгөгдөл, хүн, болон обектүүдыг компьютерт өгөгдлийн нэгж хэлбэрээр хадгалж аван дараа нь шаардлагатай үед дуудаж ажиллуулдаг. Энэ нь ерөнхийдөө буферийн функцтэй төстэй. <br />
Мөр 6: Мөр 6:
Дарааллууд нь компьютерын програмуудад энгийн хандалттай [[өгөгдлийн бүтэц]] эсвэл [[хийсвэр өгөгдлийн бүтэц]] хэлбэртэй хэрэгждэг. Ихэнх хэрэгжүүлэлтүүд нь нөөц болон [[холбоост жагсаалт]] хэлбэртэи байдаг.
Дарааллууд нь компьютерын програмуудад энгийн хандалттай [[өгөгдлийн бүтэц]] эсвэл [[хийсвэр өгөгдлийн бүтэц]] хэлбэртэй хэрэгждэг. Ихэнх хэрэгжүүлэлтүүд нь нөөц болон [[холбоост жагсаалт]] хэлбэртэи байдаг.


==Хэрэгжүүлэлт==
=='''Дарааллын хэрэгжүүлэлт'''==
Онолын үүднээс авч үзвэл дарааллын нэг гол шинж чанар бол тусгай нөөц зайгүй байх явдал юм. Шинэ элемэнтүүд нь өөрсдөө нэмэгдэх чадвартай учраас хэдэн элемэнт байх нь хамаагүй бөгөөд энэ нь аль хэдийн агуулагдсан байдаг. Энэ нь ерөнхийдөө хоосон байдаг хэдий ч дахин шинэ элемэнт нэмэгдэх хүртэл элемэнтүүдийг устгах нь боломжгүй гэсэн үг юм. <br />
Онолын үүднээс авч үзвэл дарааллын нэг гол шинж чанар бол тусгай нөөц зайгүй байх явдал юм. Шинэ элемэнтүүд нь өөрсдөө нэмэгдэх чадвартай учраас хэдэн элемэнт байх нь хамаагүй бөгөөд энэ нь аль хэдийн агуулагдсан байдаг. Энэ нь ерөнхийдөө хоосон байдаг хэдий ч дахин шинэ элемэнт нэмэгдэх хүртэл элемэнтүүдийг устгах нь боломжгүй гэсэн үг юм. <br />


Мөр 20: Мөр 20:
* [[Дэкюү ]] - Давхар-төгсгөлтэй дараалал.<br />
* [[Дэкюү ]] - Давхар-төгсгөлтэй дараалал.<br />


=='''Дарааллууд болон програмчлалын хэлнүүд'''==
==Дарааллууд болон програмчлалын хэлнүүд==
Дараалал нь дангаараа өгөгдлийн төрлийн хэрэгжүүлэлт болж болно. Харин [[дэкюү]] (давхар төгсгөлтэй) дарааллын онцгой тохиолдолд дангаараа хэрэгжиж чаддаггүй. Жишээ нь: Перл болон Руби нь төгсгөлийн жагсаалтаас ''нэмэх'' болон ''дараагын элемэнтийг устгах'' нь боломжтой байдаг, тиймээс шууд болон шууд бус дарааллын жагсаалтанд ''нэмэх'' болон ''дараагын элемэнтийг устгах'' функцуудыг хэрэглэж болно. (эсвэл эсрэгээрээ байж болно) Гэсэн хэдий ч зарим тохиолдлуудад эдгээр нь тийм ч үр дүнтэй биш байдаг.</br>
Дараалал нь дангаараа өгөгдлийн төрлийн хэрэгжүүлэлт болж болно. Харин [[дэкюү]] (давхар төгсгөлтэй) дарааллын онцгой тохиолдолд дангаараа хэрэгжиж чаддаггүй. Жишээ нь: Перл болон Руби нь төгсгөлийн жагсаалтаас ''нэмэх'' болон ''дараагын элемэнтийг устгах'' нь боломжтой байдаг, тиймээс шууд болон шууд бус дарааллын жагсаалтанд ''нэмэх'' болон ''дараагын элемэнтийг устгах'' функцуудыг хэрэглэж болно. (эсвэл эсрэгээрээ байж болно) Гэсэн хэдий ч зарим тохиолдлуудад эдгээр нь тийм ч үр дүнтэй биш байдаг.</br>


С++ ийн [[стандартын загварын сан]] нь J2SE5.0 оос хойшхи зөвхөн ''нэмэх'' болон ''дараагын элемэнтийг устгах'' үйл ажиллагааны цөөхөн төрлийн ангилал болох "Дараалал"-ын загварыг хангадаг Жава-н сан нь дарааллын ажиллагааг тодотгож өгдөг, холбоостой жагсаалт ба шууд бус жагсаалтын ангилалуудыг агуулдаг дарааллын холбоосуудыг багтаадаг.</br>
С++ ийн [[стандартын загварын сан]] нь J2SE5.0 оос хойшхи зөвхөн ''нэмэх'' болон ''дараагын элемэнтийг устгах'' үйл ажиллагааны цөөхөн төрлийн ангилал болох "Дараалал"-ын загварыг хангадаг Жава-н сан нь дарааллын ажиллагааг тодотгож өгдөг, холбоостой жагсаалт ба шууд бус жагсаалтын ангилалуудыг агуулдаг дарааллын холбоосуудыг багтаадаг.</br>


=='''Холбоотой мэдээлэл'''==
==Холбоотой мэдээлэл==
*[[Дэкюү]]
*[[Дэкюү]]
*[[Анхдагч дараалал]]
*[[Анхдагч дараалал]]
Мөр 31: Мөр 31:
*[[Стек]] – кюүгийн "эсрэг" тал: [[СОЭГ]] (Сүүлд Орвол Эхэнд Гарна)</br>
*[[Стек]] – кюүгийн "эсрэг" тал: [[СОЭГ]] (Сүүлд Орвол Эхэнд Гарна)</br>


==Ишлэл==
=='''Иш таталтууд'''==
;General
;General
*[[Donald Knuth]]. ''The Art of Computer Programming'', Volume 1: ''Fundamental Algorithms'', Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 2.2.1: Stacks, Queues, and Deques, pp.&nbsp;238&ndash;243.
*[[Donald Knuth]]. ''The Art of Computer Programming'', Volume 1: ''Fundamental Algorithms'', Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 2.2.1: Stacks, Queues, and Deques, pp.&nbsp;238&ndash;243.
Мөр 40: Мөр 40:
{{Reflist}}</br>
{{Reflist}}</br>


=='''Гадаад холбоосууд'''==
==Гадаад холбоосууд==
{{Commons category|Queue data structure}}
{{Commons category|Queue data structure}}
*[http://scanftree.com/Data_Structure/Queues Queues with algo and 'c' programe]
*[http://scanftree.com/Data_Structure/Queues Queues with algo and 'c' programe]
Мөр 50: Мөр 50:


{{DEFAULTSORT:Queue (Data Structure)}}
{{DEFAULTSORT:Queue (Data Structure)}}
[[Ангилал:Өгөгдлийн бүтэц]]
[[Category:Abstract data types]]
[[Category:Articles with example C++ code]]

16:58, 7 Гуравдугаар сар 2014-ий байдлаарх засвар

ЭОЭГ (Эхэлж-Орвол-Эхэлж-Гарна) зарчимтай дарааллын дүрслэл

Компьютерийн шинжлэх ухаанд Дараалал гэдэг нь өгөгдлийн бүтэц болон өгөгдлийн цуглуулга юм. Энэ нь өгөгдлийг цэгцэлж дэс дараалалд нь оруулахад тусладаг ба дараах зарчимтай. Нэмэгдэж орсон өгөгдөл нь дарааллын төгсгөлд орох буюу энкюү эсвэл хасагдах нэгж нь дарааллын урд байрлах буюу дэкюү. Өөрөөр хэлбэл дараалалд элемэнт нэмэгдвэл эхний элемэнт устана гэсэн үг бөгөөд дараалалд орж ирэхээс өмнө байсан элемэнтүүд нь устгагдсан байх ёстой гэсэн шаардлагыг тавьдаг (FIFO). Ихэвчлэн урд талын эсвэл пийк үйлдэл хийгдсэн бол дарааллын урд байрлах элемэнтийн утгыг устгахгүйгээр буцаадаг. Дараалал нь шугаман өгөгдлийн бүтэц болон хийсвэрлэлттэй дарааллын цуглуулгын жишээ юм.

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

Дарааллууд нь компьютерын програмуудад энгийн хандалттай өгөгдлийн бүтэц эсвэл хийсвэр өгөгдлийн бүтэц хэлбэртэй хэрэгждэг. Ихэнх хэрэгжүүлэлтүүд нь нөөц болон холбоост жагсаалт хэлбэртэи байдаг.

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

Онолын үүднээс авч үзвэл дарааллын нэг гол шинж чанар бол тусгай нөөц зайгүй байх явдал юм. Шинэ элемэнтүүд нь өөрсдөө нэмэгдэх чадвартай учраас хэдэн элемэнт байх нь хамаагүй бөгөөд энэ нь аль хэдийн агуулагдсан байдаг. Энэ нь ерөнхийдөө хоосон байдаг хэдий ч дахин шинэ элемэнт нэмэгдэх хүртэл элемэнтүүдийг устгах нь боломжгүй гэсэн үг юм.

Тогтмол урттай массивууд нь хэмжээгээрээ хязгаарлагддаг бөгөөд хэрвээ хэмжээгээрээ хязгаарлагдаагүй байвал утгуудыг тухайн дарааллын эхэнд хуулж аваачих хэрэгтэй болдог. Хязгаарлагдмал хүрээнд байгаа массивыг өөрчлөх болон эхлэл болон төгсгөлийн хэсэгт чөлөөтэй шилжих энгийн арга бол массивд хадгалагдсан утгуудыг хөдөлгөхгүй байлгах явдал юм. Массивын уртыг n гэвэл тухайн утгуудын хамрах хүрээ нь n-ын орчимд л тооцоологдоно. Энэ нь дарааллыг өндөр түвшний хэлэнд байгуулах нийтэд дэлгэрсэн энгийн ойлголтуудын нэг боловч бага зэрэг удаан байдаг. Яагаад гэвэл массивын индекс нь 0-той болон массивын урттай буюу индексүүдийн утга хил хязгаараас хэтэрсэн эсвэл хугацааны хязгаарлалттай зэргийг харгалзан үзсэний үндсэн дээр харьцуулагддаг. Үүнийг зарим хэлнүүд дэмждэг хэдий ч шуурхай болон зохимжгүй хэрэгжүүлэлттэй үед эсвэл синтаксын заагчгүй өндөр түвшний зарим хэлэнд сонголтын арга болдог. Зарим хэрэгжүүлэлтийн үед халилт тохиолдвол массивын урт нь дахин зарлагдах шаардлагатай ба тухайн хугацаанаас өмнө зарлагдсан байх ёстой. Ихэнхи орчин үеийн обьект хандалтад хэлнүүд нь динамик ажиллагаанд зориулсан архивтай ирдэг. Зарим өгөгдлийн бүтэцүүдэд тодорхой зайны хязгаар байдаггүй (санах ойноос бусад). Дүүрэн байгаа дараалалд өгөгдөл нэмэхийг халилт, харин ямар ч өгөгдөлгүй дарааллаас өгөгдөл устгахыг оролдох юм бол өгөгдлийн төөрөгдөл үүсдэг.

Хязгаарлагсан дарааллын утгуудыг өөрчлөх боломжгүй байдаг.

ЭОЭГ кюүг хэд хэдэн үр дүнтэй хэрэгжүүлэлтүүд байдаг. Үр дүнтэй гэдэг нь үүн дээр үйлдэл—энкюү болон дикюүг— О(1) хугацаанд хийх боломжтой гэсэн үг.

  • Холбоост жагсаалт
    • Давхар холбоост жагсаалт нь төгсгөлөөсөө О(1) нэмэлт болон хасалт хийж болдог тул кюүг ашиглахад тохиромжтой.
    • Энгийн холбоост жагсаалт нь зөвхөн нэг төгсгөлдөө л нэмэлт болон хасалт хийж болдог. Гэсэн хэдий ч заагчыг төгсгөлийн холбоос эсвэл эхний холбоос руу зааж байхаар өөрчлөлт хийвэл — үр дүнтэйгээр кюүг ашиглах боломжтой болно.
  • Дэкюү - Давхар-төгсгөлтэй дараалал.

Дарааллууд болон програмчлалын хэлнүүд

Дараалал нь дангаараа өгөгдлийн төрлийн хэрэгжүүлэлт болж болно. Харин дэкюү (давхар төгсгөлтэй) дарааллын онцгой тохиолдолд дангаараа хэрэгжиж чаддаггүй. Жишээ нь: Перл болон Руби нь төгсгөлийн жагсаалтаас нэмэх болон дараагын элемэнтийг устгах нь боломжтой байдаг, тиймээс шууд болон шууд бус дарааллын жагсаалтанд нэмэх болон дараагын элемэнтийг устгах функцуудыг хэрэглэж болно. (эсвэл эсрэгээрээ байж болно) Гэсэн хэдий ч зарим тохиолдлуудад эдгээр нь тийм ч үр дүнтэй биш байдаг.

С++ ийн стандартын загварын сан нь J2SE5.0 оос хойшхи зөвхөн нэмэх болон дараагын элемэнтийг устгах үйл ажиллагааны цөөхөн төрлийн ангилал болох "Дараалал"-ын загварыг хангадаг Жава-н сан нь дарааллын ажиллагааг тодотгож өгдөг, холбоостой жагсаалт ба шууд бус жагсаалтын ангилалуудыг агуулдаг дарааллын холбоосуудыг багтаадаг.

Холбоотой мэдээлэл

Ишлэл

General
Citations


Гадаад холбоосууд

 Commons: Queue data structure – Викимедиа зураг, бичлэг, дууны сан

Загвар:Data structures Загвар:DADS