Pengenalan Algortima dan Struktur Data - BAB 3 Stack dan Queue

BAB 3 STACK DAN QUEUE

CPMK2/CO2: Mahasiswa mampu menjelaskan struktur data linier string, linked list, stack dan queue

3.1 Pendahuluan

Pada pembahasan kali ini kita akan belajar mengenal dan memahami apa itu Stack dan Queue. Apa Stack dan Queue itu? Stack memiliki arti yaitu tumpukan sedangkan Queue memiliki arti antrian. Stack sendiri merupakan tumpukan elemen yang mana pengambilannya dilakukan di bagian atas yang terakhir masuk. Queue merupakan antrian elemen.

3.2 Stack

Seperti yang sudah disebutkan di atas, Stack merupakan tumpukan elemen yang mana pengambilannya dilakukan pada elemen terakhir yang masuk. Sebuah ilustrasi untuk memudahkan memberikan gambaran mengenai stack dapat diilustrasikan seperti seseorang menumpuk 5 buku seperti yang ditunjukkan pada gambar 8. Buku tersebut ditumpuk dengan urutan buku paling bawah adalah buku pertama, di atas buku pertama ada buku kedua. Selanjutnya setelah buku kedua di atasnya ada buku ketiga. Buku selanjutnya adalah buku keempat yang berada di atas buku ketiga, sedangkan buku terakhir atau paling atas adalah buku kelima. Ketika orang tersebut akan menata buku tersebut di rak buku, buku yang diambil terlebih dahulu adalah buku kelima atau buku paling atas di tumpukan tadi. Ilustrasi tersebut menggambarkan bahwa Stack memiliki aturan Last In First Out atau dapat disingkat LIFO. Dengan aturan ini memungkinkan elemen yang menjadi terakhir masuk ke dalam tumpukan menjadi elemen pertama yang diambil. Tumpukan elemen pada aturan Stack memberikan gambaran elemen dimasukkan menumpuk di atas elemen yang sudah ada.

Gambar 8. LIFO

Stack diharuskan memiliki elemen paling atas atau top dan daftar elemen yang akan dijadikan stack. Elemen di sini bisa juga kita gambarkan sebagai data atau sebuah nilai. Urutan elemen pada Stack dimulai dari kiri ke kanan, sehingga elemen paling kanan menjadi elemen top-nya. Selain itu Stack memiliki dua operasi yaitu memasukkan elemen dan mengambil elemen. Operasi untuk memasukkan ke tumpukan stack menggunakan PUSH, sedangkan untuk mengambil dari tumpukan Stack menggunakan POP.

PUSH merupakan operasi Stack yang digunakan untuk memasukkan elemen atau data ke dalam Stack. Berikut ini merupakan alur bagaimana melakukan PUSH di Stack:

1. Tentukan Stack dalam keadaan Null List (kosong) atau tidak
2. Menyiapkan elemen-elemen yang akan dimasukkan ke Stack apabila dalam keadaan Null List
3. Masukkan elemen baru ke dalam Stack
4. Masukkan elemen atau data hingga batas yang ditentukan (looping)
5. Tumpukkan elemen atau data di dalam Stack sudah tertumpuk rapi dengan elemen atau data paling kanan merupakan top of the Stack-nya.
6. Selesai

Mari kita perhatikan pada gambar 9. pada gambar 9 tersedia beberapa elemen yang nantinya akan dijadikan sebuah Stack. Elemen-elemen tersebut dimasukkan Stack bernama S. Kemudian seseorang memasukkan elemen-elemen tersebut menggunakan PUSH ke dalam Stack satu per satu, dimulai dari AB, BC, CD, dan terakhir DE dengan menggunakan perintah PUSH() seperti pada huruf c. Sesuai dengan alur pada huruf d, elemen-elemen tersebut memiliki awalan AB dan akhiran DE sebagai top of the Stack-nya. Gambar 9. Alur PUSH pada Stack

POP merupakan operasi Stack untuk mengambil elemen atau data dari Stack. Pengambilan ini dilakukan dengan mengambil elemen atau data paling akhir yang masuk. Pengambilan menggunakan POP sekaligus digunakan untuk menghapus data di Stack.

Algoritma untuk melakukan POP sebagai berikut:

• Cek Stack yang berisi elemen-elemen atau beberapa data
• Data tidak Null List maka dapat dilakukan POP
• Melakukan perintah POP pada tumpukan yang sudah ada dengan perintah POP()
• Isi Stack akan berkurang dari kanan ke kiri sesuai dengan perintah POP yang dilakukan
• Selesai

Dapat diperhatikan pada gambar 10, terdapat tumpukkan Stack dengan elemen AB, BC, CD, dan DE. Kemudian dilakukan pengambilan elemen menggunakan POP(). Elemen yang terakhir masuk dihilangkan dari Stack. Jika dilakukan POP lagi maka elemen CD akan dihilangkan dari Stack. 

Gambar 10. Alur POP Stack

3.3 Queue

Stack dan Queue memiliki kesamaan sama-sama suatu list. Sedangkan untuk perbedaannya terletak dari memasukkan elemen dan mengeluarkan elemennya. Jika Stack memiliki sifat Last In First Out, Queue memiliki sifat First In First Out atau sering disebut dengan FIFO. Queue memiliki artian elemen yang pertama kali dimasukkan ke dalam Queue akan dikeluarkan lebih dahulu dari Queue. Sebagai ilustrasi untuk mempermudah penggambaran bayangkan kalian sedang berada di sebuah antrian pengisian bahan bakar. Di tempat tersebut siapa yang duluan datang akan duluan dilayani. Kemudian setelah itu urutan kedua yang dilayani dan seterusnya. Sebagai ilustrasi lagi ketika kita mengantri ke tempat makan cepat saji, disitu kita mengantri dan siapa yang datang duluan yang dilayani duluan. Nah seperti itulah ilustrasi dari Queue. Elemen paling awal disebut Head di dalam Queue, elemen terakhir disebut Tail. Jadi dalam Queue ini penambahan dari head ke tail, namun dalam pengambilan elemen atau data dari head perhatikan pada gambar 11.

Gambar 11. Queue

 Sama seperti Stack, Queue memiliki dua operator yaitu Enqueue dan Dequeue. Enqueue seperti PUSH di Stack digunakan untuk memasukkan elemen atau data ke urutan atau List. Sedangkan Dequeue seperti POP di Stack yaitu digunakan sebagai pengambil elemen atau data di urutan atau List.

Enqueue merupakan operasi memasukkan elemen atau data ke dalam Queue sama seperti PUSH di Stack. Di dalam Queue elemen yang baru masuk akan menjadi Tail. Elemen atau data yang pertama masuk akan menjadi Head. Perhatikan pada gambar 12, digambar tersebut terlihat bahwa sebuah list Queue kosong. Kemudian Queue tersebut diberikan elemen baru menggunakan perintah Enqueue. Hasil dari elemen baru tersebut membuat elemen baru menjadi Head sekaligus Tail di Queue. Kenapa? Karena tidak ada elemen baru lagi yang ditambahkan. Apabila ada elemen baru yang dimasukkan, maka Head akan tetap pada elemen AB.

Gambar 12. Alur Enqueue

Berikut algoritma dari Enqueue:

• Tentukan Queue dalam keadaan Null List atau tidak
• Menyiapkan elemen-elemen yang akan dimasukkan ke Queue apabila dalam keadaan Null List
• Masukkan elemen baru ke Queue
• Lakukan looping untuk memasukkan elemen baru
• Jika Queue sudah penuh maka dihentikan
• Selesai

Dequeue merupakan operasi mengambil elemen atau data ke dalam Queue sama seperti POP di Stack. Namun elemen yang diambil merupakan elemen yang awal masuk atau yang menjadi Head. Di dalam Queue elemen yang baru masuk akan menjadi Tail. Perhatikan pada gambar 13, digambar tersebut terlihat bahwa sebuah list Queue kosong. Kemudian Queue tersebut diberikan elemen baru menggunakan perintah Enqueue. Hasil dari elemen baru tersebut membuat elemen baru menjadi Head sekaligus Tail di Queue. Kenapa? Karena tidak ada elemen baru lagi yang ditambahkan. Apabila ada elemen baru yang dimasukkan, maka Head akan tetap pada elemen AB.

Gambar 13. Alur Dequeue

Berikut algoritma dari Dequeue:

• Cek list Queue sudah terisi atau null list
• Data ada maka dapat dilakukan Dequeue, apabila null list maka hentikan
• Melakukan perintah Dequeue pada Queue yang sudah ada
• Isi Queue akan berkurang dari Head ke Tail
• Lakukan sampai data habis
• Selesai

Subscribe Our Newsletter