Konsep Stack dan Queue

Gambar diambil sebelum masa pandemi Covid-19

Gaess…

Coba deh liat gambar ini…

Lagi pada ngapain ya mereka?

Ya…

Mereka mengantri untuk bertemu idolanya.

Tahukah kamu bahwa antrian dapat disimulasikan dalam program komputer?

Ya… Kita akan belajar mengenai Stack dan Queue yang merupakan salah satu struktur data yang dipelajari di Pemrograman II. Kita akan belajar kedua struktur data tersebut.

Stack

Pernah nonton film We Bare Bears? Tahu istilah bear stack? Bear stack itu apaan sih?

Bear Stack dalam film We Bare Bears

Bear Stack itu berarti tumpukan beruang, seperti pada gambar di atas. Selain bear stack, tumpukan piring di meja makan serta tumpukan buku juga termasuk implementasi dari stack.

Terus, stack itu apa sih?

Nah, stack itu adalah struktur data yang menggunakan paradigma LIFO (Last In First Out), di mana elemen yang terakhir masuk adalah yang pertama keluar. Kayak gini deh, kalau numpuk buku, terus kita mau ngeluarin buku tersebut, kan yang pertama diambil buku yang paling atas kan? Yang dimasukin paling terakhir?

Dalam stack, ada beberapa operasi yang penting untuk diperhatikan, antara lain :

push(elemen) : memasukkan elemen ke dalam stack, sama kayak kalau masukin buku, ditaruh di paling atas.

pop() : mengambil elemen dari stack, sama kayak kalau ngeluarin buku, yang dikeluarin itu buku yang paling atas.

peek() : mencari elemen yang berada di paling atas (yang terakhir dimasukkan), namun tidak dikeluarkan.

search(elemen) : mencari elemen di dalam stack, kalau tidak ada, nilainya -1, sedangkan kalau ada, nilainya adalah indeks dari elemen tersebut (dimulai dari 1, indeks 1 adalah elemen yang paling atas).

empty() : mengecek apakah stack tersebut kosong atau tidak.

full() : mengecek apakah stack tersebut penuh atau tidak (jika dimasukkan berakibat overflow).

*Sebagian besar operasi di atas bersumber dari stack class pada Java, dalam implementasi yang akan kita bahas nama dan teknik indexing operasi tersebut bisa saja berbeda.

Nah, Stack sendiri juga dapat kita desain sendiri menggunakan paradigma OOP (Object Oriented Programming). Stack dapat diimplementasikan menggunakan Array ataupun Linked List. Stack yang diimplementasikan dengan Array biasanya bersifat statis, jika penuh maka akan terjadi stack overflow. Jadi tau kan, asal mula nama Stack Overflow dari mana? Itu bukan cuma sekedar asal namain ya, wkwkwk…

Desain Stack dengan menggunakan Array :

Desain Stack menggunakan Linked List :

Selain desain Stack seperti pada kedua contoh di atas, kita juga bisa membuat Stack Dinamis, di mana pada stack dinamis kita tidak perlu khawatir akan stack overflow. Berikut pseudocode yang ditemukan dalam buku Introduction to Algorithm, Third Edition yang ditulis oleh Thomas H. Cormen dkk. (2009) :

Pseudocode yang berasal dari buku karangan Thomas H. Cormen yang digunakan untuk pembelajaran algoritma di perkuliahan.

Intinya, dalam stack dinamis, kita bisa menggunakan operasi resize untuk memperbesar ukuran stack, sehingga menghindari terjadinya overflow. Sejauh yang aku ketahui sih, resize bisa dilakukan dengan menambah ukuran array menjadi 2 kali lipat pada saat terjadi overflow, atau seperti pada pseudocode di atas, di mana setiap kali memasukkan elemen, ukuran array bertambah 1.

Kompleksitas waktu operasi pada Stack :

Implementasi yang berbeda dapat menyebabkan kompleksitas waktunya juga berbeda

Untuk kompleksitas memori pada stack statis adalah O(1), sedangkan untuk kompleksitas memori pada stack dinamis bervariasi, biasanya antara O(1) sampai O(n).

Queue

Udah liat gambar di awal tadi?

Gambar tempat yang bikin si penulis pengen ikut ekskul teater pas SMA(Tapi kaga kesampean)? Wkwkwk…

Bukan.

Terus apa dong?

Gambar orang yang mengantri untuk bertemu idolanya yang cantik?

Hmm.. bisa aja sih kalau itu

Antrian panjang untuk menyaksikan konser idola mereka itu merupakan salah satu contoh implementasi Queue. Kalau kalian mengantri di minimarket, itu juga merupakan implementasi dari queue.

Bedanya queue sama stack apaan sih?

Ya beda, lah.

Queue merupakan struktur data yang menggunakan paradigma FIFO (First In First Out), dimana yang elemen pertama masuk adalah elemen yang pertama keluar. Gini lho logikanya, kalau kalian ngantri di Alf*mart atau Ind*maret, yang pertama dateng ke kasir yang pertama dilayani kan? Gitu deh…

Dalam queue, ada beberapa operasi yang penting untuk diperhatikan, antara lain :

enqueue(elemen) : memasukkan elemen ke dalam queue, sama kayak kalau ada orang yang baru dateng ke teater, pasti dia ada di paling belakang. (Kalau di Java interface namanya add/offer)

dequeue() : mengambil elemen dari queue, sama kayak kalau beli tiket teater, yang selesai duluan itu orang yang paling depan. (Kalau di Java interface namanya remove)

peek() : mencari elemen yang berada di paling depan (yang pertama dimasukkan), namun tidak dikeluarkan.

poll() : mencari elemen yang berada di paling depan dan dikeluarkan.

isEmpty() : mengecek apakah queue tersebut kosong atau tidak.

isFull() : mengecek apakah queue tersebut penuh atau tidak (pada Queue statis yang diimplementasikan dengan array).

Kita juga dapat mengimplementasikan Queue dengan menggunakan paradigma OOP, seperti pada stack. Queue dapat diimplementasikan dengan linear array, circular array, array list, ataupun dengan linked list. Namun, yang akan kita bahas saat ini hanyalah implementasi dengan linear array dan juga linked list.

Desain Queue dengan menggunakan Array :

Desain Queue menggunakan Linked List :

Kompleksitas operasi pada Queue :

Implementasi yang berbeda dapat menyebabkan kompleksitas waktunya juga berbeda.

Untuk kompleksitas memori pada queue adalah O(1).

Operasi Lanjut pada Stack dan Queue

Selain operasi-operasi pada contoh di atas, masih banyak operasi lain yang dapat dilakukan pada stack dan queue, namun karena keterbatasan waktu, mungkin baru bisa dilanjutkan di post selanjutnya. Terima kasih telah menyimak uraian mengenai konsep dasar stack dan queue pada post ini. Semoga kalian selalu diberikan kesehatan dan kekuatan dari Tuhan Yang Maha Kuasa, stay safe, dan sampai jumpa.

Daftar Pustaka

Cormen, Thomas. 2009. Introduction to Algorithm, Third Edition. Massasuchetts : The MIT Press.

https://www.techiedelight.com/stack-implementation-in-java/. Diakses tanggal 10 September 2020.

https://www.techiedelight.com/queue-implementation-in-java/. Diakses tanggal 10 September 2020

https://www.techiedelight.com/queue-implementation-using-linked-list/. Diakses tanggal 10 September 2020

https://www.techiedelight.com/stack-implementation-using-linked-list/. Diakses tanggal 10 September 2020

https://www.tutorialspoint.com/javaexamples/data_stack.htm. Diakses tanggal 10 September 2020

https://www.geeksforgeeks.org/implement-a-stack-using-singly-linked-list/. Diakses tanggal 10 September 2020