pengertian stack dan queue dalam struktur data dan penjelasannya

Assalamualaikum pada kesempatan kali ini kita akan belajar tentang stack dan queue. pada pelajaran sebelumnya kita telah belajar tentang double linked list struktur data yang memiliki 2 penyambung yaitu next dan prev. oke pada pembahasan kali ini kita akan belajar tentang stack dan queue. stack berarti tumpukan yang berarti kita menggunakan operasi addfront dan delfront atau addback dan delback. sedangkan queue merupakan sebuah antrian dan biasa menggunakan operasi addfront dan delback atau addback atau delfront. oke mungkin teman-teman masih bingung dengan inti dari argumen yang admin berikan. langsung saja teman-teman ringkasan pembahasan yang admin tulis. selamat belajar. 

array dan single linked list Read Now
Double Linked List Read Now
Stack AND Queue Read Now
Tree Read Now
Graph Read Now

1. Stack

Stack atau tumpukan dapat diartikan sebagai suatu kumpulan data yang seolah-olah terlihat seperti ada data yang diletakkan di atas data yang lain. Kaidah utama dalam konsep stack adalah LIFO yang merupakan singkatan dari Last In First Out, artinya adalah data yang terakhir kali dimasukkan atau disimpan, maka data tersebut adalah yang pertama kali akan diakses atau dikeluarkan.^[4] Berikut ilustrasi kerja sebuah stack:

      

Gambar 3 .1 Ilustrasi stack

Sebuah struktur data dari sebuah stack setidaknya harus mengandung dua buah variabel, misalnya variabel top yang akan berguna sebagai penanda bagian atas tumpukan dan array data dari yang akan menyimpan data-data yang dimasukkan ke dalam stack tersebut.

Deklarasi struktur data dari sebuah stack:

Stack(){  ListNode top;
Stack(); // create empty stack
void push(Object obj); // push object to stack
Object pop(); // get & throw top element
Object top(); // get top element
boolean isEmpty(); // check if stack empty
}

Operasi-operasi dasar dalam stack ada 2 yaitu operasi push dan pop:

• Operasi push, berfungsi untuk memasukkan sebuah nilai atau data ke dalam stack. Sebelum sebuah nilai atau data dimasukkan ke dalamstack, prosedur ini terlebih dahulu akan menaikkan posisi top satu level ke atas.^[5] Berikut ilustrasi kerja pada operasi push:

Gambar 3.2 Ilustrasi kerja operasi push

• Operasi pop, berfungsi untuk mengeluarkan atau menghapus nilai terakhir (yang berada pada posisi paling atas) dari stack, dengan cara menurunkan nilai top satu level ke bawah. ^[5] Berikut ilustrasi kerja pada operasi pop:

Gambar 3.3 Ilustrasi kerja operasi pop

2. Queue
pengertian queue dalam struktur data

Queue atau antrian merupakan struktur data linear dimana penambahan komponen dilakukan disatu ujung, sementara pengurangan dilakukan diujung lain. Kaidah utama dalam konsep queue adalah FIFO yang merupakan singkatan dari First In First Out, artinya adalah data yang pertama kali dimasukkan atau disimpan, maka data tersebut adalah yang pertama kali akan diakses atau dikeluarkan.^[4]

      

Gambar 3.4 Ilustrasi queue

Sebuah queue di dalam program komputer dideklarasikan sebagai sebuah tipe bentukan baru. Sebuah struktur data dari sebuah queue setidaknya harus mengandung dua tiga variabel, yakni variabel head yang akan berguna sebagai penanda bagian depan antrian, variabeltail yang akan berguna sebagai penanda bagian belakang antrian danarray dari yang akan menyimpan data-data yang dimasukkan ke dalam queue tersebut. Deklarasi struktur data dari sebuah queue :

Queue(){ListNode front;
ListNode end;
Queue(); // create empty queue
void add(Object obj); // add object to queue
Object remove(); // get & throw top element
ListNode getFront(); // get top element
boolean isEmpty(); // check if stack empty
}

Operasi-operasi dasar dalam stack ada 2 yaitu operasi enqueue dan dequeue:

• Operasi enqueue, digunakan untuk memasukkan sebuah data atau nilai ke dalam queue. Pada proses enqueue, tail -lah yang berjalan seiring masuknya data baru ke dalam antrian, sedangkan head akan tetap pada posisi ke-1.^[1]

Gambar 3.5 Ilustrasi kerja operasi enqueue

• Operasi dequeue, digunakan untuk menghapuskan sebuah data atau nilai yang paling awal masuk ke dalam queue. Operasi ini menaikkan nilai head satu level.^[1]

Gambar 3.6 Ilustrasi kerja operasi dequeue

3. Algoritma Stack

a. Operasi Push

Operasi push digunakan untuk menambahkan sebuah elemen baru ke atas tumpukan. Operasi ini dapat dilakukan jika tumpukan tidak penuh. ^[3] Algoritma operasi push pada stack adalah sebagai berikut:

• Menentukan kondisi tumpukan, apakah tumpukan dalam keadaan kosong atau tidak.
• Jika kosong maka mendeklarasikan data baru yang akan dimasukkan ke dalam tumpukan.
• Memasukkan nilai data yang baru.
• Melakukan perulangan untuk memasukkan data hingga batas penuh tumpukan.
• Jika tumpukan sudah penuh maka selesai.

b. Operasi Pop

Operasi pop digunakan untuk menghapus elemen teratas dari tumpukan.^[3] Algoritma operasi pop pada stack adalah sebagai berikut:

•  Melakukan pengecekan kondisi antrian, ada isi data atau tidak.
•  Jika terdapat data pada antrian, maka lakukan penghapusan data dengan cara memindahkan head (elemen teratas tumpukan) ke elemen dibawahnya.
• Kemudian menghapus elemen teratas tumpukan.
• Jika tidak terdapat data pada tumpukan maka selesai.

3. Algoritma Queue
operasi pada queue

a. Operasi Enqueue

Operasi push pada antrian disebut juga enqueue. Operasi ini digunakan untuk menambah sebuah elemen baru. Elemen baru akan dimasukkan ke belakang antrian.^[3] Algoritma operasi push pada queue adalah sebagai berikut:

• Menentukan kondisi antrian, apakah antrian dalam keadaan kosong atau tidak.
• Jika kosong maka mendeklarasikan data baru yang akan dimasukkan ke dalam antrian.
• Memasukkan nilai data yang baru.
• Melakukan perulangan untuk memasukkan data hingga batas penuh antrian dengan cara menempatkan penunjuk front menunjuk ke elemen terdepan (head) pada antrian dan rear menunjuk ke elemen baru yang ditambahkan dan nilai count bertambah satu .
• Jika antrian sudah penuh maka selesai.

b. Operasi Dequeue

Operasi pop pada antrian disebut juga dequeue. Operasi ini digunakan untuk menghapus elemen pada antrian. Elemen yang akan dihapus adalah elemen yang terletak paling depan pada antrian. Algoritma operasi pop pada queue adalah sebagai berikut:

• Melakukan pengecekan kondisi antrian, ada isi data atau tidak.
• Jika terdapat data pada antrian, maka lakukan penghapusan data dengan cara memindahkan head (elemen terdepan antrian) ke elemen setelahnya atau membuat penunjuk front menunjuk ke elemen setelah elemen terdepan pada queue.
• Kemudian menghapus elemen terdepan antrian dan nilai count antrian berkurang satu.
• Jika tidak terdapat data pada antrian maka selesai.

5. Perbedaan stack dan queue

• Stack merupakan tumpukan sedangkan queue merupakan antrian.
• Stack bersifat LIFO (Last in first out) yang artinya data yang terakhir masuk adalah data yang pertama keluar sedangkan queue bersifat FIFO ( First in first out) yaitu data yang pertama masuk akan pertama kali keluar.
• Perbedaan antara stack dan queue terdapat pada aturan penambahan dan penghapusan elemen. Pada stack, operasi penambahan dan penghapusan elemen dilakukan di satu ujung. Elemen yang terakhir kali dimasukkan akan berada paling dekat dengan ujung atau dianggap paling atas sehingga pada operasi penghapusan, elemen teratas akan dihapus paling awal (LIFO). Pada queue, operasi tersebut dilakukan di tempat yang berbeda. Penambahan elemen selalu dilakukan melalui salah satu ujung menempati posisi di belakang elemen-elemen yang sudah masuk sebelumnya atau menjadi elemen paling belakang. Sedangkan penghapusan elemen dilakukan di ujung yang berbeda, yaitu pada posisi elemen yang masuk paling awal atau elemen terdepan (FIFO).

6. Notasi Aritmatika Prefix, infix, dan postfix

Dalam struktur data terdapat 3 notasi operasi yang dilakukan suatu operasi aritmatika, yaitu prefix, infix dan postfix. Notasi terbentuk dari operand dan operator. Operand adalah data atau nilai yang membantu dalam proses, sedangkan operator adalah fungsi yang digunakan dalam proses.

Contoh :

A + B * C

2 + 3 * 5

Keterangan : A, B, C, 2, 3, 5 adalah operand.

+, * adalah operator

Level dari operator, seperti:

1. “^” (pangkat)

a. “*” (kali) atau “/” (bagi)

b. “+” (tambah) atau “-” (kurang)

Apabila terdapat operand di dalam sebuah kurung (“(.....)”), maka pengerjaannya akan dimulai dari operand yang berada di dalam kurung tersebut.

Contoh: (A-B)*(C+D)
Prioritas pengerjaannya adalah sebagai berikut:

a. Dalam kurung pertama : (A-B)

b. Dalam kurung kedua : (C+D)

c. Perkalian hasil pengurangan dengan hasil penjumlahan

Aturan notasi prefix, infix, dan postfix :

a. Notasi prefix : Operator-Operand-Operand, +AB (Polish Notation – PN)

b. Notasi infix : Operand-Operator-Operand, A+B

c. Notasi postfix : Operand-Operand-Operator, AB+ (Reveser Polish Notation – RPN)

Notasi aritmatika prefix,infix dan postfix:

a. Notasi Prefix

Notasi Prefix adalah notasi yang operatornya ditempatkan sebelum dua operand.

Contoh : A+B*C (Infix)

Maka, notasi prefixnya adalah +A*BC

b. Notasi Infix

Notasi infix adalah notasi yang operatornya ditempatkan di antara dua operand. Notasi ini telah dikenal secara umum oleh manusia dan selalu digunakan dalam perhitungan aritmatika.

Contoh : A + B * C

(A + B) * C

A – (B + C) * D ^ E

c. Notasi Postfix

Notasi postfix adalah notasi yang operatornya ditempatkan setelah dua operand.

Contoh : A+B*C (Infix)

Maka, notasi postfixnya adalah ABC*+

algoritma & struktur data

Share This :