Queue dan Stack

1.  Pengenalan Queue

Queue jika diartikan secara harfiah, queue berarti antrean, Queue merupakan suatu struktur data linear. Konsepnya hampir sama dengan Stack, perbedaannya adalah operasi penambahan dan penghapusan pada ujung yang bebeda. Pada Stack atau tumpukan menggunakan prinsip “Masuk terakhir keluar pertama”atau LIFO (Last In First Out), Maka pada Queue atau antrean prinsip yang digunakan adalah “Masuk Pertama Keluar Pertama” atau FIFO (First In First Out). Data-data di dalam antrean dapat bertipe integer, real, record dalam bentuk sederhana atau terstruktur.

Queue (antrean) adalah salah satu list linier dari struktur data yang beroperasi dengan cara First In First Out (FIFO) yaitu elemen pertama yang masuk merupakan elemen yang pertama keluar. Contohnya, ialah dalam sebuah antrean pembelian tiket bagi yang pertama masuk maka dia pulalah yang pertama keluar/selesai. Untuk penyisipan (INSERT) hanya dapat dilakukan pada satu sisi yaitu sisi belakang (REAR), sedangkan untuk penghapusan (REMOVE) pada sisi depan (FRONT) dari list.      

Queue/antrean adalah ordered list dengan penyisipan di satu ujung, sedang penghapusan di ujung lain. Ujung penyisipan biasa disebut rear/tail, sedang ujung penghapusa disebut front/head. Fenomena yang muncul adalah elemen yang lebih dulu disisipkan akan juga lebih dulu diambil. Queue merupakan kasus khusus ordered list. Dengan karakteristik terbatas itu maka kita dapat melakukan optimasi representasi ADT Queue untuk memperoleh kerja paling optimal.

Misalnya Queue Q= (a1,a2,a3…,an), maka:

1.      Elemen a1 adalah elemen paling depan

2.      Elemen ai adalah diatas elemen ai-1, di mana 1<i<n.

3.      Elemen an adalah elemen paling belakang.

Head (Front) menunjuk ke awal antrean Q (elemen terdepan), sedangkan tail (rear)menunjuk akhir antrean Q (elemen paling belakang). Disiplin FIFO pada Queue berimplikasi jika elemen A, B, C, D, E dimasukkan ke Queue, maka penghapusan/ pengambilan elemen akan terjadi dengan urutan A, B, C, D, E.

Sebagai gambaran, cara kerja queue dapat disamakan pada sebuah antrean di suatu loket dimana berlaku prinsip ‘Siapa yang duluan antre dia yang akan pertama kali dilayani‘, sehingga dapat dikatakan prinsip kerja queue sama dengan prinsip sebuah antrean.   

2.  Pengenalan Stack

Stack juga termasuk salah satu jenis list. Dalam bahasa indonesia stack biasa disebut juga sebagai tumpukan. Sama seperti queue, stack juga memiliki sifat atau operasi tertentu yang membedakannya dari list secara umum. Ukuran stack dapat ditentukan pada saat deklarasi. Jadi stack tersebut hanya mampu menampung sekian elemen sesuai dengan yang dideklarasikan di awal. Hal ini menyebabkan adanya operasi pada stack untuk mengetahui kondisi stack apakah kosong  (isEmpty) atau penuh (isFull). Selain itu, ada dua operasi pada stack yaitu menambahkan tumpukan (Push) atau mengambil tumpukan (Pop). Perintah Push akan menambah jumlah elemen dalam tumpukan dan harus didahului dengan perintah isFull. Hal ini dilakukan untuk menjamin bahwa masih ada ruang yang kosong untuk menambahkan elemen baru pada stack. Adapun perintah Pop akan mengambil elemen paling atas pada tumpukan sehingga jumlah elemen berkurang dan harus didahului dengan perintah isEmpty. Mengapa? karena sebelum mengambil sebuah elemen pada stack harus dipastikan dulu bahwa stack tersebut tidak kosong. Berbeda dengan Queue, Stack menganut prinsip Last In First Out (LIFO). Elemen yang terakhir masuk ke dalam stack akan pertama kali dikeluarkan karena sifat stack yang membatasi operasi hanya bisa dilakukan pada salah satu sisinya saja (bagian atas tumpukan).