Struktur Data - Queue

Selamat datang kembali dipembelajaran algoritma dan struktur data. Pada materi sebelumnya kita sudah masuk dasar struktur data dan membahas tentang stack. Selain stack, ada juga yang dimaksud queue. Bayangkan jika ada sederetan orang yang menunggu untuk mendapatkan ‘sesuatu’ secara bergantian, sehingga cara kerjanya adalah orang yang sudah berada di garis terpanjang akan mendapatkan ‘sesuatu’ tersebut dan keluar terlebih dahulu. Orang lain dapat bergabung pada garis tetapi hanya orang-orang yang lebih dulu mendapatkan ‘sesuatu’ tersebut yang terlebih dahulu dan keluar. Anda mungkin bisa menyebutnya sebagai struktur data input pertama, atau, struktur output pertama, keluar pertama kali atau bahasanya dalam struktur data adalah queue.

queue ini sebenarnya kebalikan dari stack dengan cara ini. Dalam stack, elemen yang paling baru ditambahkan akan keluar/out terlebih dahulu, tetapi pada queue elemen paling lama keluar terlebih dahulu. Kalau tidak, queue sebenarnya akan sangat mirip dengan stack. Elemen pertama dalam queue atau elemen tertua dalam antrian, disebut head.

Elemen terakhir dalam antrian, atau elemen terbaru dalam antrian, disebut tail. Saat Anda menambahkan elemen ke tail, Operasi ini disebut enqueue. Ketika Anda menghapus elemen head, operasi disebut dequeue. Ada juga operasi yang disebut peek, di mana Anda melihat elemen head tetapi Anda tidak benar-benar menghapusnya. Sekali lagi, Anda dapat menerapkan struktur data ini dengan linked list(yang akan dibahas dimateri selanjutnya), di mana Anda juga menyimpan referensi ke head dan tail sehingga Anda dapat melihatnya keduanya dalam waktu yang konstan.

Jika pada stack terdapat LIFO (Last In First Out), demikian pula, dalam queue, elemen yang dihapus selalu merupakan salah satu yang telah di set untuk waktu terlama: queue menerapkan kebijakan pertama masuk(First-In), keluar pertama(First-Out), atau FIFO.

Sekarang akan kita jelaskan operasi pada queue ini. Kita memanggil operasi INSERT pada queue ENQUEUE, dan kita memanggil DELETE operasi DEQUEUE, seperti operasi stack POP, DEQUEUE tidak membutuhkan argumen elemen. Properti FIFO dari antrian menyebabkannya beroperasi seperti antrian pelanggan yang menunggu untuk membayar kasir. queue memiliki head dan tail. Ketika sebuah elemen diantisipasi, ia mengambil tempat di bagian tail queue, tepat ketika pelanggan yang baru tiba mengambil tempat di ujung antrian. Elemen dequeued selalu yang ada di head antrian, seperti pelanggan di garis depan yang menunggu paling lama.

Gambar dibawah menunjukkan salah satu cara untuk menerapkan queue paling banyak elemen n-1 menggunakan array Q [1..n]. queue memiliki atribut Q.head yang mengindeks, atau menunjuk ke head. Atribut Q.tail mengindeks lokasi berikutnya di mana elemen baru tiba akan dimasukkan ke antrian. Elemen-elemen dalam antrian berada di lokasi Q.head; Q.head + 1, ……… Q.tail - 1, di mana kita “membungkus” dalam arti bahwa lokasi 1 segera mengikuti lokasi n dalam urutan melingkar. Awalnya, kami memiliki Q.head = Q.tail = 1. Jika kita mencoba mendequeue elemen dari empty queue, queue underflow.

box1

Queue diimplementasikan menggunakan array Q [1..12]. Elemen queue hanya muncul dalam posisi berbayang ringan. (a) Queue memiliki 5 elemen, di lokasi Q [7..11]

box2

(b) Konfigurasi queue setelah panggilan ENQUEUE (Q, 17), ENQUEUE (Q, 3), dan ENQUEUE (Q, 5).

box3

© Konfigurasi queue setelah panggilan DEQUEUE (Q) mengembalikan nilai kunci 15 sebelumnya di head queue. Head baru memiliki key 6.

Ketika Q.head: Q.tail + 1, queue penuh, dan jika kita mencoba untuk memasukkan elemen, maka antrian akan meluap atau overflow. Dalam prosedur kita, ENQUEUE dan DEQUEUE, kita telah menghilangkan kesalahan pemeriksaan(error checking) underflow dan overflow. Pseudocode mengasumsikan bahwa n = Q.length.

ENQUEUE(Q,x)
Q[Q.tail] = x
if Q.tail == Q.length
     Q.tail =  1
else Q.tail = Q.tail + 1


DEQUEUE(Q)
x = Q.[Q.head]
if Q.head = = Q.length
      Q.head = 1
else  Q.head = Q.head + 1
return x

Gambar operasi diatas menunjukkan efek dari operasi ENQUEUE dan DEQUEUE. Setiap operasi membutuhkan O (1) / waktu.