Bu yazıda çift uçlu kuyruk veya deque'i tartışacağız. Öncelikle kuyruğun kısa bir açıklamasını görmeliyiz.
Sıra nedir?
Kuyruk, ilk gelenin ilk çıkacağı bir veri yapısıdır ve FIFO (İlk Giren İlk Çıkar) politikasını izler. Kuyruğa ekleme, olarak bilinen bir uçtan yapılır. arka uç ya da kuyruk, silme işlemi ise bilinen başka bir uçtan yapılır. başlangıç aşaması ya da KAFA kuyruktan.
Java'nın başlatılması
Kuyruğun gerçek dünyadaki örneği, sinema salonunun dışındaki bilet kuyruğudur; sıraya ilk giren kişi ilk önce bileti alır ve sıraya en son giren kişi de bileti en son alır.
Deque (veya çift uçlu kuyruk) nedir?
Deque, Çift Uçlu Kuyruk anlamına gelir. Deque, ekleme ve silme işlemlerinin her iki uçtan gerçekleştirildiği doğrusal bir veri yapısıdır. Deque'in kuyruğun genelleştirilmiş bir versiyonu olduğunu söyleyebiliriz.
Bir deque'ye ekleme ve silme işlemleri her iki uçta da gerçekleştirilebilmesine rağmen FIFO kuralına uymaz. Bir deque'nin temsili şu şekilde verilmiştir:
Deque türleri
İki tür deque vardır -
- Giriş kısıtlı kuyruğu
- Çıkış kısıtlı kuyruk
Giriş kısıtlı Kuyruk
Giriş kısıtlamalı kuyrukta ekleme işlemi yalnızca bir uçtan yapılabilirken, silme işlemi her iki uçtan da yapılabilir.
Çıkış kısıtlı Kuyruk
Çıkış kısıtlamalı kuyrukta, silme işlemi yalnızca bir uçtan gerçekleştirilebilirken, ekleme işlemi her iki uçtan da gerçekleştirilebilir.
Deque üzerinde gerçekleştirilen işlemler
Bir deque'e uygulanabilecek aşağıdaki işlemler vardır:
- Ön tarafa yerleştirme
- Arkadan yerleştirme
- Önden silme
- Arkadan silme
Yukarıda sıraladığımız operasyonların yanı sıra deque içerisinde peek işlemlerini de gerçekleştirebiliyoruz. Peek işlemi sayesinde deque'in ön ve arka elemanlarını elde edebiliriz. Dolayısıyla yukarıdaki işlemlere ek olarak aşağıdaki işlemler de deque'de desteklenir -
ikili arama ağacı]
- Ön öğeyi deque'den alın
- Arkadaki parçayı deque'den alın
- Deque'nin dolu olup olmadığını kontrol edin
- Deque'nin boş olup olmadığını kontrol eder
Şimdi deque üzerinde yapılan işlemi bir örnekle anlayalım.
Ön uca yerleştirme
Bu işlemde eleman kuyruğun ön ucundan eklenir. İşlemi gerçekleştirmeden önce öncelikle kuyruğun dolu olup olmadığını kontrol etmemiz gerekiyor. Kuyruk dolu değilse öğe aşağıdaki koşullar kullanılarak ön uçtan eklenebilir:
- Kuyruk boşsa hem arka hem de ön 0 ile başlatılır. Şimdi her ikisi de ilk öğeyi işaret edecektir.
- Aksi takdirde ön tarafın 1'den küçük olması durumunda ön tarafın konumunu kontrol edin (ön<1), then reinitialize it by front = n - 1 , yani dizinin son dizini.1),>
Arka uca yerleştirme
Bu işlemde eleman kuyruğun arka ucundan eklenir. İşlemi gerçekleştirmeden önce öncelikle kuyruğun dolu olup olmadığını tekrar kontrol etmemiz gerekiyor. Kuyruk dolu değilse öğe aşağıdaki koşullar kullanılarak arka uçtan eklenebilir:
java'yı ayrıştırmak
- Kuyruk boşsa hem arka hem de ön 0 ile başlatılır. Şimdi her ikisi de ilk öğeyi işaret edecektir.
- Aksi takdirde, arkayı 1 artırın. Arka son indekste (veya boyut - 1) ise, o zaman onu 1 artırmak yerine 0'a eşitlememiz gerekir.
Ön uçta silme
Bu işlemde eleman kuyruğun ön ucundan silinir. İşlemi gerçekleştirmeden önce öncelikle kuyruğun boş olup olmadığını kontrol etmemiz gerekiyor.
Kuyruk boşsa yani ön = -1 ise bu durum yetersiz akış durumudur ve silme işlemini gerçekleştiremeyiz. Kuyruk dolu değilse öğe aşağıdaki koşullar kullanılarak ön uçtan eklenebilir:
Deque'nin yalnızca bir elemanı varsa, arka = -1 ve ön = -1 olarak ayarlayın.
Aksi takdirde, ön uçtaysa (bu, ön = boyut - 1 anlamına gelir), ön = 0 olarak ayarlayın.
100 üzerinden 25
Aksi halde ön tarafı 1 artırın (yani ön = ön + 1).
Arka uçtan silme
Bu işlemde eleman kuyruğun arka ucundan silinir. İşlemi gerçekleştirmeden önce öncelikle kuyruğun boş olup olmadığını kontrol etmemiz gerekiyor.
Kuyruk boşsa yani ön = -1 ise bu durum yetersiz akış durumudur ve silme işlemini gerçekleştiremeyiz.
Deque'nin yalnızca bir elemanı varsa, arka = -1 ve ön = -1 olarak ayarlayın.
Arka = 0 ise (arka öndeyse), arka = n - 1 olarak ayarlayın.
Aksi halde arka kısmı 1 azaltın (veya arka = arka -1).
Boş kontrol edin
Bu işlem deque'nin boş olup olmadığını kontrol etmek için yapılır. Front = -1 ise deque boş demektir.
Tamamını kontrol et
Bu işlem deque'nin dolu olup olmadığını kontrol etmek için yapılır. Ön = arka + 1 veya ön = 0 ve arka = n - 1 ise deque dolu demektir.
Deque'nin yukarıdaki tüm işlemlerinin zaman karmaşıklığı O(1), yani sabittir.
Deque uygulamaları
- Deque, her iki işlemi de desteklediği için hem yığın hem de kuyruk olarak kullanılabilir.
- Deque, bir palindrom denetleyicisi olarak kullanılabilir; bu, dizeyi her iki uçtan okursak dizenin aynı olacağı anlamına gelir.
Deque'nin uygulanması
Şimdi deque'nin C programlama dilindeki uygulamasını görelim.
ayrık matematik olumsuzluğu
#include #define size 5 int deque[size]; int f = -1, r = -1; // insert_front function will insert the value from the front void insert_front(int x) { if((f==0 && r==size-1) || (f==r+1)) { printf('Overflow'); } else if((f==-1) && (r==-1)) { f=r=0; deque[f]=x; } else if(f==0) { f=size-1; deque[f]=x; } else { f=f-1; deque[f]=x; } } // insert_rear function will insert the value from the rear void insert_rear(int x) { if((f==0 && r==size-1) || (f==r+1)) { printf('Overflow'); } else if((f==-1) && (r==-1)) { r=0; deque[r]=x; } else if(r==size-1) { r=0; deque[r]=x; } else { r++; deque[r]=x; } } // display function prints all the value of deque. void display() { int i=f; printf(' Elements in a deque are: '); while(i!=r) { printf('%d ',deque[i]); i=(i+1)%size; } printf('%d',deque[r]); } // getfront function retrieves the first value of the deque. void getfront() { if((f==-1) && (r==-1)) { printf('Deque is empty'); } else { printf(' The value of the element at front is: %d', deque[f]); } } // getrear function retrieves the last value of the deque. void getrear() { if((f==-1) && (r==-1)) { printf('Deque is empty'); } else { printf(' The value of the element at rear is %d', deque[r]); } } // delete_front() function deletes the element from the front void delete_front() { if((f==-1) && (r==-1)) { printf('Deque is empty'); } else if(f==r) { printf(' The deleted element is %d', deque[f]); f=-1; r=-1; } else if(f==(size-1)) { printf(' The deleted element is %d', deque[f]); f=0; } else { printf(' The deleted element is %d', deque[f]); f=f+1; } } // delete_rear() function deletes the element from the rear void delete_rear() { if((f==-1) && (r==-1)) { printf('Deque is empty'); } else if(f==r) { printf(' The deleted element is %d', deque[r]); f=-1; r=-1; } else if(r==0) { printf(' The deleted element is %d', deque[r]); r=size-1; } else { printf(' The deleted element is %d', deque[r]); r=r-1; } } int main() { insert_front(20); insert_front(10); insert_rear(30); insert_rear(50); insert_rear(80); display(); // Calling the display function to retrieve the values of deque getfront(); // Retrieve the value at front-end getrear(); // Retrieve the value at rear-end delete_front(); delete_rear(); display(); // calling display function to retrieve values after deletion return 0; }
Çıktı:
Yani bu makaleyle ilgili. Umarım makale sizin için yararlı ve bilgilendirici olacaktır.