Struktur Data Deque

Dalam tutorial ini, Anda akan mempelajari apa itu antrian berujung ganda (deque). Selain itu, Anda akan menemukan contoh kerja dari operasi yang berbeda pada deque di C, C ++, Java dan Python.

Deque atau Double Berakhir Queue adalah jenis antrian di mana penyisipan dan penghapusan elemen dapat dilakukan baik dari depan atau belakang. Dengan demikian, tidak mengikuti aturan FIFO (First In First Out).

Representasi dari Deque

Jenis-jenis Deque

  • Input Restricted Deque
    Dalam deque ini, input dibatasi di satu ujung tetapi memungkinkan penghapusan di kedua ujungnya.
  • Output Restricted Deque
    Dalam deque ini, output dibatasi pada satu ujung tetapi memungkinkan penyisipan di kedua ujungnya.

Operasi di Deque

Di bawah ini adalah implementasi array melingkar dari deque. Dalam larik melingkar, jika larik sudah penuh, kita mulai dari awal.

Namun dalam implementasi array linier, jika array sudah penuh, tidak ada lagi elemen yang dapat disisipkan. Dalam setiap operasi di bawah ini, jika arraynya penuh, "pesan luapan" dilemparkan.

Sebelum melakukan operasi berikut, ikuti langkah-langkah ini.

  1. Ambil larik (deque) dengan ukuran n.
  2. Setel dua petunjuk di posisi pertama dan setel front = -1dan rear = 0.
Inisialisasi array dan pointer untuk deque

1. Sisipkan di Depan

Operasi ini menambahkan elemen di depan.

  1. Periksa posisi depan. Periksa posisi depan
  2. Jika front < 1, inisialisasi ulang front = n-1(indeks terakhir). Geser dari depan ke ujung
  3. Lain, kurangi depan sebanyak 1.
  4. Tambahkan kunci baru 5 ke dalam array(front). Masukkan elemen di Depan

2. Masukkan di Belakang

Operasi ini menambahkan elemen ke belakang.

  1. Periksa apakah array sudah penuh. Periksa apakah deque sudah penuh
  2. Jika deque sudah penuh, inisialisasi ulang rear = 0.
  3. Lain, tingkatkan belakang sebesar 1. Tingkatkan bagian belakang
  4. Tambahkan kunci baru 5 ke dalam array(rear). Masukkan elemen di belakang

3. Hapus dari Depan

Operasi tersebut menghapus elemen dari depan.

  1. Periksa apakah deque kosong. Periksa apakah deque kosong
  2. Jika deque kosong (mis. front = -1), Penghapusan tidak dapat dilakukan ( kondisi underflow ).
  3. Jika deque hanya memiliki satu elemen (yaitu front = rear), setel front = -1dan rear = -1.
  4. Lain jika depan di akhir (yaitu front = n - 1), setel ke depan front = 0.
  5. Lain front = front + 1,. Tingkatkan bagian depan

4. Hapus dari Belakang

Operasi ini menghapus elemen dari belakang.

  1. Periksa apakah deque kosong. Periksa apakah deque kosong
  2. Jika deque kosong (mis. front = -1), Penghapusan tidak dapat dilakukan ( kondisi underflow ).
  3. Jika deque hanya memiliki satu elemen (yaitu front = rear), setel front = -1dan rear = -1, jika tidak, ikuti langkah-langkah di bawah ini.
  4. Jika belakang berada di depan (mis. rear = 0), Setel ke depan rear = n - 1.
  5. Lain rear = rear - 1,. Turunkan bagian belakang

5. Centang Empty

Operasi ini memeriksa apakah deque kosong. Jika front = -1deque kosong.

6. Periksa Penuh

Operasi ini memeriksa apakah deque sudah penuh. Jika front = 0dan rear = n - 1OR front = rear + 1, deque sudah penuh.

Implementasi Deque dengan Python, Java, C, dan C ++

Python Java 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; )

Kompleksitas Waktu

Kompleksitas waktu dari semua operasi di atas adalah konstan yaitu O(1).

Aplikasi Struktur Data Deque

  1. Dalam operasi pembatalan pada perangkat lunak.
  2. Untuk menyimpan sejarah di browser.
  3. Untuk mengimplementasikan tumpukan dan antrian.

Artikel yang menarik...