Showing posts with label Struktur Data. Show all posts
Showing posts with label Struktur Data. Show all posts

Stack

  • ..


Stack merupakan bagian dari struktur data yang dikategorikan ke dalam bentuk linear data, dimana operasi pemasukan maupun pengeluaran data selalu dilakukan pada salah satu sisinya. Dalam dunia komputer, penggunaan stack (tumpukan) merupakan suatu hal yang umum digunakan seperti untuk penentuan alamat memory, penempatan ruang data, dan aplikasi lain. Sebagai bagian dari struktur data, aplikasi stack juga digunakan untuk berbagai macam keperluan seperti pengujian kalimat palindrome, penguji tanda kurung (matching parentheses), dan juga berfungsi sebagai konversi dari notasi infix menjadi notasi prefix atau notasi postfix.
Tulisan ini dibuat untuk memberikan gambaran secara jelas proses simulasi konversi atas dua notasi aritmatika tersebut, berdasarkan studi literatur dari beberapa buku dan dituangkan dengan bantuan bahasa pemrograman Pascal. Adapun proses konversi ini ditujukan untuk menjelaskan bagaimana mesin kompilasi dapat merubah notasi infix yang biasa digunakan oleh berbagai kalangan menjadi notasi postfix yang dimengerti oleh mesin kompilasi sehingga suatu proses perhitungan aritmatika dapat dilaksanakan oleh komputer. Alasan pemilihan bahasa pemrograman Pascal digunakan karena fleksibilitas bahasa tersebut dalam menerangkan implementasi dan aplikasi dari struktur data dalam bentuk pemrograman.
Artikel Notasi Prefix, Infix, dan Postfix

Definisi Stack
Stack adalah suatu koleksi atau kumpulan item data yang teroganisasi dalam bentuk urutan linear, yang operasi pemasukan dan penghapusan datanya dilakukan pada salah satu sisinya.
Elemen-elemen yang berada dalam stack, memiliki prinsip dasar dalam pengoperasiannya yaitu prinsip LIFO (Last In First Out) atau elemen yang masuk paling terakhir akan memiliki prioritas untuk keluar paling pertama. 

 Gambar 1.1 - Ilustrasi sebuah stack.

Suatu stack dapat digambarkan sebagai suatu array berdimensi satu yang elemen-elemennya berkisar antara 1 sampai N elemen. Dengan demikian jika suatu stack didefinisikan dengan N elemen maka dapat dikatakan jumlah maksimum dari stack adalah N, sehingga penambahan elemen stack yang ke N+1 tidak diperkenankan atau stack tersebut dalam kondisi Overflow. Hal tersebut juga berlaku untuk stack dengan nilai minimum yaitu stack dalam kondisi 0, jika dilakukan operasi pengambilan elemen atas stack tersebut akan mengakibatkan stack tersebut dalam kondisi Underflow. Dua kondisi tersebut merupakan dasar dalam merancang suatu aplikasi pemrograman komputer.

Ciri-ciri Stack
·         Elemen teratas / puncaknya diketahui.
·         Penambahan atau pengambilan elemen stack selalu dilakukan pada elemen teratas stack.
·         LIFO (Last In First Out).

Pemanfaatan Stack
·         Penghitungan ekspresi matematika (postfix).
·         Algoritma Backtracking (runtut balik).
·         Algoritma Rekursif.

Operasi-operasi Stack
Dalam penggunaannya suatu stack memiliki beberapa operasi yang dapat diterapkan. Adapun operasi-operasi dasar dari suatu stack adalah :

1.      Create (Stack)
Operasi Create (Stack) digunakan untuk membuat suatu stack baru dengan nama stack, yang nilai elemen saat stack tersebut dibuat 0 dan elemen teratasnya belum ada.

Spesifikasi :
·         Input               : Stack
·         Syarat awal     : Tidak ada
·         Output             : Kosong
·         Syarat akhir     : Stack dalam keadaan kosong

2.      IsEmpty (Stack)
Operasi ini digunakan untuk memeriksa isi suatu stack dalam keadaan kosong atau tidak. Operasi ini memiliki 2 kondisi boolean, yaitu:
·         True, apabila stack berada dalam kondisi kosong atau nilai elemennya = 0.
·         False, apabila stack tidak berada dalam kondisi kosong atau nilai elemennya > 0.

Spesifikasi :
·         Input               : Stack
·         Syarat awal     : Tidak ada
·         Output             : Boolean
·         Syarat akhir     : Sesuai kondisi Boolean di atas

3.      IsFull (Stack)
Operasi ini digunakan untuk memeriksa isi suatu stack dalam keadaan penuh atau tidak.

Spesifikasi :
·         Input               : Stack
·         Syarat awal     : Tidak ada
·         Output             : Boolean
·         Syarat akhir     : Bernilai True apabila stack dalam keadaan penuh
 
4.      Push (Stack, Elemen)
Operasi ini digunakan untuk menambahkan sebuah elemen dengan nilai X pada puncak suatu stack, sehingga posisi paling atas stack bernilai X, penerapan operasi Push pada suatu Stack(S) akan berakibat Overflow apabila nilai stack tersebut telah lebih dari maksimum.

Spesifikasi :
·         Input               : Stack dan elemen baru
·         Syarat awal     : Stack tidak penuh
·         Output             : Stack
·         Syarat akhir     : Stack bertambah satu elemen


Gambar 1.2 - Ilustrasi Operasi Push
5.      Pop (Stack)
Operasi ini digunakan untuk menghapus elemen teratas sebuah stack, sehingga jumlah nilai stack akan berkurang satu elemen dan nilai teratas stack akan berubah. Operasi Pop dapat menyebabkan kondisi Underflow apabila suatu stack telah berada dalam kondisi minimum saat dilakukan operasi Pop.

Spesifikasi :
·         Input               : Stack
·         Syarat awal     : Stack tidak dalam kondisi kosong
·         Output             : Stack dalam informasi Pop
·         Syarat akhir     : Stack berkurang satu elemen

 

Gambar 1.3 - Ilustrasi Operasi Pop

6.      Clear (Stack)
Operasi ini digunakan untuk mengosongkan stack (membuat nilainya menjadi 0).

7.      Top of Stack
Operasi ini digunakan untuk mengetahui elemen teratas pada sebuah stack.

Notasi Prefix, Infix, Postfix

  • ..


Dalam struktur data terdapat 3 notasi operasi yang dilakukan suatu operasi aritmatika, yaitu prefix, infix, dan postfix.

Namun, sebelumnya kita harus memahami terlebih dahulu indikator yang membentuk terjadinya notasi dalam struktur data. Notasi terbentuk dari operand dan operator. Operand adalah data atau nilai yang membantu dalam proses, sedangkan operator adalah fungsi yang digunakan dalam proses.

Contoh :
            A + B * C
            2 + 3 * 5

            Keterangan :    A, B, C, 2, 3, 5 adalah operand.
                                    +, * adalah operator

Setelah kita mengetahui indikator pembentuk suatu notasi, kita juga harus mengetahui level dari operator, seperti:
1.      “^” (pangkat)
2.      “*” (kali) atau “/” (bagi)
3.      “+” (tambah) atau “-” (kurang)

Namun, apabila terdapat operand di dalam sebuah kurung (“(.....)”), maka pengerjaannya akan dimulai dari operand yang berada di dalam kurung tersebut.

Contoh :
                        (A-B)*(C+D)

                        Prioritas pengerjaannya adalah sebagai berikut:
1.      Dalam kurung pertama : (A-B)
2.      Dalam kurung kedua : (C+D)
3.      Perkalian hasil pengurangan dengan hasil penjumlahan

Aturan notasi prefix, infix, dan postfix :
  • Notasi prefix   : Operator-Operand-Operand, + AB (disebut juga Polish Notation – PN)
  • Notasi infix     : Operand-Operator-Operand, A + B
  • Notasi postfix : Operand-Operand-Operator, AB + (disebut juga Reveser Polish Notation – RPN)

Notasi Prefix

Notasi Prefix adalah notasi yang operatornya ditempatkan sebelum dua operand.

Contoh :          A+B*C (Infix)
                        Maka, notasi prefixnya adalah +A*BC

Pemecahannya :

A + B * C

Diketahui ada 3 operand, yaitu : A, B, C dan 2 operator, yaitu : +, *. Proses dimulai dengan melihat dari level operator. Contoh di atas operator tertinggi adalah * kemudian +. Tanda * diapit oleh 2 operand, yaitu B dan C. Prefixnya dengan menggabungkan operand dan memindahkan operator ke depan dari operand, sehingga fungsi B * C, notasi prefixnya menjadi *BC. Hasil sementara dari notasi prefixnya adalah :

A + *BC

Selanjutnya, mencari prefix untuk operator yang berikutnya, yaitu +, cara yang dilakukan sama seperti di atas.  Operator +, diapit oleh 2 operand, yaitu A dan *BC. Gabungkan operand sehingga menjadi A*BC, lalu pindahkan operator + ke depan operand, sehingga hasil akhir menjadi :

+ A * B C

Contoh lainnya :

1.      A + B – C * D
A + B - * CD
+ AB - * CD
- + AB * CD

2.      A * B ^ C – D
A * ^ BC – D
* A ^ BC – D
                        - * A ^ BCD

3.      A + (B – C) * D
A + - BC * D
A + * - BCD
+ A * - BCD

Contoh konversi dari prefix ke infix :

            + / * ABCD

            Pengerjaan : (Mencari operator dimulai dari operand terkanan)

Cari operator pertama : *, ambil dua operand sebelumnya, yaitu A dan B, sehingga infixnya menjadi (A * B)
Cari operator kedua : /, ambil dua operand sebelumnya (A * B) dan C, sehingga infixnya adalah ((A * B) / C)
Cari operator ketiga : +, ambil dua operand sebelumnya ((A * B) / C) dan D, sehingga infixnya adalah ((A * B) / C) + D

Contoh konversi dari prefix ke postfix :

+ / * ABCD

            Pengerjaan : (Mencari operator dimulai dari operand terkanan)

Cari operator pertama : *, ambil dua operand sebelumnya, yaitu A dan B, sehingga postfixnya menjadi AB *
Cari operator kedua : /, ambil dua operand sebelumnya AB * dan C, sehingga postfixnya adalah AB * C /
Cari operator ketiga : +, ambil dua operand sebelumnya AB * C / dan D, sehingga postfixnya adalah AB * C / D +

Notasi Infix

Notasi infix adalah notasi yang operatornya ditempatkan di antara dua operand. Notasi ini telah dikenal secara umum oleh manusia dan selalu digunakan dalam perhitungan aritmatika.

Contoh :          A + B * C
                        (A + B) * C
                        A – (B + C) * D ^ E

Contoh konversi dari infix ke prefix :

            (A + B) – (C * D)

            Pengerjaan :

            Pengerjaan dalam kurung pertama : (A + B), prefixnya adalah + AB
            Pengerjaan dalam kurung kedua : (C * D), prefixnya adalah * CD
            Terakhir adalah operator -, + AB - * CD, prefixnya adalah - + AB * CD

Contoh konversi dari infix ke postfix :

            (A + B) – (C * D)

            Pengerjaan :

            Pengerjaan dalam kurung pertama : (A + B), postfixnya adalah AB +
            Pengerjaan dalam kurung kedua : (C * D), postfixnya adalah CD *
            Terakhir adalah operator -, AB + - CD *, postfixnya adalah AB + CD * -

Notasi Postfix

Notasi postfix adalah notasi yang operatornya ditempatkan setelah dua operand.

Contoh :          A+B*C (Infix)
                        Maka, notasi postfixnya adalah ABC*+

Pemecahannya :

A + B * C

Diketahui ada 3 operand, yaitu : A, B, C dan 2 operator, yaitu : +, *. Proses dimulai dengan melihat dari level operator. Contoh di atas operator tertinggi adalah * kemudian +. Tanda * diapit oleh 2 operand, yaitu B dan C. Postfixnya dengan menggabungkan operand B dan C menjadi BC, lalu memindahkan operator ke belakang operand C, sehingga fungsi B * C, notasi postfixnya menjadi BC*. Sehingga hasil sementara dari notasi postfix adalah :

A + BC*

Selanjutnya, mencari postfix untuk operator yang berikutnya, yaitu +, cara yang dilakukan sama seperti di atas.  Operator +, diapit oleh 2 operand, yaitu A dan BC*. Gabungkan operand sehingga menjadi ABC*, lalu pindahkan operator + ke depan operand, sehingga hasil akhir menjadi :

A B C * +

Contoh lainnya :

1.      A + B – C * D
A + B – CD *
AB + - CD *
AB + CD * -

2.      A * B ^ C – D
A * BC ^ – D
ABC ^ * - D
                        ABC ^ * D -

3.      A + (B – C) * D
A + BC - * D
A + BC – D *
ABC – D * +

Contoh konversi dari postfix ke infix :

            ABCD * / -

            Pengerjaan : (Mencari operator dimulai dari operand terkiri)

Cari operator pertama : *, ambil dua operand sebelumnya, yaitu C dan D, sehingga infixnya menjadi (C * D)
Cari operator kedua : /, ambil dua operand sebelumnya B dan (C * D), sehingga infixnya adalah (B / (C * D))
Cari operator ketiga : -, ambil dua operand sebelumnya A dan (B / (C * D)), sehingga infixnya adalah A – (B / (C * D))

Contoh konversi dari postfix ke prefix :

ABCD * / -

            Pengerjaan : (Mencari operator dimulai dari operand terkiri)

Cari operator pertama : *, ambil dua operand sebelumnya, yaitu C dan D, sehingga prefixnya menjadi * CD
Cari operator kedua : /, ambil dua operand sebelumnya B dan * CD, sehingga prefixnya adalah / B * CD
Cari operator ketiga : -, ambil dua operand sebelumnya A dan / B * CD, sehingga prefixnya adalah – A / B * CD