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.
Bir qator oling (deque) hajmi n.
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.
Ning holatini tekshiring old. Old holatini tekshiring
Agarfront < 1, reinitialize front = n-1(oxirgi indeks). Oldinga oxirigacha siljiting
Boshqa, fronttomonidan kamaytirish 1.
Yangi kalit 5qo'shish array[front]. Elementni Old tomonga joylashtiring
2. Orqa tomonga joylashtiring
Ushbu operatsiya orqa tomonga element qo'shadi.
Massiv to'lganligini tekshiring. Deque to'lganligini tekshiring
Agar deque to'la bo'lsa, reinitialize qiling rear = 0.
Boshqa, reartomonidan oshirish 1. Orqa oshirish
Yangi kalit 5qo'shish array[rear]. Elementni orqa tomonga joylashtiring
3. Old tomondan o'chirish
Operatsiya old tomondan elementni o'chiradi.
Deque bo'sh bo'lsa tekshiring. Deque bo'shligini tekshiring
Agar deque bo'sh bo'lsa (ya'ni front = -1), o'chirish amalga oshirilmaydi (oqim holati).
Agar deque faqat bitta elementga ega bo'lsa (ya'ni front = rear), o'rnating front = -1va rear = -1.
Else if frontoxirida (ya'nifront = n - 1) bo'lsa, old tomonga o'ting front = 0.
Boshqa, front = front + 1. Old oshirish
4. Orqa tomondan o'chirish
Bu operatsiya orqa bir elementi o'chiriladi.
Deque bo'sh bo'lsa tekshiring. Deque bo'shligini tekshiring
Agar deque bo'sh bo'lsa (ya'ni front = -1), o'chirish amalga oshirilmaydi (oqim holati).
Agar deque faqat bitta elementga ega bo'lsa (ya'ni front = rear), o'rnating front = -1va rear = -1, else quyidagi amallarni bajaring.
Agar rearold tomonda bo'lsa (ya'ni rear = 0), old tomonga o'tingrear = n - 1.
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
Dasturiy ta'minot bo'yicha operatsiyalarni bekor qilishda.
Brauzerlarda tarixini saqlash uchun.
Vayronaga va navbatga, ham amalga oshirish uchun
Do'stlaringiz bilan baham: |