Session 5 (Stack , Queue dan Implementasi)

Stack adalah tumpukan dari suatu data.

Dalam kehidupan stack bisa dinyatakan seperti piring yg memiliki konsep

LIFO (Last in First Out) : data yang terakir masuk akan pertama kali keluar

FILO (First in Last Out) : data yang pertama kali masuk akan keluar terakir

Dalam stack ada 2 variabel ;

TOP : untuk menunjukan data teratas pada stack

MAX : untuk menujukan jumlah data pada stack

Jika Top = NULL maka stack kosong

jika Top = Max - 1 berarti stack penuh.

Pada stack, jika menambah data maka TOP akan naik dan jika menghapus data  TOP akan turun.

Operasi – operasi pada Stack (Tumpukan)

Operasi yang sering diterapkan pada struktur data Stack (Tumpukan) adalah Push dan Pop. Operasi – operasi yang dapat diterapkan adalah sebagai berikut :

1. Push : digunakan untuk menembah item pada Stack pada Tumpukan paling atas.

2. Pop : digunakan untuk mengambil item pada Stack pada Tumpukan paling atas.

3. Clear : digunakan untuk mengosongkan Stack.

4. Create Stack : membuat Tumpukan baru S, dengan jumlah elemen kosong.

5. MakeNull : mengosongkan Tumpukan S, jika ada elemen maka semua elemen dihapus.

6. IsEmpty : fungsi yang digunakan untuk mengecek apakah Stack sudah kosong.

7. Isfull : fungsi yang digunakan untuk mengecek apakah Stack sudah penuh.

Macam – macam Stack

1. Stack dengan Array

Sesuai dengan sifat stack, pengambilan atau penghapusan elemen dalam stack harus dimulai dari elemen teratas.

2. Double Stack dengan Array

Metode ini adalah teknik khusus yang dikembangkan untuk menghemat pemakaian memori dalam pembuatan dua stack dengan array. Intinya adalah penggunaan hanya sebuah array untuk menampung dua stack.

QUEUE (ANTRIAN)

A. Definisi Queue (Antrian)

          Queue merupakan suatu struktur data linear. Konsepnya hampir sama dengan Stack, perbedaannya adalah operasi penambahan dan penghapusan pada ujung yang bebeda. Penghapusan dilakukan pada bagian depan (front) dan penambahan berlaku pada bagian belakang (Rear). Elemen-elemen di dalam antrian dapat bertipe integer, real, record dalam bentuk sederhana atau terstruktur.

          Tumpukan disebut juga “Waiting Line” yaitu penambahan elemen baru dilakukan pada bagian belakang dan penghapusan elemen dilakukan pada bagian depan. Sistem pada pengaksesan pada Queue menggunakan sistem FIFO (First In First Out), artinya elemen yang pertama masuk itu yang akan pertama dikeluarkan dari Queue. Queue jika diartikan secara harfiah, queue berarti antrian. Queue merupakan salah satu contoh aplikasi dari pembuatan double linked list yang cukup sering kita temui dalam kehidupan sehari-hari, misalnya saat anda mengantri diloket untuk membeli tiket.

         Istilah yang cukup sering dipakai apabila seseorang masuk dalam sebuah antrian adalah enqueue. Sedang istilah yang sering dipakai bila seseorang keluar dari antrian adalah dequeue.

B. Operasi-operasi pada Queue

1. Create Queue (Q) : membuat antrian baru Q, dengan jumlah elemen kosong.

2. Make NullQ (Q) : mengosongkan antrian Q, jika ada elemen maka semua elemen dihapus.

3. EnQueue : berfungsi memasukkan data kedalam antrian.

4. DeqQueue : berfungsi mengeluarkan data terdepan dari antrian.

5. Clear : Menghapus seluruh Antrian

6. IsEmpty : memeriksa apakah antrian kosong

7. IsFull : memeriksa apakah antrian penuh.

Depth First Search (DFS) dan Breadth First Search (BFS)

DFS : pencarian solusi dengan menelusuri lebih dahulu akar - akarnya,jika tidak ketemu pencarian akan dipindah ke node yang lain pada level yang sama

Keuntungan menggunakan metode DFS:

- Membutuhkan memori yang relative kecil, karena hanya node-node pada lintasan yang aktif saja yang disimpan.

- Secara kebetulan, metode depth-first search akan menemukan solusi tanpa harus menguji lebih banyak lagi.

Kekurangan dari metode DFS ini yaitu:

- Memungkinkan tidak ditemukannya tujuan yang diharapakan.

- Hanya akan menemukan 1 solusi pada setiap pencarian.

BFS : pencarian solusi dimana semua node pada level n akan ditelusuri terlebih dahulu.

Keuntungan yang didapat apabila menggunakan metode BFS ini yaitu:

- Tidak akan menemui jalan buntu.

- Menjamin ditemukannya solusi (jika solusinya memang ada) dan solusi yang ditemukan pasti yang paling baik.

- Jika ada satu solusi maka bread-first search akan menemukannya.

Dan kekurangan dari metode BFS ini yaitu:

- Membutuhkan memori yang cukup banyak.

- Membutuhkan waktu yang cukup lama.

Nama: Ardi Yuriansyah

Nim: 1701290816

Kelas: 02PFT

www.binus.ac.id