Stack and Queue

A. Stack

     Stack atau tumpukan adalah sebuah data struktur penting di mana setiap elemennya memiliki urutan tertentu. Dapat juga diartikan sebagai kumpulan data yang seolah terlihat membentuk suatu tumpukan atau seperti ada data yang diletakkan di atas data lainnya.

     Stack dapat dianalogikan seperti ketika kita memiliki setumpuk piring di mana setiap piring diletakkan di atas piring lainnya atau ditumpuk ke atas. Ketika ingin mengeluarkan sebuah piring dari tumpukan tersebut, yang pertama kali diambil adalah piring yang paling atas. Oleh karena itu, kita hanya bisa menambahkan dan mengurangi piring pada satu posisi, yaitu posisi yang paling atas.

     Stack merupakan sebuah data struktur linear yang dapat diimplementasikan menggunakan array atau linked list. Elemen-elemen yang ditumpuk hanya bisa ditambah atau dikurangi dari ujungnya, yaitu yang paling atas (top). Maka, kaidah utama dalam konsep stack adalah LIFO yang merupakan singkatan dari Last In First Out. Artinya, data yang terakhir kali dimasukkan atau disimpan adalah data yang pertama kali akan diakses atau dikeluarkan.


                                       

     Operasi-operasi dalam stack :
1. Push : memasukkan atau menyimpan sebuah data ke dalam stack.
2. Pop : mengeluarkan atau menghapus data terakhir (yang berada pada posisi paling atas) dari stack.





B. Infix, Postfix, and Prefix Notation

     Ada tiga notasi operasi yang dilakukan untuk suatu operasi aritmatika, yaitu Infix, Postfix, dan Prefix. Notasi-notasi tersebut terbentuk dari operand dan operator. Operand adalah data atau nilai, sedangkan operator adalah fungsi yang digunakan dalam proses.

     Pada notasi Infix, operator terletak di antara operand. Contoh :
     4 + 6 * (5 - 2) / 3 

     Pada notasi Prefix, operator berada di depan operand. Contoh :
     + 4 / * 6 - 5 2 3 

     Pada notasi Postfix, operator berada di belakang operand. Contoh :
     4 6 5 2 - * 3 / + 

     Mengapa kita membutuhkan notasi Prefix atau Postfix? Karena notasi tersebut tidak membutuhkan tanda kurung () untuk memprioritaskan operator-operator (operator precedence). Notasi Prefix dan Postfix lebih mudah untuk diproses oleh komputer.

     Latihan Soal :
     Infix : ( (1 + 3) / (100 * 5) ^ 30 )
     Prefix : / + 1 3 ^ * 100 5 30
     Postfix : 1 3 + 100 5 * 30 ^ /





C. Queue

     Queue atau antrian merupakan struktur data linear di mana penambahan dilakukan di satu ujung, dan pengurangan dilakukan di ujung lainnya. Dapat dianalogikan seperti orang-orang yang bergerak di eskalator. Orang yang pertama menaiki eskalator akan lebih dulu keluar dari eskalator.

     Kaidah utama dalam konsep queue adalah First In First Out (FIFO). Artinya, data yang pertama kali dimasukkan atau disimpan adalah data yang pertama kali akan diakses atau dikeluarkan.


                             


     Operasi-operasi dalam queue :
1. Enqueue : memasukkan sebuah data ke dalam queue.
2. Dequeue : menghapuskan sebuah data yang paling awal masuk ke dalam queue.





D. Perbedaan Stack dan Queue

1. Stack merupakan tumpukan, sedangkan queue merupakan antrian.

2. Stack bersifat LIFO, sedangkan queue bersifat FIFO.

3. Penambahan dan penghapusan elemen pada stack dilakukan di satu ujung, sedangkan pada queue dilakukan pada ujung yang berbeda.




Comments

Post a Comment

Popular posts from this blog

AVL Tree dan B-Tree

Image
A. AVL Tree AVL adalah balanced binary search tree yang memiliki perbedaan jumlah node pada subtree kiri dan subtree kanannya maksimal satu.                                              Untuk menentukan Height dan Balance Factor, gunakan cara berikut : Height : 1. Jika node (root) tidak memiliki subtree heightnya = 0. 2. Jika node adalah leaf, height = 1. 3. Jika internal node, maka height = height tertinggi dari anak + 1. Balance Factor : 1. Selisih height antara anak kiri dan kanan. Jika tidak memiliki anak dianggap 0. Insertion Insert suatu node pada AVL Tree sama dengan insert node pada Binary Search Tree. Node baru diposisikan sebagai leaf. Setelah memasukkan node baru, maka harus dilakukan penyeimbangan kembali pada path dari node yang baru di-insert atau path terdalam. Namun biasanya, path terdalam adalah path dari node yang baru saja di-insert. ...
Read more

Hashing and Hash Tables, Trees & Binary Tree

A. HASHING      Hashing merupakan metode yang digunakan untuk menyimpan data dalam sebuah array agar dapat menyimpan data, mencari data, menambah data, dan menghapus data dengan cepat. Pengertian hashing adalah transformasi aritmatik sebuah string dari karakter menjadi nilai yang merepresentasikan string aslinya. Dalam hashing, yang dilakukan adalah menghitung posisi record yang dicari dalam array, bukan membandingkan record dengan isi pada array.      Hash Function atau Fungsi Hash merupakan fungsi yang mengembalikan nilai atau kunci. Hash Table atau Tabel Hash merupakan array yang digunakan. B. HASH TABLE      Hash Table merupakan sebuah struktur data, terdiri atas sebuah tabel dan fungsi. Fungsi pada Hash Table bertujuan untuk memetakan nilai kunci yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah tabel.      Kelebihan dari Hash Table adalah waktu mengakse...
Read more

Binary Search Tree

A. BINARY SEARCH TREE      Binary Search Tree adalah tree yang terurut (ordered Binary Tree) yang memiliki kelebihan bila dibanding dengan struktur data lain. Binary Search Tree juga sering disebut dengan Sorted Binary Tree yang berfungsi untuk menyimpan informasi nama atau bilangan yang disimpan di dalam memory.      Ciri-ciri Binary Search Tree : 1. Setiap node mempunyai value dan tidak ada value yang double. 2. Value yang ada di kiri tree lebih kecil dari rootnya. 3. Value yang ada di kanan tree lebih besar dari rootnya. 4. Kiri dan kanan tree bisa menjadi root lagi atau bisa mempunyai child. 5. Memiliki sifat rekursif.      Binary Search Tree memiliki tiga operasi dasar : 1. Find(x) : menemukan value x di dalam Binary Search Tree (Search) 2. Insert(x) : memasukkan value baru x ke Binary Search Tree (Push) 3. Remove(x) : menghapus key x dari Binary Search Tree (Delete) B....
Read more