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

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.
- Ambil larik (deque) dengan ukuran n.
- Setel dua petunjuk di posisi pertama dan setel
front = -1
danrear = 0
.

1. Sisipkan di Depan
Operasi ini menambahkan elemen di depan.
- Periksa posisi depan.
Periksa posisi depan
- Jika
front < 1
, inisialisasi ulangfront = n-1
(indeks terakhir).Geser dari depan ke ujung
- Lain, kurangi depan sebanyak 1.
- Tambahkan kunci baru 5 ke dalam
array(front)
.Masukkan elemen di Depan
2. Masukkan di Belakang
Operasi ini menambahkan elemen ke belakang.
- Periksa apakah array sudah penuh.
Periksa apakah deque sudah penuh
- Jika deque sudah penuh, inisialisasi ulang
rear = 0
. - Lain, tingkatkan belakang sebesar 1.
Tingkatkan bagian belakang
- Tambahkan kunci baru 5 ke dalam
array(rear)
.Masukkan elemen di belakang
3. Hapus dari Depan
Operasi tersebut menghapus elemen dari depan.
- Periksa apakah deque kosong.
Periksa apakah deque kosong
- Jika deque kosong (mis.
front = -1
), Penghapusan tidak dapat dilakukan ( kondisi underflow ). - Jika deque hanya memiliki satu elemen (yaitu
front = rear
), setelfront = -1
danrear = -1
. - Lain jika depan di akhir (yaitu
front = n - 1
), setel ke depanfront = 0
. - Lain
front = front + 1
,.Tingkatkan bagian depan
4. Hapus dari Belakang
Operasi ini menghapus elemen dari belakang.
- Periksa apakah deque kosong.
Periksa apakah deque kosong
- Jika deque kosong (mis.
front = -1
), Penghapusan tidak dapat dilakukan ( kondisi underflow ). - Jika deque hanya memiliki satu elemen (yaitu
front = rear
), setelfront = -1
danrear = -1
, jika tidak, ikuti langkah-langkah di bawah ini. - Jika belakang berada di depan (mis.
rear = 0
), Setel ke depanrear = n - 1
. - Lain
rear = rear - 1
,.Turunkan bagian belakang
5. Centang Empty
Operasi ini memeriksa apakah deque kosong. Jika front = -1
deque kosong.
6. Periksa Penuh
Operasi ini memeriksa apakah deque sudah penuh. Jika front = 0
dan rear = n - 1
OR 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
- Dalam operasi pembatalan pada perangkat lunak.
- Untuk menyimpan sejarah di browser.
- Untuk mengimplementasikan tumpukan dan antrian.