Double Endeed Queue

DEQUE DeQue adalah kependekan dari Double Ended QUEUE ( Antrian dengan ujung ganda ). Pada deque, proses memasukkan dan mengeluarkan atau menghapus data dapat dilakukan dari kedua sisi antrian. Perhatikan ilustrasi berikut. Pada gambar di atas tampak sebuah tabung, jika tabung tersebut akan diisi air maka air dapat diisikan melalui kedua sisi (kanan dan kiri) tabung tersebut. Begitu pula air dapat dikeluarkan melalui kedua sisi tabung tersebut. Perhatikan pula gambar kalung berikut. Pada gambar di atas tampak sebuah kalung. Kalung di atas dapat diisi dengan manik-manik atau biji-bijian dari kedua ujungnya. Sedangkan untuk mengeluarkan manik-manik yang berada di bagian tengah harus lebih dahulu mengeluarkan manik-manik yang terluar baik dari kiri maupun kanan. Berikut merupakan representasi Double Ended Queue dalam array satu dimensi Misalnya ilustrasi di atas kita isikan dengan angka. Proses insert dan delete 1.      INSERT KANAN, Masuk dari kanan 2.      INSERT KIRI, Masuk dari kiri 3.      DELETE KANAN, keluar dari kanan 4.      DELETE KIRI, keluar dari kiri Contoh proses : Misalnya ada perintah masuk dari kanan maka akan masuk di elemen nomor 6 dan indeks  R  akan menunjuk elemen nomor 6. Begitu pun seterusnya jika akan diisi dari kanan. Berikut adalah gambar ilustrasinya. Algoritma :  R = R + 1;                Q[R] = X;   Jika ada perintah masuk dari kiri maka akan masuk di elemen nomor 2 dan indeks  R  akan menunjuk elemen nomor 2. Begitu pun seterusnya jika akan diisi dari kiri. Berikut adalah gambar ilustrasinya. Algoritma :  L = L - 1;                Q[L] = X;   Jika ada perintah keluar dari kanan, maka yang akan keluar adalah isi elemen nomor 5 dan indeks  R  akan menunjuk elemen nomor 4. Begitu pun seterusnya jika akan keluar dari kanan. Berikut adalah gambar ilustrasinya. Algoritma :  X = Q[R];                R = R - 1;   Jika ada perintah keluar dari kiri, maka yang akan keluar adalah isi elemen nomor 3 dan indeks  L  akan menunjuk elemen nomor 4. Begitu pun seterusnya jika akan keluar dari kiri. Berikut adalah gambar ilustrasinya. Algoritma :  X = Q[L];                L = L + 1; PROSES Prinsip proses pada DeQue bukan  FIFO  bukan juga LIFO tapi keluar masuk dari kedua ujungnya  sesuai dengan kesempatan yang ada. Apabila ada ruang yang memungkinkan diisi dari kanan atau kiri maka proses pemasukkan data bisa dilakukan. Proses yang dapat dilakukan pada DeQue adalah : a.       AWAL (Inisialisasi) b.      INSERT (Sisip, Masuk, Simpan, Tulis) c.       DELETE ( Hapus, Keluar, Ambil, Baca) Proses AWAL (Inisialisasi) Algoritma dasar untuk proses awal void AWAL(void) {  L  =  0;    R  =  -1;     } Ilustrasi hasil proses awal Kondisi awal R = R + 1; Q[R] = X;   Pada saat keadaan seperti gambar di atas maka proses yang dapat dilakukan hanya insert kanan. Misalnya akan memasukkan data, maka R maju 1 langkah lalu isi tempat yang ditunjuk oleh R dengan Q[R] = X;. Jika X = 25 maka hasilnya : Lalu, bagaimana hasilnya jika insert kiri? Berikut ilustrasi gambarnya : Pada gambar di atas awalnya L maju satu langkah dan itu tidak error, namun ketika akan diisi hasilnya akan error karena tidak ada tempat untuk diisi. Proses INSERT Algoritma dasar untuk proses INSERT Insert Kiri Insert Kanan void INSERT_KIRI(void) { L = L - 1;   Q[L] = X; } void INSERT_KANAN(void) { R = R + 1;   Q[R] = X; }   Proses DELETE Algoritma dasar untuk proses DELETE Delete Kiri Delete Kanan void DELETE_KIRI(void) {   X = Q[L];     L = L + 1; } void DELETE_KANAN(void) { X = Q[R];   R = R - 1; }  KONDISI ANTRIAN a.       KOSONG       : Tak ada yang bisa diambil b.      PENUH          : Penuh Kanan (Tak bisa diisi dari kanan) atau Penuh Kiri (Tak bisa diisi dari kiri) c.       BISA DIISI      : Bisa diisi dari Kanan atau bisa diisi dari Kiri d.      ADA ISINYA   : Bisa keluar baik dari kanan maupun dari kiri    Perhatikan gambar berikut : Kondisi Antrian Gambar Ciri Kosong 1, 5, 7 L == R + 1 atau R == L - 1 Penuh kanan 6, 7, 8 R == n-1 Penuh kiri 1, 2, 8 L == 0 Penuh kanan dan kiri 8 R == n-1 && L == 0 Bisa diisi dari kanan 1, 2, 3, 4, 5 R < n Bisa diisi dari kiri 3, 4, 5, 6, 7 L > 0 Ada isinya 2, 3, 4, 6, 8 L < R+1  atau L <= R atau R > L-1 atau R >= L   Algoritma yang lengkap untuk proses INSERT dan DELETE Proses Kiri Kanan INSERT void INSERT_KIRI(void) { if ( L > 0)     { L = L - 1;       Q[L]  =  X;     }   else     printf("Antrian Penuh Kiri") } void INSERT_KANAN(void) { if (R < n-1)    { R  =  R + 1;      Q[R]  =  X; }   else     printf("Antrian Penuh Kanan"); }       DELETE void DELETE_KIRI(void) { if(L < R+1)    { X = Q[L]; }      L = L + 1; else    printf("Antrian Kosong"); } void DELETE_KANAN(void) { if(L < R+1)     { X  =  Q[R];       R   =   R - 1; }   else     printf("Antrian Kosong"); }