TUMPUKAN

1 PENGERTIAN TUMPUKAN
               Tumpukan (stack) bisa diartikan sebagai suatu kumpulan data yang seolah-olah ada data yang diletakkan diatas data yang lain. Dimana kita dapat menambah (menyisip) data dan mengambil (menghapus) data lewat ujung yang sama, yang disebut sebagai ujung atas tumpukan (top of stack).

2 PENYAJIAN TUMPUKAN
               Ada beberapa cara untuk menyajikan tumpukan dalam bahasa pemrograman. Cara paling sederhana adalah menggunakan larik (array). Dimana elemen tumpukan tidak melebihi maksimum elemen larik, karena jumlah elemen larik sudah tertentu (statis).
             Cara lain, tumpukan bisa disajikan menggunakan rekaman (record). Dengan demikian, tumpukan bisa dideklarasikan sebagai berikut :
             const MaxElemen = 255;
             type Tumpukan = record
                                                Isi : array [ 1 . . MaxElemen ] of integer;
                                                Atas : 0 . . MaxElemen
                                          end;
              var T : Tumpukan;
            Dengan deklarasi diatas dianggap bahwa elemen tumpukan T, yang tersimpan dalam larik T.Isi, adalah bertipe integer dan banyaknya elemen tumpukan maksimum adalah sebesar MaxElemen, dalam hal ini 255 elemen.

3 OPERASI PADA TUMPUKAN
             Ada dua operasi dasar yang bisa dilakukan pada sebuah tumpukan, yaitu operasi menyisipkan data (push), operasi menghapus data (pop). Karena kedalam tumpukan bisa mempush data, maka tumpukan sering disebut dengan pushdown list.

3.1 Operasi Push
             Operasi Push adalah operasi untuk menambah (menyisip) elemen pada sebuah tumpukan. Prosedur untuk operasi push adalah sebagai berikut :
                      procedure PUSH (var T : Tumpukan; X : integer);
                      begin
                               if T.Atas = MaxElemen then
                                           writeln (‘TUMPUKAN SUDAH PENUH’)
                               else
                                           begin
                                                  T.Atas := T.Atas + 1; T.Isi [T.Atas] := X
                                           end
                       end;

3.2 Operasi Pop
             Operasi pop adalah operasi untuk menghapus elemen yang terletak pada posisi paling atas dari sebuah tumpukan. Prosedur untuk operasi pop adalah sebagai berikut :
                      procedure POP (var T : Tumpukan);
                      begin
                               if T.Atas = 0 then
                                              writeln (‘TUMPUKAN SUDAH KOSONG’)
                               else
                                              T.Atas := T.Atas – 1
                       end;

4 PENULISAN UNGKAPAN NUMERIS
               Salah satu pemanfaatan tumpukan adalah untuk menulis ungkapan menggunakan notasi tertentu. Dalam penulisan ungkapan khususnya ungkapan numeris, kita selalu menggunakan tanda kurung untuk mengelompokkan bagian mana yang harus dikerjakan lebih dulu.
Contoh :
               1. (A + B) * (C – D)
                    Suku (A + B) akan dikerjakan lebih dahulu, kemudian suku (C – D) dan terakhir                                                       mengalikan hasil yang diperoleh dari dua suku ini.
               2. A + B * C – D
                    Maka B * C akan dikerjakan lebih dahulu, diikuti yang lain.
                    Dalam hal ini pemakaian tanda kurung akan sangat mempengaruhi hasil akhir.
               Cara penulisan ungkapan sering disebut dengan Notasi Infix, yang artinya adalah operator ditulis diantara dua operand. Seorang ahli matematika yang bernama Jan Lukasiewicz kemudian mengembangkan satu cara penulisan ungkapan numeris yang disebut Notasi Polish atau Notasi Prefix, yang artinya operator ditulis sebelum kedua operand yang akan disajikan. Berikut disajikan beberapa contoh notasi prefix dari notasi infix.
                        Infix                                       Prefix
                        A+B                                       +AB
                       (A + B) * (C – D)                  * + A B – C D
Secara sederhana, proses konversi dari infix menjadi prefix adalah sebagai berikut :

•  Ungkapan yang akan dikonversikan adalah (A + B) * (C – D)
•  Dengan menggunakan tanda kurung bantuan, ungkapan diatas dirubah menjadi [ + A B ] * [ - C D ]
•  Jika [ + A B ] dimisalkan P, dan [ - C D ] dimisalkan Q, maka ungkapan diatas bisa ditulis menjadi : P * Q
•  Selanjutnya notasi infix diatas dirubah menjadi notasi prefix : * P Q
•  Dengan mengembalikan P dan Q pada notasi semula dan menghapus tanda kurung bantuan, diperoleh notasi prefix dari persamaan (A + B) * (C – D) yaitu: * + A B – C D