Ma’lumotlar tuzilmasi va algoritmlar 11- ma’ruza: Stek, navbat va dek. Ma’ruza rejasi Plan lecture

Ma’lumotlar tuzilmasi va algoritmlar

11- ma’ruza: Stek, navbat va dek.

Ma’ruza rejasi Plan lecture

• Yarim-statik tuzilmalar
• Navbat va undagi amallar. Navbatlarni tasvirlash.
• Dek va undagi amallar.
• Stek va undagi amallar. Steklarni tasvirlash.

Yarim-statik tuzilmalar

• Yarimstatik ma’lumotlar tuzilmasiga stek, dek va navbatlar kirib, bundan tashqari ular oshkormas ro’yxatlarga va shu bilan birga ketma-ket tuzilmaga misol bo’ladi. Bunday tuzilma elementlari orasidagi bog’liq, ularning ketma-ketligidir.

Nima sababdan yarimstatik tuzilma deyiladi?

• Bunday tuzilma uzunliklari oldindan beriladi (statiklik sharti), lekin tuzilmani tashkil etuvchi elementlar soni dastur bajarilishi mobaynida vaqtga va ro’yxat uzunligiga bog’liq ravishda o’zgarib turishi mumkin (dinamiklik sharti).

Navbat, Stek va Dek nima?

• Dasturlashda shunday ma’lumotlar tuzilmasi mavjudki, u navbat deb ataladi. Bu turdagi ma’lumotlar tuzilmasida kelib tushgan buyurtmalarga xizmat ko’rsatish tartibi aniqlanadi.

Navbatning turlari

• Ro’yxatni tashkil qiluvchi elementlarga xizmat ko’rsatilish tartibiga qarab, navbatning asosiy ikkita ko’rinishi mavjud:
• 1. FIFO (First input-First output) – Navbat. Navbat har ikkala tomondan ochiq bo’ladi.

Navbatning turlari

• Ro’yxatni tashkil qiluvchi elementlarga xizmat ko’rsatilish tartibiga qarab, navbatning asosiy ikkita ko’rinishi mavjud:
• 2. LIFO (Last input - First output) – Stek. Stek faqat bir tomoni ochiq tuzilma.

Navbat tushinchasi

Navbat bu shunday tuzilmaki, u elementlar qo’shilishi bilan kengayib boradi va elementlarni faqatgina bir tomondan qabul qiladi. Stekdan farqli holda, navbat tuzilmasi har ikkala tomondan ham ochiq hisoblanadi, lekin element kiritish bir tomondan, chiqarish esa ikkinchi tomonidan amalga oshiriladi. Navbat FIFO(first in first out – birinchi kelgan birinchi ketadi) ko’rinishidagi tuzilmadir. Navbatda ham xuddi stekdagi kabi C++ da alohida kutubxona mavjud.