STRUKTUR DATA - Stack and Queue Representation

STACK


Stack adalah suatu tumpukan atau kumpulan data yang menggunakan konsep LIFO (last in first out). Dimana elemen terakhir yang di letakan adalah elemen pertama yang akan diambil (push depan pop depan). Konsepnya sama seperti tumpukan benda yang biasa kita temukan dalam kehidupan sehari-hari. Misalnya tumpukan buku, pada tumpukan tersebut pastinya buku pertama yang akan kita ambil adalah buku yang paling atas atau buku yang terakhir diletakan pada tumpukan tersebut. 

Array Representation

Dalam stack yang menggunakan array, dikenal 2 variabel, yaitu variabel TOP dan MAX. Variabel Top merupakan variabel yang digunakan untuk menyimpan alamat / index elemen yang paling atas (yang paling terakhir diletakan) dalam sebuah stack. Sedangkan variabel Max merupakan variabel yang menunjukan jumlah elemen pada stack. Jika Top == NULL, maka stack tersebut dinyatakan kosong atau belum memiliki elemen. Jika Top=Max-1, maka stack dinyatakan full. Mengapa Max-1? karena dalam array menggunakan index yang dimulai dari 0, sehingga jika ada 10 data, index terbesarnya adalah 9. berikut gambarannya :


Linked List Representation

Membuat stack menggunakan array memang lebih mudah, akan tetapi dalam penggunaannya kita mesti mendeklarasikan terlebih dahulu jumlah alamat yang akan dipesan, misalnya : data[10]; , maka memory yang dipesan hanya 10 sehingga membuat jumlah data terbatasi karena memory yang sudah dipesan tidak dapat di hapus ataupun ditambah. Sehingga membuatnya tidak dinamis. Oleh karena itu, untuk mengatasinya kita dapat menggunakan linked list, karena dalam linked list, jumlah memory yang dipesan dapat kita kurangi atau tambah kapanpun jika kita membutuhkannya.

Elemen pada linked list di kenal sebagai node. Setiap node memiliki 2 bagian, satu untuk menyimpan data, satunya lagi untuk menyimpan alamat dari node yang selanjutnya.  Pada Stack yang menggunakan linked list terdapat pointer START yang digunakan sebagai TOP. Dan proses penghapusan dan penambahan node dilakukan pada bagian Top.

berikut gambarannya :


Stack Operation

  • Push()   :   Menambah item pada bagian atas stack 
  • Pop()    :   Menghapus item pada bagian atas stack
  • Top()    :   Mengembalikan item teratas pada stack. Top dikenal juga sebagai Peek.
Codingan operasi stack diatas sama seperti codingan yang saya contohkan di postingan Linked List . Bedanya hanya saat push() dan pop() nya saja, stack hanya menggunakan push depan dan pop depan, karena stack menggunakan konsep LIFO.

Prefix, Infix, and Postfix

Prefix, infix dan postfix merupakan suatu cara penulisan atau notasi suatu operasi perhitungan / matematika berdasarkan operan dan operatornya. 
  • Operan adalah bilangan/angka yang kita akan hitung
  • Operator adalah lambang perhitungan yang kita gunakan untuk mengoperasikan operan, misalnya +, -, /, *, ^, dsb.
  • Prefix   : Operator diletakan sebelum operan. 
  • Infix     : Operator diletakan diantara operan.
  • Posfix  : Operator diletakan setelah operan.

berikut contohnya :


Mengapa Kita Menggunakan Notasi Prefix / Postfix?

Mungkin banyak orang bertanya mengapa kita memerlukan notasi prefix dan postfix, padahal sudah ada notasi infix yang secara manual lebih mudah untuk dibaca dan digunakan. Berikut manfaat menggunakan notasi prefix/postfix :
  • Prefix/Postfix tidak memerlukan bracket/tanda kurung ( ) untuk memprioritaskan presedensi operator.
  • Prefix/Postfix lebih mudah dievaluasi komputer. 

Cara menghitung notasi PREFIX

Secara Manual
  • Baca dari kanan ke kiri

 contoh :
+ 7 – x 6 5 ^ 3 2    , baca dari kiri sampai menemukan operator
+ 7 – x 6 5 ^ 3 2    , hitung 2 angka setelah operator, yaitu 3^2 = 9
+ 7 – x 6 5 9        , baca dari kiri sampai menemukan operator selanjutnya
+ 7 – x 6 5 9        , hitung 2 angka setelah operator, yaitu 6x5 = 30
+ 7 – 30 9           , baca dari kiri sampai menemukan operator selanjutnya
+ 7 – 30 9           , hitung 2 angka setelah operator, yaitu 30-9 = 21
+ 7 21               , baca dari kiri sampai menemukan operator selanjutnya
+ 7 21               , hitung 2 angka setelah operator, yaitu 3^2 = 9
28                   , karena sudah tidak ada operator, maka selesai

Menggunakan Stack
  • Baca elemen dari kanan ke kiri satu persatu
  • Jika elemen tersebut operan, letakan pada stack
  • Jika elemen tersebut operator, pop() dua elemen terakhir misal B lalu A, kemudian push(A-B) pada stack


Cara menghitung notasi POSTFIX

Secara Manual :
  • Baca dari kiri ke kanan

 contoh :
7 6 5 x 3 2 ^ – + , baca setiap elemen dari kiri sampai menemukan operator
7 6 5 x 3 2 ^ – + , hitung 2 angka sebelum operator, yaitu 6 x 5 =30
7 30 3 2 ^ – +    , baca kembali sampai menemukan operator selanjutnya
7 30 3 2 ^ – +    , hitung 2 angka sebelum operator, yaitu 3^2 = 9
7 30 9 – +       , baca kembali sampai menemukan operator selanjutnya
7 30 9 – +       , hitung 2 angka sebelum operator, yaitu 30-9 = 21
7 21 +           , baca kembali sampai menemukan operator selanjutnya
7 21 +           , hitung 2 angka sebelum operator, yaitu 7+21 = 28
28               , karena sudah tidak ada operator lagi, maka selesai.

Menggunakan Stack :
  • Baca elemen dari kiri ke kanan satu persatu
  • Jika elemen tersebut operan, letakan pada stack
  • Jika elemen tersebut operator, pop() dua elemen terakhir misal B lalu A, kemudian push(A-B) pada stack

Mengubah dari Infix --> Prefix

  • Cari operator yang memiliki presedensi tertinggi
  • Letakan operator sebelum operannya
  • Ulangi sampai selesai

 contoh : 
A+B–CxD^E/F , cari operator yang memiliki presedensi tertinggi, yaitu ^
A+B–CxD^E/F , letakan ^ di sebelah kiri operan-operannya, yaitu sebelum D dan E
A+B–Cx^DE/F , cari operator yang memiliki presedensi tertinggi, yaitu x
A+B–Cx^DE/F , letakan ^ di sebelah kiri operan-operannya, yaitu sebelum C dan ^DE
A+B–xC^DE/F , cari operator yang memiliki presedensi tertinggi, yaitu /
A+B–xC^DE/F , letakan ^ di sebelah kiri operan-operannya, yaitu sebelum C^DE dan F
A+B–/xC^DEF , cari operator yang memiliki presedensi tertinggi, yaitu +
A+B–/xC^DEF , letakan ^ di sebelah kiri operan-operannya, yaitu sebelum A dan B
+AB–/xC^DEF , cari operator yang memiliki presedensi tertinggi, yaitu -
+AB–/xC^DEF , letakan ^ di sebelah kiri operan-operannya, yaitu sebelum +AB dan /xC^DEF
–+AB/xC^DEF , selesai

Mengubah dari Infix --> Postfix

  • Cari operator yang memiliki presedensi tertinggi
  • Letakan operator dibelakang operannya
  • Ulangi sampai selesai

 contoh : 
A+B–CxD^E/F , cari operator yang memiliki presedensi tertinggi, yaitu ^
A+B–CxD^E/F , letakan ^ di sebelah kanan operan-operannya, yaitu setelah D dan E
A+B–CxDE^/F , cari operator yang memiliki presedensi tertinggi ke-2, yaitu x
A+B–CxDE^/F , letakan x di sebelah kanan operan-operannya, yaitu setelah C dan DE^
A+B–CDE^x/F , cari operator yang memiliki presedensi tertinggi ke-3, yaitu /
A+B–CDE^x/F , letakan / di sebelah kanan operan-operannya, yaitu setelah CDE^x dan F
A+B–CDE^xF/ , cari operator yang memiliki presedensi tertinggi ke-4, yaitu +
A+B–CDE^xF/ , letakan + di sebelah kanan operan-operannya, yaitu setelah A dan B
AB+–CDE^xF/ , cari operator yang memiliki presedensi tertinggi ke-5, yaitu -
AB+–CDE^xF/ , letakan - di sebelah kanan operan-operannya, yaitu setelah AB+ dan CDE^xF/
AB+CDE^xF/– , selesai

QUEUE

Queue adalah suatu kumpulan data yang menggunakan konsep FIFO (first in first out) / LILO (last in last out) sehingga mirip dengan konsep antrian dalam kehidupan sehari-hari, dimana orang pertama yang mengantri adalah orang pertama juga yang akan keluar dari antrian tersebut sehingga queue menggunakan push belakang pop depan.

Array Representation

Sama halnya seperti stack, queue pada array juga memiliki 2 variabel, yaitu variabel FRONT dan REAR yang menunjuk ke posisi dimana insertion dan deletion dapat dilakukan masing-masing. Front adalah variabel yang menunjuk posisi pertama dalam antrian, dan rear adalah variabel yang menunjuk posisi terakhir dalam antrian. 

 berikut gambarannya :


Linked List Representation

Linked list pada queue juga sama seperti pada stack, elemennya pun disebut node dan memiliki bagian yang sama. Hanya saja pointer START pada queue digunakan sebagai FRONT. Proses penambahan node dilakukan pada bagian Rear dan penghapusan node dilakukan pada bagian Front. Jika FRONT = REAR = NULL, maka Queue dinyatakan kosong, atau belum memiliki node.

berikut gambarannya :


Queue Operations

  • Push() :  Menambah item pada bagian belakang/rear suatu queue.
  • Pop()  : Menghapus item pada bagian depan/front suatu queue.
  • Front(): Mengembalikan item yang paling depan dalam suatu queue. Front dikenal juga sebagai Peek.
Codingan operasi queue diatas sama seperti codingan yang saya contohkan di postingan Linked List . Bedanya hanya saat push() dan pop() nya saja, queue hanya menggunakan push belakang/tail dan pop depan, karena queue menggunakan konsep FIFO.


POPULAR

STRUKTUR DATA - Linked List

Linked List Linked List atau dikenal juga dengan sebutan senarai berantai adalah struktur data yang terdiri dari urutan record data dimana setiap record memiliki field yang menyimpan alamat/referensi dari record selanjutnya (dalam urutan). Elemen data yang dihubungkan dengan link pada Linked List disebut Node. Biasanya didalam suatu linked list, terdapat istilah head dan tail.  Head adalah elemen yang berada pada posisi pertama dalam suatu linked list Tail adalah elemen yang berada pada posisi terakhir dalam suatu linked list Ada beberapa macam Linked List, yaitu : Single Linked List Double Linked List Circular Linked List Multiple Linked List Single Linked List Single Linked List merupakan suatu linked list yang hanya memiliki satu variabel pointer saja. Dimana pointer tersebut menunjuk ke node selanjutnya. Biasanya field pada tail menunjuk ke NULL. contoh : contoh codingannya : struct Mahasiswa{       char nama[25];       int usia;       struct
Read more

STRUKTUR DATA - Balanced Binary Search Tree (AVL and RBT) and 2-3 Tree

Balanced Binary Search Tree Dalam Binary Search Tree, tinggi maksimal suatu tree adalah N-1, dimana N  adalah jumlah node. Dalam melakukan suatu operasi, misalnya insertion, deletion, dan seaching, kecepatan waktu merupakan hal yang cukup penting untuk diperhatikan. Setiap operasi pasti di harapkan dapat berjalan dengan cepat, sehingga semakin cepat suatu operasi maka semakin baik. Cepat atau tidaknya suatu operasi, bergantung pada ketinggian tree tersebut, semakin rendah tingginya, maka semakin cepat. Dengan Balanced Binary Search Tree, kita dapat membuat suatu tree dengan tinggi minimum. untuk menetapkan tingginya, kita dapat menggunakan rumus berikut: O(log n) 2 contoh tree yang termasuk ke dalam balanced binary search tree, yaitu : - AVL Tree - Red Black Tree (RBT) AVL Tree AVL adalah balanced binary search tree dimana ia memiliki perbedaan jumlah node pada subtree kiri dan subtree kanannya maksimal 1 (atau dapat dikatakan antara tingginya sama atau selisi
Read more

STRUKTUR DATA - B Tree and Heap & Deap

B-Tree Pada B-Tree dikenal istilah order. Order menentukan jumlah maksimum/minimum anak yang dimiliki oleh setiap node, sehingga order merupakan hal yang cukup penting dalam B-Tree. 2-3 Tree pada postingan sebelumnya yaitu Balanced Binary Search Tree (AVL and RBT) and 2-3 Tree  merupakan salah satu B-Tree berorder 3. Itu sebabnya setiap nodenya memiliki batasan anak, dengan minimal 2 anak dan maksimal 3 anak. Aturan pada B-Tree : m = order Setiap node (kecuali leaf) memiliki anak paling banyak sejumlah m anak Setiap node (kecuali root) memiliki anak paling sedikit m/2 anak Root memiliki anak minimal 2, selama root bukan leaf Jika node non leaf memiliki k anak, maka jumlah data yang tersimpan dalam node k-1 Data yang tersimpan pada node harus terurut secara inorder Semua leaf berada pada level yang sama, level terbawah Berikut contoh B-Tree : B-Tree order 4 B-Tree order 6 Operasi : Searching Searching pada B-Tree mirip seperti 2-3 Tree. Pertama-ta
Read more