Deque Ma'lumotlar Tarkibi



Download 208,41 Kb.
Sana14.07.2022
Hajmi208,41 Kb.
#801346
Bog'liq
Yuldashev bunyod


Deque Ma'lumotlar Tarkibi
Ushbu qo'llanmada siz ikki marta tugagan navbat (deque) nima ekanligini bilib olasiz. Shuningdek, Agar C bir deque turli operatsiyalar misollar ish topasiz, C++, Java va Python.
Deque yoki ikki marta tugagan navbat ning bir turi navbat unda elementlarni kiritish va olib tashlash old yoki orqa tomondan amalga oshirilishi mumkin. Shunday qilib, u FIFO qoidasiga amal qilmaydi (birinchi navbatda).
Vakillik Deque
Deque turlari

  • Kirish cheklangan Deque
    ushbu deque - da kirish bitta uchida cheklangan, ammo ikkala uchida ham o'chirishga imkon beradi.

  • Chiqish cheklangan Deque
    ushbu deque - da chiqish bitta uchida cheklangan, ammo ikkala uchida ham kiritishga imkon beradi.

A Deque ustida operatsiyalar
Quyida deque circular array amalga oshirish hisoblanadi. Dumaloq massivda, agar massiv to'la bo'lsa, biz boshidan boshlaymiz.
Lekin bir chiziqli array amalga oshirishda, array to'liq bo'lsa, hech elementlar joylashtirilgan bo'lishi mumkin. Quyidagi operatsiyalarning har birida, agar qator to'la bo'lsa, "toshib ketish xabari" tashlanadi.
Quyidagi operatsiyalarni bajarishdan oldin ushbu qadamlar bajariladi.

  1. Bir qator oling (deque) hajmi n.

  2. Birinchi holatda ikki markerni o'rnating va o'rnatish front = -1va rear = 0.

Deque uchun bir qator va markerni Initialize
1. Old tomondan joylashtiring
Bu operatsiya oldida bir elementi qo'shadi.

  1. Ning holatini tekshiring old. Old holatini tekshiring

  2. Agarfront < 1, reinitialize front = n-1(oxirgi indeks). Oldinga oxirigacha siljiting

  3. Boshqa, fronttomonidan kamaytirish 1.

  4. Yangi kalit 5qo'shish array[front]. Elementni Old tomonga joylashtiring

2. Orqa tomonga joylashtiring
Ushbu operatsiya orqa tomonga element qo'shadi.

  1. Massiv to'lganligini tekshiring. Deque to'lganligini tekshiring

  2. Agar deque to'la bo'lsa, reinitialize qiling rear = 0.

  3. Boshqa, reartomonidan oshirish 1. Orqa oshirish

  4. Yangi kalit 5qo'shish array[rear]. Elementni orqa tomonga joylashtiring

3. Old tomondan o'chirish
Operatsiya old tomondan elementni o'chiradi.

  1. Deque bo'sh bo'lsa tekshiring. Deque bo'shligini tekshiring

  2. Agar deque bo'sh bo'lsa (ya'ni front = -1), o'chirish amalga oshirilmaydi (oqim holati).

  3. Agar deque faqat bitta elementga ega bo'lsa (ya'ni front = rear), o'rnating front = -1va rear = -1.

  4. Else if frontoxirida (ya'nifront = n - 1) bo'lsa, old tomonga o'ting front = 0.

  5. Boshqa, front = front + 1. Old oshirish

4. Orqa tomondan o'chirish
Bu operatsiya orqa bir elementi o'chiriladi.

  1. Deque bo'sh bo'lsa tekshiring. Deque bo'shligini tekshiring

  2. Agar deque bo'sh bo'lsa (ya'ni front = -1), o'chirish amalga oshirilmaydi (oqim holati).

  3. Agar deque faqat bitta elementga ega bo'lsa (ya'ni front = rear), o'rnating front = -1va rear = -1, else quyidagi amallarni bajaring.

  4. Agar rearold tomonda bo'lsa (ya'ni rear = 0), old tomonga o'tingrear = n - 1.

  5. Boshqa, rear = rear - 1. Orqa kamaytirish

5. Tekshirish Bo'sh
Deque bo'sh bo'lsa, bu operatsiya tekshiradi. Agar, deque bo'sh.front = -1
6. To'liq Tekshirish
Deque to'liq bo'lsa, bu operatsiya tekshiradi. Agar va front = 0yokirear = n - 1, deque to'la.front = rear + 1
Python, Java, C va C++da Deque dasturi
Python
Java
C
C++
# Deque implementaion in python


class Deque:
def __init__(self):
self.items = []


def isEmpty(self):
return self.items == []


def addRear(self, item):
self.items.append(item)


def addFront(self, item):
self.items.insert(0, item)


def removeFront(self):
return self.items.pop(0)


def removeRear(self):
return self.items.pop()


def size(self):
return len(self.items)
d = Deque()
print(d.isEmpty())
d.addRear(8)
d.addRear(5)
d.addFront(7)
d.addFront(10)
print(d.size())
print(d.isEmpty())
d.addRear(11)
print(d.removeRear())
print(d.removeFront())
d.addFront(55)
d.addRear(45)
print(d.items)
Vaqt Murakkabligi
Yuqoridagi barcha operatsiyalarning vaqt murakkabligi doimiydir, ya'ni O(1).
Deque ma'lumotlar tuzilishi ilovalar

  1. Dasturiy ta'minot bo'yicha operatsiyalarni bekor qilishda.

  2. Brauzerlarda tarixini saqlash uchun.

  3. Vayronaga va navbatga, ham amalga oshirish uchun

Download 208,41 Kb.

Do'stlaringiz bilan baham:




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish