Langsung ke konten utama

Rangkuman Week 3 - Stack and Queue


Stack


Stack biasa disebut sebagai LIFO (Last In First Out), jadi data yang terakhir masuk akan di pop/ keluar duluan. Sebagai contoh seperti saat kita mencuci piring dan terdapat tumpukan piring, maka kita akan mengambilnya dari yang paling atas dahulu secara berurutan. Kurang lebih cara kerja stack seperti itu.
Dalam stack umumnya terdapat 3 proses operasi yang dilakukan :
a. push (x) : menumpuk item x diatas stack.
b. pop( ) : menghapus / mengambil data paling atas.
c. top ( ) : melihat item / value data paling atas pada stack.
Sumber : wikipedia

 Queue


Queue biasa disebut sebagai FIFO (First In First Out), jadi data yang masuk pertama akan di pop/ keluarkan dahulu. Sebagai contoh seperti saat kita mengantri, tentu saja orang paling depan akan dilayani / dapat menggunakan fasilitas dahulu. Kurang lebih ara kerja Queue seperti itu.
Dalam queue umumnya terdapat 3 proses operasi yang dilakukan :
a. push(x) : menambah antrian data pada queue.
b. pop( ) : menghapus / mengambil data paling depan.
C. first( ) : melihat data paling depan

Queue memiliki kekurangan, yaitu jika head telah mencapai batas array (head sudah sama dengan tail di array terakhir) karena head akan terus maju mendekati tail saat dilakukan proses pop( ). Maka dari itu, terdapat Circular Queue dimana kita dapat menukar index L dan R dengan men-set R menjadi 0 dan sama juga L.



Terdapat pula jenis queue berupa Deques (Double Ended Queue) dimana data dapat di push ke kanan atau kekiri.
- Input restricted deque : push dibatasi (1 tempat)
- Output restricted deque : pop dibatasi (1 tempat)


Infix, Prefix, dan Postfix notation.


Operasi Infix : opd opr opd, ct : 4 * 10
Operasi Prefix : opr opd opd, ct : * 4 10
Operasi Postfix : opd opd opr, ct : 4 10 *
Ketiga operasi ini digunakan pada masa lalu karena computer dimasa lalu tidak dapat menghitung / mendeteksi tanda kurung ( ), maka infix harus diubah ke prefix atau postfix lalu dilakukan pengecekan satu persatu. Hal ini dilakukan untuk mempercepat kerja computer dari O^n2 menjadi O^n saja.

Contoh :
Infix = ( 1 + 3 ) / ( 100 * 5) ^ 30
Dalam mengubah infix menjadi prefix ataupun postfix harus dilakukan secara urut menurut tingkatan / hirarki yang paling tinggi.

Prefix :
( 1 + 3 ) / ( 100 * 5) ^ 30
( 1 + 3 ) dan ( 100 * 5 ) memiliki tingkat yang sama maka kerjakan dari yang kiri dahulu :
ó  + 1 3 / ( 100 * 5 ) ^ 30
ó  + 1 3 / ( * 5 100 ) ^ 30
ó ( + 1 3 ) / ^ * 5 100 30
ó / + 1 3 ^ * 5 100 30
hasil ubah ini akan dijadikan string dan dilakukan pengecekan dari kanan.

Postfix :
( 1 + 3 ) / ( 100 * 5) ^ 30
ó 1 3 + / ( 100 5 * ) ^ 30
ó 1 3 + / 100 5 * 30 ^
ó 1 3 + 100 5 * 30 ^ /
hasil ubah ini akan dijadikan string dan dilakukan pengecekan dari kiri.

DFS dan BFS


DFS (Depth First Search) biasa digunakan dalam stack, dimana search pada struktur graf / pohon yang dilakukan berdasarkan kedalamannya.

 node yang dilewati : A -> C -> B -> E -> D









BFS (Breadth First Search) biasa digunakan dalam queue, diamana search pada struktur graf / pohon yang dilakukan secara melebar.

node yang dilewati : A-> B -> C -> D -> E

Komentar

Posting Komentar

Postingan populer dari blog ini

HEAP

HEAP      Di dalam bidang Teknik Informatika terdapat banyak sekali jenis-jenis algoritma pengurutan yang dapat digunakan untuk memecahkan masalah pengurutan. Oleh karena itu, teknik untuk memilih algoritma pengurutan yang tepat, sesuai dengan kebutuhan, dan mangkus sangat diperlukan karena masing-masing algoritma pengurutan memiliki karakteristik yang berbedabeda. Heap sort merupakan salah satu contoh algoritma pengurutan yang memiliki kompleksitas waktu asimptotik terbaik serta menerapkan teknik yang unik/khas di dalam memecahkan masalah pengurutan, yaitu dengan menggunakan heap tree.  Pengertian Heap Tree:      Secara umum pengertian dari heap adalah bagian dari memori yang terorganisasi untuk dapat melayani alokasi memori secara dinamis.      Suatu heap tree adalah Complete Binary Tree (CBT) di mana harga-harga key pada node-nodenya sedemikian rupa sehingga haga-harga key pada node-node anaknya tidak ada yang lebih besar dari harga k...
Posting Komentar
Baca selengkapnya

Hashing and Tree

HASH TABLE DAN BINARY TREE Hashing adalah teknik dalam struktur data, dimana teknik ini digunakan untuk menyimpan dan mengambil / mencari kata kunci dengan cepat dan efisien. Dalam hashing, string akan ditransformasikan menjadi sebuah kunci yang mewakili string aslinya. Hashing digunakan untuk mengindeks dan menemukan suatu value dengan kata kunci yang lebih pendek. Hashing dilakukan untuk menyimpan data, mencari data, menambah data, dan menghapus data dengan lebih efisien. Hash Table adalah sebuah struktur data yang terdiri atas table dan fungsi yang digunakan untuk menyimpan / menaruh key value yang unik untuk setiap record (baris) menjadi angka (hash). Contoh simplenya : arr[ ] value 0 algo 1 bahaha 2 cat 3 NULL 4 NULL  5 fly 6 go … 25 zebra algo terletak pada arr[0] kar...
Posting Komentar
Baca selengkapnya

AVL Tree and B-Tree

AVL Tree dan Balanced Tree / B-Tree AVL Tree AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi/ level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree muncul untuk menyeimbangkan Binary Search Tree. Dengan AVL Tree, waktu pencarian dan bentuk tree dapat dipersingkat dan disederhanakan yaitu dari yang seharusnya dari O(h) dimana h adalah height dari tree menjadi hanya O(log n). Agar Tree tetap seimbang, maka diberikan batasan sebesar -1, 0, atau 1, dimana batasan ini didapat dari selisih height child kiri dan child kanan. Ada beberapa operasi dalam AVL Tree, yaitu: 1. Insert, dalam insert dapat menyebabkan beberapa masalah miringnya / tidak seimbangnya jumlah child kiri dan child kanan, berikut beberapa masalah yang ada: a. Left-left case dan Right-right case: diselesaikan dengan single rotation yaitu dengan mengambil bagian tengah dari 3 node yang segaris/lurus dan meletakkanya di tengah sebagai parent, dengan 2 node sisanya menjadi cabangnya...
Posting Komentar
Baca selengkapnya