DIY Queue: Öz növbə sinifini necə yazmaq olar

Kompüter elmində bir növbə bir xəttdə dayanan insanlara bənzəyir (və ya - daha çox İngilis dilli istifadə etməyi istəsən bir növbə). Metafora, VIP qısa gözləmə xətləri, DisneyLand Fast Passes və gündəlik həyatda rast gələ bilən xətt mühəndisliyi və dizaynı ilə mükəmməl deyil. Ancaq gəlin daha sadə bir dövrə qayıdaq, bir xətt bir xətt olanda və əgər mən xətdə ilk adam idimsə, onda gosh darnit, mən xidmət edən ilk insan idim. Məni arxamdakı adam, sonra da arxasında duran adam izləyərdim. Heç kəsilmir, dostun qoşulacağı yer qazandırmır. Sadəcə, gözəl, uyğun bir xətt. Bu, dostum, növbədir.

Metaforalardan uzaqlaşaraq, bir növbə daha məhdud imkanlara malik bir sıra kimi fəaliyyət göstərir. Bir First-In-First-Out məlumat quruluşudur və adətən dörd metod olacaq:

enqueue: növbənin sonuna bir dəyər əlavə edir

dequeue: növbədəki ilk dəyəri aradan qaldırır

peek: növbədəki ilk dəyərin ləğv edilmədən nə olduğunu görmək imkanı verir

is_empty?: növbədə dəyərlərin olub olmadığını yoxlayaq

Kodlaşdırmaya gələk. Əvvəlcə sinif qurmalıyıq. Növbəni adlayacağımız yeni bir massiv hazırlayaraq başlayacağıq və uzunluğunu izləyirik. Hal hazırda sinifimiz belə görünür:

Bir az cansıxıcı, amma başlamaq üçün yaxşı bir yer. Gəlin enqueue quraq:

Enqueue üçün cari növbənin sonunda bir element əlavə edə bilmək istəyirik. Uzunluğu istifadə edərək bunun harada olduğunu tapa bilərik. Məsələn, növbəmiz boşdursa, uzunluq 0-a bərabərdir, buna görə ilk indeksdə bir dəyər daxil edəcəyik. Növbəmizdə beş maddə varsa, uzunluq beşdir, ancaq maddələr 0–4 indekslərdədir, buna görə 5 indeksində növbəti dəyərimizə əlavə etmək istədiyimizdir. Gözəl!

Gəlin dequeue-a keçək. Əslində heç bir şeyi silməkdən çəkinməyək, əvəzində sadəcə bir ofset izləyirik və bir maddəni təyin etdikdə yeniləyirik? Bu o deməkdir ki, izləmək üçün yeni bir dəyişənə ehtiyac duyacağıq. Bunu konstruktorumuza əlavə etməklə başlayaq:

İndi bunu dequeue metoduna qoşaq:

Bunu parçalayaq. Üç maddədən ibarət bir sıra olduğumuzu söylə:

Üstdən, hər bir dəyəri olduğu indeks etiket etiketini etiket etdim, alt hissədə isə ofset etiket etdim. Başlanğıcda onlar birdir. Ancaq bir elementi serialdan çıxarmaq istəsək, əslində onu silmək məcburiyyətində deyilik. Sadəcə baxdığımızı tənzimləməliyik. Bir maddənin indeks əvəzinə bir ofset istifadə etsək, axtardığımızı ofsetə əlavə etməklə sadəcə düzəldə bilərik. Aşağıdakı şəkildəki serialın ilk dəyərini ofset dəyişdirərək silinmişəm, beləliklə baxdığımız serialın hansı hissəsini dəyişdirirəm:

Eyni zamanda, uzunluğu azaltmalıyıq və eyni zamanda qaldırdığımız dəyəri qaytarmaq istəyirik. Ruby'nin gizli geri dönmələri sayəsində, metodun son ifadəsindəki görmə qabiliyyətimizdən köçürdüyümüz dəyərləri geri qayıtmadan söyləyə bilməyəcəyik, lakin əksər digər dillərdə bu barədə açıq olmaq istərdik.

Hamısı yaxşıdır, amma indi həll etmək üçün yeni bir problemimiz var. Bizim enqueue artıq işləmir, buna görə onu yeniləməliyik. Olduğu kimi qalsa, növbənin sonuna maddələr əlavə etmək əvəzinə, onsuz da təsadüfən üzərindəki elementlərin üstünə yazacağıq. Enqueue və yeniləmə qayıdaq:

İndi növbənin uzunluğunu və ofsetini nəzərə alaraq növbəyə bir şey əlavə etdiyimiz yerləri yeniləyirik. Beləliklə, yuxarıda göstərilən növbəyə bir şey əlavə etmək istəsəydik, bizim ofset 1 olar və uzunluğumuz 2 olar. Ardınca yeni bir element əlavə etmək istədiyimiz indeks olan 1 + 2 = 3.

İs_empty üzərində hərəkət?:

Artıq daxili olaraq uzunluğu izləyirik, is_empty? növbədə ən azı bir maddənin olub olmadığını yoxlamaq üçün sadə bir məsələdir. Yoxdursa, həqiqi qayıda bilərik (növbə boşdur) və əks halda yalnış qayıdırıq (növbə boş deyil).

Nəhayət, yazmaq üçün peek metodumuz var. Peek ilə, növbə altındakı növbəti dəyərin nə olduğunu yoxlamaq istəyirik. Bizim üçün şanslı, ofset artıq növbədəki ilk elementin yerini izləyir:

Daha əvvəl çəkdiyimiz növbələrə istinad edərək bunu yoxlayaq:

Bu vəziyyətdə, ofsetimiz 0-a bərabərdir, növbəyə baxanda növbənin ilk bəndini "a" görürük.

Bununla birlikdə, artıq bir şeyi növbədən çıxartdıq. Bizim ofset hazırda 1-dir, növbədəki ilk maddənin indeksidir və tam axtardığımız budur.

Gözəl! İndi ürəklərimizin istəyinə istifadə edə biləcəyimiz sadə, lakin işlək bir növbə sinifimiz var.