STACK

Penyimpanan dan pengambilan data yang sangat efektif apabila data yang terakhir masuk adalah data yang akan diambil pertama kali. Tumpukan memungkinkan akses ke satu item data saja, yaitu item terakhir yang disisipkan. Bila kita menghilankan item ini maka kita bisa mengakses ke sebelah item terakhir yang disisipkan, dan seterusnya

SEJARAH

Tumpukan pertama kali diusulkan pada tahun 1955, dan kemudian dipatenkan pada tahun 1957, oleh Friedrich L. Bauer Jerman. Konsep yang sama dikembangkan secara independen, pada sekita waktu yang sama, oleh Leonard Charles Australia Hamblin

PENGERTIAN

Merupakan tumpukan data yang seolah - olah diletakkan di atas data yang lain. Kita dapat menambahkan (menyisipkan) data dan mengambil (menghapus) data melalui ujung yang sama, yang disebut sebagai ujung atas stack (top of stack). Stack bersifat LIFO (Last In First Out): Benda yang terakhir masuk ke dalam stack menjadi yang pertama keluar dari stack.

Ilustrasi

Misalnya:

Terdapat stack S = (a1, a2, a3, ..., an)

    1. Elemen mana yang merupakan elemen terbawah.

    2. Elemen mana yang merupakan elemen paling atas

    3. Elemen mana yang akan dikeluarkan

    4. Elemen mana yang paling terakhir dikeluarkan

Karakteristik stack

• Elemen stack yaitu item - item data di elemen stack
• Top (elemen puncak dari stack)
• Jumlah elemen pada stack
• Status / kondisi stack

Kondisi Stack

Kondisi stack yang perlu diperhatikan adalah:

1. Penuh: bila elemen stack mencapai kapasitas maksimum. Pada kondisi ini tidak mungkin dilakukan penambahan ke stack. Penambahan elemen menyebabkan kodnisi kesalahan overlow
2. Kosong: bila tidak ada elemen di stack. Pada kondisi ini, tidak mungkin dilakukan pengambilan elemen dari stack. Pengambilan elemen menyebabkan kondisi kesalahan underflow.

STACK REPRESENTASI STATIS

Biasanya diimplementasikan dengan menggunakan array. Karena itu, stack dengan representasi statis dapat mengalami kondisi elemen penuh.

STACK REPRESENTASI DINAMIS

Biasanya diimplementasikan dengan menggunakan pointer yang menunjuk pada elemen - elemen yang dialokasikan pada memori. Elemen ditambahkan akan menggunakan penambahan elemen pada awal stack (addfirst). Saat pengambilan atau penghapusan elemen menggunakan penghapusan di awal stack (delfirst).

OPERATOR - OPERATOR DI DALAM STACK

OPERASI PUSH

Adalah operasi menambahkan elemn baru pada sebuah stack. Aturan penambahan stack

• Sebagai kondisi awal ada sebuah stack yang telah memiliki beberapa elemen dengan paling atas sebagai top.
• Dibuat sebuah elemen baru yang akan dimasukkan ke dalam stack
• Elemen baru dimasukkan kedalam stack.
• Penunjuk top pada stack diubah menunjuk ke elemen yang baru saja ditambahkan.

OPERASI POP

Adalah operasi mengambil sebuah elemen dari sebuah stack. Aturan mengambil sebuah elemen dari sebuah stack adalah sebagai berikut:

• Sebagai kondisi awal ada sebuah stack yang telah memiliki beberapa elemen dengan paling atas sebagai top.
• Penunjuk top diubah menjadi menunjuk elemen di bawah elemen atas
• Elemen atas diambil dari stack

Contoh

Ada sekumpulan perintah stack yaitu push (3), push(5), pop, push(2), pop, pop.

Maka apabila dijalankan maka hasilnya adalah:

CREATE

Operator ini berfungsi untuk membuat sebuah stack kosong.

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 sttack kosong

        atau

        ISEMPTY(S) = true, jika (S) = NULL

                               = false, jika (S) = 1

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

ISFULL

Operator ini berfungsi untuk menentukan apakah suatu stack adalah stack penuh. Operasinya akan bernilai boolean, dengan definisi sebagai berikut:

        ISFULL(S) = true, jika S adalah stack penuh

                           = false, jika S bukan stack penuh

        Catatan: ISEMPTY(CREATE(S)) = true

PENGGUNAAN STACK

Dalam dunia komputer, penggunaan stack (tumpukan) merupakan suatu hal yang umum digunakan seperti untuk penentuan alamat memory, penempatan ruang data dan aplikasi lain. Aplikasi stack juga digunakan untuk berbagai macam keperluan seperti pengujian kalimat palindrome, penguji tanda kurun (matchin parentheses), dan juga berfungsi sebagai konversi dari notasi infix menjadi notasi postfix. Sebuah kompilator mempunyai tugas, salah satu di antaranya adalah menyelidiki apakah pemrograman telah dengan cermat mengikuti aturan tata bahasa, atau sintaks dari bahasa pemrograman yang bersangkutan. Misalnya untuk paranthes kiri (tanda kurung buka) yang diberikan, harus dipastikan adanya parantheses kanan (tanda kurung tutup) yang bersangkutan.

MATCHING PARENTHESES

Proses ini dilakukan compiler untuk memeriksa kelengkapan tanda kurung yang terdapat pada suatu ekspesi 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 Parentehsis", 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 tida ada simbol"(" yang seharusnya mendahului.
• Jika stack tidak kosong artinya ada pasangannya dan langsung di-POP keluar stack.

INTERPRETER POSTFIX

Contoh lain penggunaan stack adalah pemeriksaan dan eksekusi ekspresi postfix. Ekspresi postfix merupakan ekspresi dengan aturan L R B dengan L adalah operand kiri, R operand kanan, dan B adalah operatornya. Ekspresi yang kita biasa gunakan sehari - hari adalah ekspresi infix dengan aturan L B R. Contoh, jika ekspresi infixnya "6 * 7 - 2" maka ekspresi postfixnya adalah "6 7 * 2 -".

NOTASI INFIX DAN POSTFIX

Suatu perhitungan aritmatika biasanya berhubungan dengan operand dan operator. Operand merupakan suatu karakter atau elemen yang nilainya dioperasikan dengan bantuan suatu operator untuk menghasilkan suatu solusi. Misalkan jika diberikan suatu ekspresi aritmatika 2 * 3, maka elemen 'dua' dan elemen 'tiga' merupakan operand dari ekspresi tersebut dan elemen '*' merupakan operator perkalian atas dua operand yang menghasilkan suatu solusi.

Dalam penggunaannya, dalam kehidupan sehari - hari notasi infix merupakan notasi aritmatika yang paling banyak digunakan untuk mengekspresikan suatu perhitungan aritmati dibanding dengan dua notasi yang lain. Akan tetapi notasi Postfix merupakan notasi yang digunakan oleh mesin kompilasi pada komputer dengan maksud untuk mempermudah proses pengkodean, sehingga mesin kompilasi membutuhkan stack untuk proses translasi ekspresi tersebut.

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 Pengurangan (-)

ATURAN DALAM PROSES TRANSFORMASI KE POSTFIX

Ekspresi aritmatik yang diberikan di - "Scan" dari kiri ke kanan. Bila simbol yang di-scan adalah "(", maka simbol tersebut di push ke dalam stack. Bila simbol yang di-scan adalah ")", maka seluruh isi stack di pop keluar mulai dari simbol "(" yang pertama ditemukan dalam stack. Bila simbol adalah operator, maka dilakukan perbandingan dulu dengan simbol (operator) yang berada pada posisi top dalam stack:

• Jika derajatnya setara atau lebih rendah dari simbol yang berada pada posisi top, maka top stack di - pop keluar sebagai output dan simbol yang baru di - push ke dalam stack.
• Jika derajatnya lebih tinggi dari simbol yang berada pada posisi top, maka simbol (operator) yang di - scan tersebut di - push ke dalam stack.

Bila simbol yang di - scan adalah operand, maka simbol tersebut langsung sebagai output. Bila simbol adalah ";" maka seluruh isi stack di - pop sebagai output.

Contoh:

3 + 2 * 5 = 325*+

(A + B) * (C - D ) / E; = AB+*CD-E/

Latihan 1

Ubah bentuk aritmatika berikut ke dalam bentuk postfix

1. ((A + B) * C / D + E ^ F) / G;
2. ((A * B) + C / D - E * F) * G;

STACK PADA ARRAY

Deklarasi MAX_STACK

    #define MAX_STACK 5

Deklarasi STACK dengan struct dan array data

    typedef struct STACK{

        int top;

        int data[5];

    };

Deklarasi variabel stack dari struct

    STACK tumpuk;

INISIALISASI

Pada mulanya isi top dengan -1, karena array dalam C/C++ dimulai dari 0, berarti stack adalah KOSONG

TOP adalah variabel penanda dalam STACK yang menunjukkan elemen teratas Stack. TOP of STACK akan selalu bergerak hingga mencapai MAX of STACK sehingga menyebabkan stack PENUH

FUNGSI IsEmpty

Digunakan untuk memeriksa apakah stack masih dalam kondisi kosong

Dengan cara memeriksa TOP of STACK. Jika TOP masih = -1 maka berarti stack masih kosong

FUNGSI IsFull

Digunakan untuk memeriksa apakah kondisi stack sudah penuh. Dengan cara memeriksa TOP of Stack.

Jika TOP of STACK = MAX_STACK-1 maka FULL (Penuh)

Jika TOP of STACK < MAX_STACK-1 maka belum penuh

FUNGSI PUSH

Digunakan untuk memasukkan elemen ke dalam stack dan selalu menjadi elemen teratas stack. Dengan cara:

1. Menambah satu (increment) nilai TOP of STACK setiap ada penambahan elemen stack selama stack masih belum penuh
2. Isikan nilai baru ke stack berdasarkan indeks TOP of STACK setelah ditambah satu (diincrement)

FUNGSI POP

Digunakan untuk menghapus elemen yang berada pada posisi paling atas dari stack. Dengan cara:

1. Ambil dahulu nilai elemen teratas stack dengan mengakses TOP of STACK.
2. Tampilan nilai yang akan diambil.
3. Lakukan decrement nilai TOP of STACK sehingga jumlah elemen stack berkurang 1

FUNGSI CLEAR

Digunakan untuk mengosongkan stack / membuat stack hampa sehingga Top pada Stack berada kembali di posisi Top = -1