Дараалал
Компьютерийн шинжлэх ухаанд Дараалал' буюу Кюү, Queue гэдэг нь өгөгдлийн бүтэц болон өгөгдлийн цуглуулга юм. Энэ нь өгөгдлийг цэгцэлж дэс дараалалд нь оруулахад тусладаг ба дараах зарчимтай. Нэмэгдэж орсон өгөгдөл нь дарааллын төгсгөлд орох буюу энкюү эсвэл хасагдах нэгж нь дарааллын урд байрлах буюу дэкюү. Өөрөөр хэлбэл дараалалд элемэнт нэмэгдвэл эхний элемэнт устана гэсэн үг бөгөөд дараалалд орж ирэхээс өмнө байсан элемэнтүүд нь устгагдсан байх ёстой гэсэн шаардлагыг тавьдаг (FIFO). Ихэвчлэн урд талын эсвэл пийк үйлдэл хийгдсэн бол дарааллын урд байрлах элемэнтийн утгыг устгахгүйгээр буцаадаг. Дараалал нь шугаман өгөгдлийн бүтэц болон хийсвэрлэлттэй дарааллын цуглуулгын жишээ юм.
Дараалал нь компьтерийн шинжлэх ухаан, мэдээлэлийн хэрэгсэл, мөн судалгааны ажил зэрэгт ашиглагддаг. Ингэхдээ өгөгдөл, хүн, болон обектүүдыг компьютерт өгөгдлийн нэгж хэлбэрээр хадгалж аван дараа нь шаардлагатай үед дуудаж ажиллуулдаг. Энэ нь ерөнхийдөө буферийн функцтэй төстэй.
Дарааллууд нь компьютерын програмуудад энгийн хандалттай өгөгдлийн бүтэц эсвэл хийсвэр өгөгдлийн бүтэц хэлбэртэй хэрэгждэг. Ихэнх хэрэгжүүлэлтүүд нь нөөц болон холбоост жагсаалт хэлбэртэи байдаг.
Хэрэгжүүлэлт
[засварлах | кодоор засварлах]Онолын үүднээс авч үзвэл дарааллын нэг гол шинж чанар бол тусгай нөөц зайгүй байх явдал юм. Шинэ элемэнтүүд нь өөрсдөө нэмэгдэх чадвартай учраас хэдэн элемэнт байх нь хамаагүй бөгөөд энэ нь аль хэдийн агуулагдсан байдаг. Энэ нь ерөнхийдөө хоосон байдаг хэдий ч дахин шинэ элемэнт нэмэгдэх хүртэл элемэнтүүдийг устгах нь боломжгүй гэсэн үг юм.
Тогтмол урттай массивууд нь хэмжээгээрээ хязгаарлагддаг бөгөөд хэрвээ хэмжээгээрээ хязгаарлагдаагүй байвал утгуудыг тухайн дарааллын эхэнд хуулж аваачих хэрэгтэй болдог. Хязгаарлагдмал хүрээнд байгаа массивыг өөрчлөх болон эхлэл болон төгсгөлийн хэсэгт чөлөөтэй шилжих энгийн арга бол массивд хадгалагдсан утгуудыг хөдөлгөхгүй байлгах явдал юм. Массивын уртыг n гэвэл тухайн утгуудын хамрах хүрээ нь n-ын орчимд л тооцоологдоно. Энэ нь дарааллыг өндөр түвшний хэлэнд байгуулах нийтэд дэлгэрсэн энгийн ойлголтуудын нэг боловч бага зэрэг удаан байдаг. Яагаад гэвэл массивын индекс нь 0-той болон массивын урттай буюу индексүүдийн утга хил хязгаараас хэтэрсэн эсвэл хугацааны хязгаарлалттай зэргийг харгалзан үзсэний үндсэн дээр харьцуулагддаг. Үүнийг зарим хэлнүүд дэмждэг хэдий ч шуурхай болон зохимжгүй хэрэгжүүлэлттэй үед эсвэл синтаксын заагчгүй өндөр түвшний зарим хэлэнд сонголтын арга болдог. Зарим хэрэгжүүлэлтийн үед халилт тохиолдвол массивын урт нь дахин зарлагдах шаардлагатай ба тухайн хугацаанаас өмнө зарлагдсан байх ёстой. Ихэнхи орчин үеийн обьект хандалтад хэлнүүд нь динамик ажиллагаанд зориулсан архивтай ирдэг. Зарим өгөгдлийн бүтэцүүдэд тодорхой зайны хязгаар байдаггүй (санах ойноос бусад). Дүүрэн байгаа дараалалд өгөгдөл нэмэхийг халилт, харин ямар ч өгөгдөлгүй дарааллаас өгөгдөл устгахыг оролдох юм бол өгөгдлийн төөрөгдөл үүсдэг.
Хязгаарлагсан дарааллын утгуудыг өөрчлөх боломжгүй байдаг.
ЭОЭГ кюүг хэд хэдэн үр дүнтэй хэрэгжүүлэлтүүд байдаг. Үр дүнтэй гэдэг нь үүн дээр үйлдэл—энкюү болон дикюүг— О(1) хугацаанд хийх боломжтой гэсэн үг.
- Холбоост жагсаалт
- Давхар холбоост жагсаалт нь төгсгөлөөсөө О(1) нэмэлт болон хасалт хийж болдог тул кюүг ашиглахад тохиромжтой.
- Энгийн холбоост жагсаалт нь зөвхөн нэг төгсгөлдөө л нэмэлт болон хасалт хийж болдог. Гэсэн хэдий ч заагчыг төгсгөлийн холбоос эсвэл эхний холбоос руу зааж байхаар өөрчлөлт хийвэл — үр дүнтэйгээр кюүг ашиглах боломжтой болно.
- Дэкюү - Давхар-төгсгөлтэй дараалал.
Дарааллууд болон програмчлалын хэлнүүд
[засварлах | кодоор засварлах]Дараалал нь дангаараа өгөгдлийн төрлийн хэрэгжүүлэлт болж болно. Харин дэкюү (давхар төгсгөлтэй) дарааллын онцгой тохиолдолд дангаараа хэрэгжиж чаддаггүй. Жишээ нь: Перл болон Руби нь төгсгөлийн жагсаалтаас нэмэх болон дараагын элемэнтийг устгах нь боломжтой байдаг, тиймээс шууд болон шууд бус дарааллын жагсаалтанд нэмэх болон дараагын элемэнтийг устгах функцуудыг хэрэглэж болно. (эсвэл эсрэгээрээ байж болно) Гэсэн хэдий ч зарим тохиолдлуудад эдгээр нь тийм ч үр дүнтэй биш байдаг.
С++ ийн стандартын загварын сан нь J2SE5.0 оос хойшхи зөвхөн нэмэх болон дараагын элемэнтийг устгах үйл ажиллагааны цөөхөн төрлийн ангилал болох "Дараалал"-ын загварыг хангадаг Жава-н сан нь дарааллын ажиллагааг тодотгож өгдөг, холбоостой жагсаалт ба шууд бус жагсаалтын ангилалуудыг агуулдаг дарааллын холбоосуудыг багтаадаг.
Холбоотой мэдээлэл
[засварлах | кодоор засварлах]- Дэкюү
- Анхдагч дараалал
- Дарааллын онол
- Стек – кюүгийн "эсрэг" тал: СОЭГ (Сүүлд Орвол Эхэнд Гарна)
Ишлэл
[засварлах | кодоор засварлах]- 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. 238–243.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 10.1: Stacks and queues, pp. 200–204.
- William Ford, William Topp. Data Structures with C++ and STL, Second Edition. Prentice Hall, 2002. ISBN 0-13-085850-1. Chapter 8: Queues and Priority Queues, pp. 386–390.
- Adam Drozdek. Data Structures and Algorithms in C++, Third Edition. Thomson Course Technology, 2005. ISBN 0-534-49182-0. Chapter 4: Stacks and Queues, pp. 137–169.