logo

Deque (veya çift uçlu kuyruk)

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 (veya çift uçlu kuyruk)

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.

Deque (veya çift uçlu kuyruk)

Çı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 (veya çift uçlu kuyruk)

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.
Deque (veya çift uçlu kuyruk)

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.
Deque (veya çift uçlu kuyruk)

Ö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).

Deque (veya çift uçlu kuyruk)

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).

Deque (veya çift uçlu kuyruk)

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 &amp;&amp; r==size-1) || (f==r+1)) { printf(&apos;Overflow&apos;); } else if((f==-1) &amp;&amp; (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 &amp;&amp; r==size-1) || (f==r+1)) { printf(&apos;Overflow&apos;); } else if((f==-1) &amp;&amp; (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(&apos;
Elements in a deque are: &apos;); while(i!=r) { printf(&apos;%d &apos;,deque[i]); i=(i+1)%size; } printf(&apos;%d&apos;,deque[r]); } // getfront function retrieves the first value of the deque. void getfront() { if((f==-1) &amp;&amp; (r==-1)) { printf(&apos;Deque is empty&apos;); } else { printf(&apos;
The value of the element at front is: %d&apos;, deque[f]); } } // getrear function retrieves the last value of the deque. void getrear() { if((f==-1) &amp;&amp; (r==-1)) { printf(&apos;Deque is empty&apos;); } else { printf(&apos;
The value of the element at rear is %d&apos;, deque[r]); } } // delete_front() function deletes the element from the front void delete_front() { if((f==-1) &amp;&amp; (r==-1)) { printf(&apos;Deque is empty&apos;); } else if(f==r) { printf(&apos;
The deleted element is %d&apos;, deque[f]); f=-1; r=-1; } else if(f==(size-1)) { printf(&apos;
The deleted element is %d&apos;, deque[f]); f=0; } else { printf(&apos;
The deleted element is %d&apos;, deque[f]); f=f+1; } } // delete_rear() function deletes the element from the rear void delete_rear() { if((f==-1) &amp;&amp; (r==-1)) { printf(&apos;Deque is empty&apos;); } else if(f==r) { printf(&apos;
The deleted element is %d&apos;, deque[r]); f=-1; r=-1; } else if(r==0) { printf(&apos;
The deleted element is %d&apos;, deque[r]); r=size-1; } else { printf(&apos;
The deleted element is %d&apos;, 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ı:

Deque (veya çift uçlu kuyruk)

Yani bu makaleyle ilgili. Umarım makale sizin için yararlı ve bilgilendirici olacaktır.