Stack & Queue
Stack
Stack atau tumpukan merupakan salah satu bagian dari Data Structure yang memiliki prinsip yang terakhir masuk yang duluan keluar. Stack bisa diumpamakan seperti buku yang saling bertumpukan dan ketika kita ingin mengambil sebuah buku, buku pertama yang kita keluarkan adalah buku yang berada di paling atas dimana buku tersebut terakir masuk ke dalam tumpukan. Stack bisa ditambahkan atau dihilangkan hanya dengan melalui satu jalan yaitu sisi paling atas tumpukan. Atau dengan kata lain data dari stack hanya bisa disimpan dengan cara Last In First Out (LIFO). Stack bisa menggunakan array ataupun linked list.
Stack dalam array
Infix, Postfix, dan Prefix Notation
front dan rear adalah tempat dimana operasi insertion dan deletion bisa berlangsung. Front untuk deletion. Rear untuk insertion. 0 di dalam gambar merupakan front sedangkan 4 di gambar merupakan rear. Sama seperti stack bahwa penggunaan array relatif lebih mudah dibandingkan linked list dalam penerapan queue.
 |
| https://jonlennartaasenden.files.wordpress.com/2019/05/use-case-graphic_full-stack-provisioning.png |
Stack atau tumpukan merupakan salah satu bagian dari Data Structure yang memiliki prinsip yang terakhir masuk yang duluan keluar. Stack bisa diumpamakan seperti buku yang saling bertumpukan dan ketika kita ingin mengambil sebuah buku, buku pertama yang kita keluarkan adalah buku yang berada di paling atas dimana buku tersebut terakir masuk ke dalam tumpukan. Stack bisa ditambahkan atau dihilangkan hanya dengan melalui satu jalan yaitu sisi paling atas tumpukan. Atau dengan kata lain data dari stack hanya bisa disimpan dengan cara Last In First Out (LIFO). Stack bisa menggunakan array ataupun linked list.
Stack dalam array
 |
| https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhUBAKfxTE_3DMm65cfZ4UjdICcsYOhShV4qnE4BqU_9dB-NmKhGv1WT_pJsD3TFnmKWDJvkHDaC143BI-Ei3ERML0LMqlj2j-yY2Px2IUsyEEcJ0wI7lwVQq0V_sPqZqjy6xrZ-6XNrQc/?imgmax=800 |
Stack menggunakan Array relatif lebih mudah dibandingkan membuat stack dengan Linked list. Untuk stack dengan pengunaan array yang pertama harus di declare terlebih dahulu ukurannya. Stack memiliki 2 buah variable yaitu TOP dan MAX. TOP berfungsi untuk menyimpan alamat dari elemen yang berada di tumpukan paling atas. Sedangkan MAX berfungsi untuk menyimpan jumlah maksimal elemen yang dapat disimpan oleh stack.. Jika TOP memiliki value NULL maka stack kosong. Jika TOP = MAX - 1 hal ini menandakan bahwa stack full.
Stack dalam Linked List
 |
| https://blogger.googleusercontent.com/img/proxy/AVvXsEgME50MC_BcWVT5SuSKpmlrBR6KuS8vp3qB8ZK7zn9HVPAFQvoSmdVns9AG7jZ9a_IzkqxGVP25Xc8-cw0ocVbhhJ3U7r-WODOr0J1x2KH4WY3FsAVRdIzUWMsNDW-wxeF1BjCbvomPhKeO0z4F3zblI6C79x0r8PxSfC2LkT2-idP_ZdtBlLjJEPhdVrMBJilKSHXGlY62XDRaficL18cp3bzj= |
Stack dengan menggunakan Linked List memang relatif lebih susah daripada array, namun tetap memiliki kelebihan jika dibandingkan dengan menggunakan array yaitu tidak mendeclare di awal ukurannya. Dalam Linked stack, setiap node punya 2 field yang satu untuk menyimpan data dan yang lainnya berfungsi untuk menyimpan alamat dari node selanjutnya. TOP(peek) dari linked list stack adalah pointer headnya. Semua operasi yang dilakukan seperti deletion dan insertions dilakukan dari TOP. jika TOP bernilai NULL maka bisa disimpulkan bahwa stack kosong.
Bentuk-Bentuk Operasi Stack
Terdapat 3 bentuk operasi dalam stack yaitu:
- push
- pop
- top
push(x) adalah operasi untuk menambahkan data ke TOP(peek) stack. pop adalah operasi stack untuk menghilangkan data atau mendelete data dari TOP(peek) stack. Dan top untuk memunculkan data teratas dari stack.
 |
| https://i1.faceprep.in/Companies-1/stack%20data%20structure%20in%20c.png |
Infix: Operator berada di antara operand. *operator: +-*/^
Postfix: Operator berada setelah operand.
Prefix: Operator berada di sebelum operand.
contoh:
infix: ((1+3)/(100*5)^30)
Postfix: 13+1005*30^/
Prefix: /+13^*100530
Evaluation:
infix: mencari prioritas operator tertinggi dahulu.
Postfix: scan dari kiri ke kanan.
Prefix: scan dari kanan ke kiri.
Depth First Search (DFS)
DFS adalah suatu algoritma dimana berguna untuk mencari jalan di dalam tree atau graph. Jika merupakan pohon dimulai dari rootnya. Langkah pertama yang dilakukan adalah mengeksplor bagian luar. Hanya edge yang menuju vertex yang belum dilewati yang dieksplor. Ketika semua edge sudah di eksplor, pencarian akan balik lagi hingga menjangkau tetangga yang belum dilewati.
 |
| https://upload.wikimedia.org/wikipedia/commons/thumb/1/1f/Depth-first-tree.svg/450px-Depth-first-tree.svg.png |
QUEUE
Merupakan bagian dari Struktur Data yang menyimpan data secara teratur. Contoh Queue adalah ketika kita memutar playlist lagu kita di media player, musik yang pertama kita dengar adalah musik yang pertama kita masukan ke daftar lagu kita dan yang lainya menunggu musik pertama selesai. Contoh lainnya adalah ketika kita mengantri di sebuah foodcourt dimana kita harus menunggu orang yang pertama datang yang dilayani terlebih dahulu. Sama seperti stack, queue bisa menggunakan array dan linked list. Ada beberapa operasi yang bisa dilakukan pada queue, untuk menambahkan elemen dari belakang dan untuk menghapus elemen dilakukan dari depan. Data disimpan dengan metode First In First Out (FIFO) . Siapa yang pertama masuk dia yang terlebih dahulu keluar.
Menggunakan array
 |
| https://static.javatpoint.com/ds/images/array-representation-of-queue.png |
Menggunakan Linked List
 |
| https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjS3p6uTo4pES1laqMQ6w4bwEEwbM1S7HV2BGIhetyci7jgKiMVYlNdwp7KjiBICqN413dNjQS9qOKa0dFKFOIaE7zEoYiY-uuptEZNPjXoNovIpJ5KLlIdISGCBW1rQ-NbhMLRhSgkFZpe/h90/linked-list-implementation-of-queue.png |
Keuntungan dalam menggunakan linked list dibanding array adalah kita tidak perlu mendeclare di awal ukurannya. Dalam Linked queue, setiap node punya 2 field yang satu untuk menyimpan data dan yang lainnya berfungsi untuk menyimpan alamat dari node selanjutnya. Insertion selalu dilakukan di rear dan deletion dilakukan di front. jika front dan rear bernilai NULL maka queue tersebut kosong.
Operasi queue
- push
- pop
- front
push(x) untuk menambahkan elemen x ke-rear. pop() adalah operasi untuk menghilankan elemen dari front. front untuk memunculkan item paling depan dari queue.
Circular Queue
untuk mengatasi masalah ketika queue sudah penuh dan mencegah data baru berada di luar range maka bisa diatasi dengan circular queue. Ketika index kiri sudah mencapai maksimal index di set kembali ke 0. Demikian juga dengan index kanan.
Deques
Atau sering juga disebut head-tail linked list Adalah suatu list dimana kita bisa melakukan deletion dan insertion dari head(front) atau tail(rear). Ada 2 jenis Deques Input Restriction deque dan Output Restriction deque. Input Restriction memungkinkan deletion di kedua sisi(head & tail) namun insertion hanya bisa dilakukan di salah satu sisi. Pada Output Restriction deque memungkinkan insertion di kedua sisi (head&tail) namun deletion hanya bisa dilakukan di salah satu sisi.
Priority Queue
Merupakan tipe data abstrak yang mementingkan priority dalam penempatannya. Elemen atau data yang memiliki priority lebih tinggi akan dikerjakan terlebih dahulu dari elemen yang memiliki priority lebih kecil. Jika terdapat dua elemen yang memiliki tingkat priority yang sama makan akan diberlakukan prinsip First In First Served (FIFS). Deletion dengan menghapus node pertama dan data dari node tersebut diproses terlebih dahulu.
Breadth First Search (BFS)
Jika Depth First Search menggunakan stack, Breadth First Search menggunakan queue. Pencarian yang mengunjungi vertex secara dari kiri ke kanan yaitu mengunjungi suatu vertex setelah itu mengeskplor semua vertex- vertex tetangga dengan vertex tersebut terlebih dahulu. Setelah itu , mengungjungi vertex yang belum dikunjungi dan tetangga vertex yang tadi sudah dikunjungi
Operasi queue
- push
- pop
- front
push(x) untuk menambahkan elemen x ke-rear. pop() adalah operasi untuk menghilankan elemen dari front. front untuk memunculkan item paling depan dari queue.
Circular Queue
untuk mengatasi masalah ketika queue sudah penuh dan mencegah data baru berada di luar range maka bisa diatasi dengan circular queue. Ketika index kiri sudah mencapai maksimal index di set kembali ke 0. Demikian juga dengan index kanan.
 |
| https://www.tutorialride.com/images/data-structures/circular-queue2.jpeg |
Atau sering juga disebut head-tail linked list Adalah suatu list dimana kita bisa melakukan deletion dan insertion dari head(front) atau tail(rear). Ada 2 jenis Deques Input Restriction deque dan Output Restriction deque. Input Restriction memungkinkan deletion di kedua sisi(head & tail) namun insertion hanya bisa dilakukan di salah satu sisi. Pada Output Restriction deque memungkinkan insertion di kedua sisi (head&tail) namun deletion hanya bisa dilakukan di salah satu sisi.
Priority Queue
Merupakan tipe data abstrak yang mementingkan priority dalam penempatannya. Elemen atau data yang memiliki priority lebih tinggi akan dikerjakan terlebih dahulu dari elemen yang memiliki priority lebih kecil. Jika terdapat dua elemen yang memiliki tingkat priority yang sama makan akan diberlakukan prinsip First In First Served (FIFS). Deletion dengan menghapus node pertama dan data dari node tersebut diproses terlebih dahulu.
Breadth First Search (BFS)
Jika Depth First Search menggunakan stack, Breadth First Search menggunakan queue. Pencarian yang mengunjungi vertex secara dari kiri ke kanan yaitu mengunjungi suatu vertex setelah itu mengeskplor semua vertex- vertex tetangga dengan vertex tersebut terlebih dahulu. Setelah itu , mengungjungi vertex yang belum dikunjungi dan tetangga vertex yang tadi sudah dikunjungi
 |
| https://upload.wikimedia.org/wikipedia/commons/thumb/3/33/Breadth-first-tree.svg/450px-Breadth-first-tree.svg.png |
BFS VS DFS
 |
| https://vivadifferences.com/wp-content/uploads/2019/10/DFS-VS-BFS.png |
Komentar
Posting Komentar