Deque Data Yapısı

Bu eğitimde, çift uçlu bir sıranın (deque) ne olduğunu öğreneceksiniz. Ayrıca, C, C ++, Java ve Python'da bir dizide farklı işlemlerin çalışma örneklerini bulacaksınız.

Deque veya Double Ended Queue, öğelerin eklenmesinin ve kaldırılmasının önden veya arkadan gerçekleştirilebildiği bir kuyruk türüdür. Böylece FIFO kuralına (İlk Giren İlk Çıkar) uymaz.

Deque'in Temsili

Deque Türleri

  • Giriş Kısıtlı Geriye Döndürme
    Bu gecikmede , giriş tek bir uçta kısıtlanır, ancak her iki uçta da silmeye izin verir.
  • Çıktı Kısıtlı Deque
    Bu gecikmede , çıktı tek bir uçta sınırlandırılır ancak her iki uçta da yerleştirmeye izin verir.

Bir Arka Plan Üzerinde İşlemler

Deque'in dairesel dizi uygulaması aşağıdadır. Dairesel bir dizide, dizi dolu ise baştan başlarız.

Ancak doğrusal bir dizi uygulamasında, dizi doluysa, daha fazla öğe eklenemez. Aşağıdaki işlemlerin her birinde dizi doluysa "taşma mesajı" atılır.

Aşağıdaki işlemleri gerçekleştirmeden önce bu adımlar takip edilir.

  1. N boyutunda bir dizi (deque) alın.
  2. Birinci konumda ve sette iki işaretçileri ayarlayın front = -1ve rear = 0.
Deque için bir dizi ve işaretçileri başlatın

1. Öne Takın

Bu işlem, öne bir eleman ekler.

  1. Ön tarafın konumunu kontrol edin. Ön tarafın konumunu kontrol edin
  2. Eğer front < 1, yeniden başlatın front = n-1(son dizin). Önü sona kaydır
  3. Aksi takdirde, öne 1 azaltın.
  4. Yeni anahtarı 5 içine ekleyin array(front). Öğeyi Öne yerleştirin

2. Arka Tarafa Takın

Bu işlem arkaya bir eleman ekler.

  1. Dizinin dolu olup olmadığını kontrol edin. Deque'in dolu olup olmadığını kontrol edin
  2. Kuyruk doluysa, yeniden başlatın rear = 0.
  3. Aksi takdirde, arka kısmı 1 arttırın.
  4. Yeni anahtarı 5 içine ekleyin array(rear). Elemanı arkaya yerleştirin

3. Önden Sil

İşlem, ön taraftan bir öğeyi siler.

  1. Süsün boş olup olmadığını kontrol edin. Deque boş mu kontrol edin
  2. Kuyruk boşsa (yani front = -1), silme gerçekleştirilemez ( yetersiz akış koşulu ).
  3. Süslemenin yalnızca bir öğesi varsa (yani front = rear), front = -1ve ayarlayın rear = -1.
  4. Aksi takdirde, ön uçta ise (yani front = n - 1), öne git'i ayarlayın front = 0.
  5. Aksi takdirde front = front + 1,. Ön tarafı artırın

4. Arkadan Sil

Bu işlem arkadan bir öğeyi siler.

  1. Süsün boş olup olmadığını kontrol edin. Deque boş mu kontrol edin
  2. Kuyruk boşsa (yani front = -1), silme gerçekleştirilemez ( yetersiz akış koşulu ).
  3. Süslemenin yalnızca bir öğesi varsa (yani front = rear), ayarlayın front = -1ve rear = -1aşağıdaki adımları izleyin.
  4. Arka öndeyse (yani rear = 0), öne git ayarını yapın rear = n - 1.
  5. Aksi takdirde rear = rear - 1,. Arka kısmı küçültün

5. Boş'u Kontrol Edin

Bu işlem, arkın boş olup olmadığını kontrol eder. Eğer front = -1, perde boştur.

6. Dolu Kontrol Et

Bu işlem, dizinin dolu olup olmadığını kontrol eder. Eğer front = 0ve rear = n - 1VEYA front = rear + 1, deque dolu.

Python, Java, C ve C ++ 'da Deque Uygulaması

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() def removeRear(self): return self.items.pop(0) 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)
 // Deque implementation in Java class Deque ( static final int MAX = 100; int arr(); int front; int rear; int size; public Deque(int size) ( arr = new int(MAX); front = -1; rear = 0; this.size = size; ) boolean isFull() ( return ((front == 0 && rear == size - 1) || front == rear + 1); ) boolean isEmpty() ( return (front == -1); ) void insertfront(int key) ( if (isFull()) ( System.out.println("Overflow"); return; ) if (front == -1) ( front = 0; rear = 0; ) else if (front == 0) front = size - 1; else front = front - 1; arr(front) = key; ) void insertrear(int key) ( if (isFull()) ( System.out.println(" Overflow "); return; ) if (front == -1) ( front = 0; rear = 0; ) else if (rear == size - 1) rear = 0; else rear = rear + 1; arr(rear) = key; ) void deletefront() ( if (isEmpty()) ( System.out.println("Queue Underflow"); return; ) // Deque has only one element if (front == rear) ( front = -1; rear = -1; ) else if (front == size - 1) front = 0; else front = front + 1; ) void deleterear() ( if (isEmpty()) ( System.out.println(" Underflow"); return; ) if (front == rear) ( front = -1; rear = -1; ) else if (rear == 0) rear = size - 1; else rear = rear - 1; ) int getFront() ( if (isEmpty()) ( System.out.println(" Underflow"); return -1; ) return arr(front); ) int getRear() ( if (isEmpty() || rear < 0) ( System.out.println(" Underflow"); return -1; ) return arr(rear); ) public static void main(String() args) ( Deque dq = new Deque(4); System.out.println("Insert element at rear end : 12 "); dq.insertrear(12); System.out.println("insert element at rear end : 14 "); dq.insertrear(14); System.out.println("get rear element : " + dq.getRear()); dq.deleterear(); System.out.println("After delete rear element new rear become : " + dq.getRear()); System.out.println("inserting element at front end"); dq.insertfront(13); System.out.println("get front element: " + dq.getFront()); dq.deletefront(); System.out.println("After delete front element new front become : " + +dq.getFront()); ) )
 // Deque implementation in C #include #define MAX 10 void addFront(int *, int, int *, int *); void addRear(int *, int, int *, int *); int delFront(int *, int *, int *); int delRear(int *, int *, int *); void display(int *); int count(int *); int main() ( int arr(MAX); int front, rear, i, n; front = rear = -1; for (i = 0; i < MAX; i++) arr(i) = 0; addRear(arr, 5, &front, &rear); addFront(arr, 12, &front, &rear); addRear(arr, 11, &front, &rear); addFront(arr, 5, &front, &rear); addRear(arr, 6, &front, &rear); addFront(arr, 8, &front, &rear); printf("Elements in a deque: "); display(arr); i = delFront(arr, &front, &rear); printf("removed item: %d", i); printf("Elements in a deque after deletion: "); display(arr); addRear(arr, 16, &front, &rear); addRear(arr, 7, &front, &rear); printf("Elements in a deque after addition: "); display(arr); i = delRear(arr, &front, &rear); printf("removed item: %d", i); printf("Elements in a deque after deletion: "); display(arr); n = count(arr); printf("Total number of elements in deque: %d", n); ) void addFront(int *arr, int item, int *pfront, int *prear) ( int i, k, c; if (*pfront == 0 && *prear == MAX - 1) ( printf("Deque is full."); return; ) if (*pfront == -1) ( *pfront = *prear = 0; arr(*pfront) = item; return; ) if (*prear != MAX - 1) ( c = count(arr); k = *prear + 1; for (i = 1; i <= c; i++) ( arr(k) = arr(k - 1); k--; ) arr(k) = item; *pfront = k; (*prear)++; ) else ( (*pfront)--; arr(*pfront) = item; ) ) void addRear(int *arr, int item, int *pfront, int *prear) ( int i, k; if (*pfront == 0 && *prear == MAX - 1) ( printf("Deque is full."); return; ) if (*pfront == -1) ( *prear = *pfront = 0; arr(*prear) = item; return; ) if (*prear == MAX - 1) ( k = *pfront - 1; for (i = *pfront - 1; i < *prear; i++) ( k = i; if (k == MAX - 1) arr(k) = 0; else arr(k) = arr(i + 1); ) (*prear)--; (*pfront)--; ) (*prear)++; arr(*prear) = item; ) int delFront(int *arr, int *pfront, int *prear) ( int item; if (*pfront == -1) ( printf("Deque is empty."); return 0; ) item = arr(*pfront); arr(*pfront) = 0; if (*pfront == *prear) *pfront = *prear = -1; else (*pfront)++; return item; ) int delRear(int *arr, int *pfront, int *prear) ( int item; if (*pfront == -1) ( printf("Deque is empty."); return 0; ) item = arr(*prear); arr(*prear) = 0; (*prear)--; if (*prear == -1) *pfront = -1; return item; ) void display(int *arr) ( int i; printf(" front: "); for (i = 0; i < MAX; i++) printf(" %d", arr(i)); printf(" :rear"); ) int count(int *arr) ( int c = 0, i; for (i = 0; i < MAX; i++) ( if (arr(i) != 0) c++; ) return c; )
 // Deque implementation in C++ #include using namespace std; #define MAX 10 class Deque ( int arr(MAX); int front; int rear; int size; public: Deque(int size) ( front = -1; rear = 0; this->size = size; ) void insertfront(int key); void insertrear(int key); void deletefront(); void deleterear(); bool isFull(); bool isEmpty(); int getFront(); int getRear(); ); bool Deque::isFull() ( return ((front == 0 && rear == size - 1) || front == rear + 1); ) bool Deque::isEmpty() ( return (front == -1); ) void Deque::insertfront(int key) ( if (isFull()) ( cout << "Overflow" << endl; return; ) if (front == -1) ( front = 0; rear = 0; ) else if (front == 0) front = size - 1; else front = front - 1; arr(front) = key; ) void Deque ::insertrear(int key) ( if (isFull()) ( cout << " Overflow " << endl; return; ) if (front == -1) ( front = 0; rear = 0; ) else if (rear == size - 1) rear = 0; else rear = rear + 1; arr(rear) = key; ) void Deque ::deletefront() ( if (isEmpty()) ( cout << "Queue Underflow" << endl; return; ) if (front == rear) ( front = -1; rear = -1; ) else if (front == size - 1) front = 0; else front = front + 1; ) void Deque::deleterear() ( if (isEmpty()) ( cout << " Underflow" << endl; return; ) if (front == rear) ( front = -1; rear = -1; ) else if (rear == 0) rear = size - 1; else rear = rear - 1; ) int Deque::getFront() ( if (isEmpty()) ( cout << " Underflow" << endl; return -1; ) return arr(front); ) int Deque::getRear() ( if (isEmpty() || rear < 0) ( cout << " Underflow" << endl; return -1; ) return arr(rear); ) int main() ( Deque dq(4); cout << "insert element at rear end "; dq.insertrear(5); dq.insertrear(11); cout << "rear element: " << dq.getRear() << endl; dq.deleterear(); cout << "after deletion of the rear element, the new rear element: " << dq.getRear() << endl; cout << "insert element at front end "; dq.insertfront(8); cout << "front element: " << dq.getFront() << endl; dq.deletefront(); cout << "after deletion of front element new front element: " << dq.getFront() << endl; )

Zaman Karmaşıklığı

Yukarıdaki işlemlerin tümünün zaman karmaşıklığı sabittir, yani O(1).

Deque Data Yapısının Uygulamaları

  1. Yazılım üzerindeki geri alma işlemlerinde.
  2. Geçmişi tarayıcılarda saklamak için.
  3. Hem yığınları hem de kuyrukları uygulamak için.

Ilginç makaleler...