STACK

stack atau tumpukan merupakan sebuah koleksi objek yang menggunakan prinsip LIFO (Last In First Out), yaitu data yang terakhr kali dimasukkan akan pertama kali keluar dari stack tersebut. Stack dapat diimplementasikan sebagai representasi berkait atau kontigu (dengan tabel fix).

Misal diberikan Stack S sebagai berikut :

      S = [ S1, S2, .........., ST ]   maka TOP(S) = ST.

     Untuk menunjukkan jumlah elemen suatu stack digunakan notasi NOEL. Dari stack di atas, maka NOEL(S) = T.



Ciri Stack :

• Elemen TOP (puncak) diketahui
• penisipan dan penghapusan elemen selalu dilakukan di TOP
• LIFO

Pemanfaatan Stack :

• Perhitungan ekspresi aritmatika (posfix)
• algoritma backtraking (runut balik)
• algoritma rekursif

Operasi Stack yang biasanya :

1. Push (input E : typeelmt, input/output data : stack): menambahkan sebuah elemen ke stack
2. Pop (input/output data : stack, output E : typeelmt ) : menghapus sebuah elemen stack
3. IsEmpty ()
4. IsFull ()
5. dan beberapas selektor yang lain

 CREATE
      Operator ini berfungsi untuk membuat sebuah stack kosong dan didefinisikan bahwa :

NOEL(CREATE(S)) = 0 dan TOP(CREATE(S)) = null

 
ISEMPTY
      Operator ini berfungsi untuk menentukan apakah suatu stack adalah stack kosong. Operasinya akan bernilai boolean, dengan definisi sebagai berikut :
            ISEMPTY(S) = true, jika S adalah stack kosong
                                    = false, jika S bukan stack kosong
      atau
            ISEMPTY(S) = true, jika NOEL(S) = 0
                                    = false, jika NOEL(S) 0

            Catatan :       ISEMPTY(CREATE(S)) = true.
                                                       

PUSH
      Operator ini berfungsi untuk menambahkan satu elemen ke dalam stack. Notasi yang digunakan adalah :

            PUSH(E,S)
Artinya : menambahkan elemen E ke dalam stack S.

      Elemen yang baru masuk ini akan menempati posisi TOP.
       Jadi : TOP(PUSH(E,S)) = E.
      Akibat dari operasi ini jumlah elemen dalam stack akan bertambah, artinya NOEL(S) menjadi lebih besar atau stack menjadi tidak kosong (ISEMPTY(PUSH(E,S)) = false).

POP
      Operator ini berfungsi untuk mengeluarkan satu elemen dari dalam stack. Notasinya :
                   POP(S)

      Elemen yang keluar dari dalam stack adalah elemen yang berada pada posisi TOP. Akibat dari operasi ini jumlah elemen stack akan berkurang atau NOEL(S) berkurang dan elemen pada posisi TOP akan berubah. Operator POP ini tidak dapat digunakan pada stack kosong, artinya :

                   POP(CREATE(S)) = error condition

Catatan : TOP(PUSH(E,S)) = E


DEKLARASI STACK PADA BAHASA PEMROGRAMAN
      Dalam bahasa pemrograman, untuk menempatkan stack biasanya digunakan sebuah array. Tetapi perlu diingat di sini bahwa stack dan array adalah dua hal yang berbeda. Misalkan suatu variabel S adalah sebuah stack dengan 100 elemen. Diasumsikan elemen S adalah integer dan jumlah elemennya maksimum adalah 100 elemen. Untuk mendeklarasikan stack dengan menggunakan array, harus dideklarasikan pula variabel lain yaitu TOP_PTR yang merupakan indeks dari array. Variabel TOP_PTR ini digunakan untuk menyatakan elemen yang berada pada posisi TOP dalam stack tersebut. Selanjutnya gabungan kedua variabel ini diberi nama STACK_STRUCT. Kemudian didefinisikan bahwa :

                  NOEL(S) = TOP_PTR
                  ISEMPTY(S) = TRUE, jika TOP_PTR = 0 dan
                                             FALSE, jika TOP_PTR > 0.

Maka bentuk deklarasinya dalam PASCAL adalah :

                  TYPE Stack_Struct = Record
                                                           Stack   : array[1..100] of integer;
                                                           TopPtr : integer;
                                                       End;
                  VAR S : Stack_Struct;

PENGGUNAAN/APLIKASI STACK
      Logika stack digunakan untuk menyelesaikan berbagai macam masalah. Antara lain digunakan pada compiler, operating system dan dalam program-program aplikasi. Berikut ini tiga buah contoh aplikasi stack, yaitu :

MATCHING PARENTHESES
      Proses ini dilakukan compiler untuk memeriksa kelengkapan tanda kurung yang terdapat pada suatu ekspresi aritmetik. Sedangkan stack di sini digunakan sebagai tempat prosesnya. Algoritma yang digunakan adalah :

1.   Elemen-elemen suatu ekspresi aritmetik (string) di-Scan dari kiri ke kanan.
2.   Jika ditemukan simbol "(" atau "Left parenthesis", maka simbol tersebut di-push ke dalam stack.
3.   Jika ditemukan simbol ")" atau "Right parenthesis", maka isi stack diperiksa.
          Jika stack kosong terjadi kesalahan.
            berarti : ada simbol ")", tetapi tidak ada simbol "(" yang seharusnya mendahului.
          Jika stack tidak kosong artinya ada pasangannya dan langsung di-POP keluar          stack.

NOTASI POSTFIX
      Bentuk aplikasi stack yang lain adalah mengubah suatu ekspresi aritmatik (string) ke dalam notasi postfix. Notasi postfix ini digunakan oleh compiler untuk menyatakan suatu ekspresi aritmatik dalam bahasa tingkat tinggi (high level language). Stack digunakan oleh compiler untuk mentransformasikan ekspresi aritmatik menjadi suatu ekspresi dalam bentuk/notasi postfix.

Contoh :
Misal diberikan ekspresi aritmatik : A + B ;
Maka bentuknya dalam notasi postfix menjadi : AB+
Urutan (prioritas) dari operator adalah :
      1.   Perpangkatan (^)
      2.   Perkalian (*) atau Pembagian (/)
      3.   Penjumlahan (+) atau Pengurangan (-)

Posted in: Artikel,Kode Komputer,Komputer