“Ахборот технологиялари” факультети “Ахборот технологияларини дастурий таъминоти” кафедраси “маълумотлар тузилмаси ва алгоритмлар”

2-Тажриба иши. "ЯРИМСТАТИК МАЪЛУМОТЛАР ТУЗИЛМАСИ" 
Ишдан мақсад: Навбат ва Стекни ўрганиш ҳамда уларни тадқиқ қилиш. 
Қўйилган масала: C++ тилида навбат ва стекни тадқиқ қилиш дастурини ишлаб чиқиш . 
Иш тартиби: 
 Тажриба иши тавсифини ўрганиш; 
 Берилган топшириқни дастури алгоритмини ишлаб чиқиш; 
 С+ тилида дастурни яратиш; 
 Дастурни ишлатиш; 
 масалани ечиш; 
 хисоботни тайёрлаш. 
Қисқача назария 
Яримстатик маълумотлар тузилмасини қуйидагича тавсифлаш мумкин:
- 
ўзгарувчан узунликка эга ва уни ўзгартирувчи оддий процедураларга эга; 
- 
тузилмани узунлигини ўзгартириш маълум бир чегарада, яъни қандайдир бир максимал қийматдан 
ошмаган холда амалга оширилиши мумкин; 
Агар яримстатик тузилмани мантиқий жихатдан қарайдиган бўлсак, у холда чизиқли рўйхат 
муносабати билан боғланган маълумотлар кетма-кетлиги тушунилади. Элементга мурожаат унинг тартиб 
рақами билан амалга оширилади. Хотирада яримстатик маълумотлар тузилмасини физик жихатдан 
тасвирлайдиган бўлсак, бу хотирада слотларнинг оддий кетма-кетлигидир, яъни хар бир элемент хотирада 
навбатдаги слотларда жойлашади. Яримстатик МТ ни физик тасвирлашнинг яна бир кўриниши бир томонлама 
боғланган рўйхат (занжир) кўринишида ифодалаш мумкин, яъни бунда хар бир навбатдаги элементни адреси 
жорий элементда кўрсатилади. Бундай тасвирлашда тузилманинг узунлигига чекланиш унчалик қаттиқ 
қўйилмайди. Бундай тузилмаларга – навбат, стек, дек ва сатрлар киради.
Навбат 
Навбат бу FIFO (First In - First Out - "биринчи келган – биринчи кетади"), шундай ўзгарувчан 
узунликдаги кетма-кетлик, рўйхатки, унда тузилмага элементлар фақат бир томондан, яъни навбатнинг 
охиридан қўшилади ва элементларни тузилмадан чиқариш бошқа томондан, яъни навбат бошидан амалга 
оширилади. Навбат устида бажариладиган асосий амаллар
- 
янги элементни қўшиш,
- 
элементни ўчириш,
- 
узунлигини аниқлаш,
- 
навбатни тозалаш.
Навбатни статик хотирада вектор кўринишида ифодалашда 2 та параметр, яъни навбат 
бошини(навбатнинг 1-элементини) ва охирини(навбатнинг охирги элементини) кўрсатувчи кўрсаткичлар 
олинади.
Навбатга янги элемент киритилаётганда навбат охири кўрсаткичи кўрсатаётган адресга ёзилади ва 
шундан кейин навбат охири кўрсаткичи биттага оширилади. Навбатдан элементни ўчиришда навбат боши 
кўрсаткичи кўрсатаётган адресдаги элемент ўчирилади ва шундан кейин бу кўрсаткичнинг қиймати биттага 
оширилади. Навбатга элементлар киритилганда навбат охири кўрсаткичи шу навбат учун ажратилган хотира 
сохасининг охирига етиб қолади. Бунда навбат тўлган хисобланади.
Агар навбатдан элементлар ўчириладиган бўлса, навбат бошида бўш жой ажратилади. Вахоланки, 
навбат охири кўрсаткичи чегарага етиб қолганлиги сабабли, навбатга янги элемент киритиб бўлмайди. Шу 
сабабли навбатда хар сафар элемент ўчирилганда қолган барча элементлар битта олдинга сурилиши керак 
бўлади. Натижада навбат охирида бўш жой очилади. Бу холатда навбат боши кўрсаткичига хожат қолмайди. 
Лекин шуни айтиш керакки, бу ёндашув бир мунча ноқулай хисобланади. Шунинг учун хар сафар 
элементларни суриб ўтирмаслик учун навбатни халқасимон шаклда ташкил этамиз. Яъни бунда хотирада 
навбат сохасининг охирига етиб борилганда навбат бошига ўтиб кетилади. Ушбу холатда навбат боши ва охири 
кўрсаткичлари хотирадаги навбат сохасининг бошини кўрсатади. Бу иккала кўрсаткичларнинг тенглиги 
навбатнинг бўшлигини англатади. Халқасимон навбатда элемент қўшиш амали ўчириш амалидан кўпроқ 
бажарилса, навбат охири кўрсаткичи навбат боши кўрсаткичига “етиб олади”. Бу холат навбат тўлалигини 
англатади. Халқасимон навбатда элементни ўчириш иккала кўрсаткич кўрсатаётган битта адресда амалга 
оширилади. Бундай навбатнинг узунлиги боши ва охири кўрсаткичлари фарқи билан аниқланади.
Навбат боши 
Навбат охири 
R=8 
чиқиш 
кириш 

---

13