IMPLEMENTASI STACK PADA STRUKTUR DATA

KATA PENGANTAR

Segala puji bagi  Tuhan Yang Maha Esa atas segala berkat, rahmat, taufik, serta hidayah-Nya yang tiada terkira besarnya, sehingga penulis dapat menyelesaikan makalah dengan judul ”IMPLEMENTASI STACK PADA STRUKTUR DATA”.

Adapun isi dari makalah yang kami buat terdiri dari empat baba tau bagian. Bab pertama Pendahuluan. Bab kedua berisi Pembahasan, membahas tentang Definisi, Operasi dasar pada stack, deklarasi stack dalam pemrograman, dan implementasi dalam kehidupan sehari-hari, bab ketiga berisi contoh program stack, serta bab empat berisi kesimpulan.

Meskipun penulis berharap isi dari makalah ini bebas dari kekurangan dan kesalahan, namun selalu ada yang kurang. Oleh karena itu, penulis mengharapkan kritik dan saran yang membangun agar skripsi ini dapat lebih baik lagi. Akhir kata penulis berharap agar makalah ini bermanfaat bagi semua pembaca.

Medan , Mei 2013

Penyusun

i

DAFTAR ISI

KATA PENGANTAR………………………………………………………………      i

DAFTAR ISI…………………………………………………………………………    ii

BAB I PENDAHULUAN…………………………………………………………...     1

BAB II PEMBAHASAN…………………………………………………………….    2

            II.1 Defenisi…………………………………………………………………...    2

            II.2 Operasi Dasar Pada Stack…………………………………………………   3         

            II.3 Deklarasi Stack Pada Bahasa Pemrograman………………………………   5

            II.4 Penggunaan / Aplikasi Stack………………………………………….......   5 

            II.5 Implementasi Stack Dalam Kehidupan Sehari-hari……………………….   7     

BAB III CONTOH PROGRAM STACK………………………………………….   12    

            III.1 Contoh Program Stack 1………………………………………………..    12

            III.2 Contoh Program Stack 2……………………………………………......    14

BAB IV KESIMPULAN……………………………………………………………   16

            IV.1 Kesimpulan……………………………………………………………....  16

            IV.2 Saran…………………………………………………………………….   16

DAFTAR PUSTAKA………………………………………………………………..  17     

ii

BAB I

PENDAHULUAN

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[1]. 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 postfix.

Pada perhitungan aritmatika, notasi infix adalah notasi yang menempatkan operator ditengah dua operand sedangkan notasi Postfix adalah notasi yang menempatkan operator setelah dua operand. Penggunaan notasi infix merupakan hal yang lumrah digunakan dalam perhitungan aritmatika dibandingkan dengan penggunaan notasi Postfix, akan tetapi bagi mesin kompilasi notasi Postfix merupakan notasi yang digunakan untuk melakukan suatu perhitungan.

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 [2].

BAB II

PEMBAHASAN

II.1      DEFENISI

Dalam dunia komputer, penggunaan stack atau tumpukan merupakan salah satu komponen penting untuk menjamin proses penanganan suatu data disamping hal lain seperti Queue (antrian), linked list, dan tree.

Definisi 1.

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[1]

Definisi 2.

Diberikan suatu himpunan yang terurut himpunan sebagai S = {S₁, S₂, ......., S_T}, T pada anggota S merupakan linear order, sehingga stack dari himpunan tersebut memiliki informasi sebagai berikut [1] :

1. Elemen puncak dari stack dalam himpunan S dikatakan sebagai TOP,

Sehingga :

TOP[S} = S_{T ............................................................................}(1)

2. Banyaknya elemen stack dalam himpunan S dikatakan sebagai NOEL,

Sehingga :

NOEL= T, dimana himpunan dari S tersebut dapat disusun sebagai :

S = {S₁, S₂, .........., S_NOEL} .............................(2)

Jadi, Stack adalah suatu tumpukan dari benda. Konsep utamanya adalah LIFO (Last In First Out), benda yang terakhir masuk dalam stack akan menjadi benda pertama yang dikeluarkan dari stack.

II.2 OPERASI DASAR PADA STACK

      Ada empat operasi dasar yang didefinisikan pada stack, yaitu :

      1. CREATE(stack)

      2. ISEMPTY(stack)

      3. PUSH(elemen,stack)

      4. POP(stack)

  CREATE

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

  ISEMPTY

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

           

      atau

     

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

  PUSH

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

                       

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:

                         

      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 :

                       

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

II. 3  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 :

                 

II.4 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.

Misalkan NEXT CHAR adalah suatu karakter terakhir dalam suatu string. Berikut ini bentuk flowchart (logika proses) yang digunakan pada proses matching ini :

     

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

Aturan yang digunakan dalam proses transformasi tersebut adalah :

1.   Ekspresi aritmatik yang diberikan di- "Scan" dari kiri ke kanan.

2.   Bila simbol yang di-scan adalah "(", maka simbol tersebut di push ke dalam stack.

3.   Bila simbol yang di-scan adalah ")", maka seluruh isi stack di pop keluar mulai dari simbol "(" yang pertama ditemukan dalam stack.

4.   Bila simbol adalah operator, maka dilakukan perbandingan dulu dengan simbol (operator) yang berada pada posisi top dalam stack.

a.   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.

b.   Jika derajatnya lebih tinggi dari simbol yang berada pada posisi top, maka simbol (operator) yang di-scan tersebut di-push ke dalam stack.

5.   Bila simbol yang di-scan adalah operand, maka simbol tersebut langsung sebagai output.

6.   Bila simbol adalah ";" maka seluruh isi stack di-pop sebagai output.

II.5 IMPLEMENTASI STACK DALAM KEHIDUPAN SEHARI-HARI

                  Dapat di ilustrasikan seperti sebuah tumpukan buku, ketika mengambil sebuah buku di dalam tumpukan itu maka harus diambil satu persatu dari buku yang paling atas dari tumpukan buku tersebut. Beberapa contoh ilustrasi yang dapat menggambarkan tumpukan dan cara beroperasinya adalah tumpukan sate, tumpukan Compact Disk (CD), dan lain-lain. Sate misalnya, si pembuat sate menusukan (memasukan) daging sate ke tusukan satu per satu dari ujung tusukan (ujung yang runcing) menuju/mendekati batas pangkal, jika telah dimasak, maka si pemakan sate akan mengeluarkan (memakan) sate satu persatu dari ujung (yang akhir-akhir dimasukan si pembuat, itulah yang awal-awal dimakan). Demikian juga dengan tumpukan CD, orang akan mengambil CD dari tumpukan teratas yang mana merupakan yang terakhir dimasukan di dalam tumpukan.

 Cara mendefenisikan Stack dengan Array of Struct yaitu:

1. Definisikan Stack dengan menggunakan struct

2. Definisikan konstanta MAX_STACK untuk menyimpan maksimum isi stack

3. Buatlah variabel array data sebagai implementasi stack

4. Deklarasikan operasi-operasi/function di atas dan buat implemetasinya.

contoh :

//Deklarasi MAX_STACK

                #define MAX_STACK 10   

            

//Deklarasi STACK dengan struct dan array data

                typedef struct STACK{

                                int top;

                                char data[10][10];                                                           

                }; 

//Deklarasi/buat variabel dari struct

                STACK tumpuk;

Inisialisasi Stack

Pada mulanya isi top dengan -1, karena array dalam C dimulai dari 0, yang berarti stack adalah kosong.

Top adalah suatu variabel penanda dalam STACK yang menunjukkan elemen teratas Stack sekarang.  Top Of Stack akan selalu bergerak hingga mencapai MAX of STACK sehingga menyebabkan stack penuh.

Ilustrasi Stack pada saat inisialisasi

IsFull berfungsi untuk memeriksa apakah stack sudah penuh atau tidak. Dengan cara, memeriksa top of stack, jika sudah sama dengan MAX_STACK-1 maka full, jika belum (masih lebih kecil dari MAX_STACK-1)  maka belum full.

Ilustrasi Stack pada kondisi Full

IsEmpty berfungsi untuk memeriksa apakah stack masih kosong atau tidak. Dengan cara memeriksa top of stack, jika masih -1 maka berarti stack masih kosong.

Push berfungsi untuk memasukkan elemen ke stack, selalu menjadi elemen teratas stack (yang ditunjuk oleh TOS).

Tambah satu (increment)  nilai top of stack lebih dahulu setiap kali ada penambahan elemen stack.

Asalkan stack masih belum penuh, isikan data baru ke stack berdasarkan indeks top of stack setelah diincrement sebelumnya.

Pop berfungsi untuk mengambil elemen teratas (data yang ditunjuk oleh TOS) dari stack.

Ambil dahulu nilai elemen teratas stack dengan mengakses top of stack, tampilkan nilai yang akan dipop, baru dilakukan decrement nilai top of stack sehingga jumlah elemen stack berkurang.

 

Print berfungsi untuk menampilkan semua elemen-elemen stack dengan cara looping semua nilai array secara terbalik, karena kita harus mengakses dari indeks array tertinggi terlebih dahulu baru ke indeks yang kecil.

 

 

Operasi Push

void Push (NOD **T, char item)

                {

                                NOD *n;

                                n=NodBaru (item);

                                n->next=*T;

                                *T=n;

                }

Operasi Pop

char Pop (NOD **T)

                {

                                NOD *n; char item;

                                if (!StackKosong(*T)) {

                                                P=*T;

                                                *T=(*T)->next;

                                                item=P->data;

                                                free(P);

                                }

                                return item;

                }

 

create berfungsi untuk membuat sebuah stack baru yang masih kosong.

Sumber : http://blog-arul.blogspot.com/2012/01/stack-pada-struktur-data.html#ixzz2SzNerqRz

Fungsi dalam Stack :
* Fungsi init : fungsi yang digunakan untuk inisialisasi atau membuat stack baru yang masih kosong.
* Fungsi full : digunakan untuk mengetahui stack penuh atau tidak.
* Fungsi empty : digunakan untuk mengetahui stack kosong atau tidak.
* Fungsi clear : digunakan untuk mengosongkan stack. Stack dianggap kosong apabila puncak stack berada pada posisi -1.
* Fungsi push : digunakan untuk menambahkan data ke dalam stack. Penambahan data tidak bisa dilakukan apabila stack sudah penuh. Urutan perintahnya adalah: menambahkan nilai top dan menambahkan data pada posisi nilai top. Jika dalam Linked List menggunakan method addLast.
* Fungsi pop :  digunakan untuk mengeluarkan data teratas stack dengan syarat bahwa stack tidak kosong.
Urutan perintahnya adalah : menghapus data pada posisi nilai top dan menurunkan nilai top. Jika dalam Linked List menggunakan method removeLast.

BAB III

CONTOH PROGRAM STACK

 III.1 CONTOH PROGRAM STACK 1

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.util.Stack;

public class KardusStack {

private static Stack<Integer> stack;

private static int ukuran;

public static void main(String[] args) {

System.out.print("masukan banyak kardus!");

ukuran = inputData();

buatStack(ukuran);

bacaData();

tulisData();

}

private static void buatStack(int ukuran) {

stack = new Stack<Integer>();

}

private static void bacaData() {

int data;

System.out.println("Masukkan nilai stacknya : ");

for(int i=0; i<ukuran; i++) {

System.out.print("Data ke-" + (i+1) + " = ");

data = inputData();

stack.push(data);

}

}

private static void tulisData() {

System.out.println("Isi stack menggunakan prosedur POP : ");

int dataStack;

for(int i=0; i<ukuran; i++) {

dataStack = stack.pop();

System.out.println("Nilainya = " + dataStack);

}

}

private static Integer inputData() {

BufferedReader bfr =

new BufferedReader(new InputStreamReader(System.in));

String angkaInput = null;

try {

angkaInput = bfr.readLine();

} catch (IOException e) {

e.printStackTrace();

}

int Data =

Integer.valueOf(angkaInput).intValue();

return Data;

}

}

Gambar 1

Hasil output

III.2 CONTOH PROGRAM STACK 2

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.util.Stack;

public class StackDemo {

            public static void main(String[] args) throws IOException {

                        // Create a new, empty stack

                        Stack lifo = new Stack();

                        System.out.println ("===========================");

                        System.out.println ("==Selamat Datang di Program Stack Sederhana =");

                        System.out.println ("===========================");

                        System.out.println ("= Berapa Data yang Ingin Dimasukkan Kedalam Stack==");

                        BufferedReader masuk = new BufferedReader (new InputStreamReader (System.in));

                        String test = masuk.readLine ();

                        int x = Integer.parseInt(test);

                       

                        for (int a=x; a>0; --a){

                                    System.out.print ("Masukkan push stack :");

                                    String test1 = masuk.readLine();

                                    lifo.push (test1);

                                    }

                                                                       

System.out.println (" Stack :"+ lifo);

System.out.println (" top :"+ lifo.peek());

System.out.println (" noel :"+ lifo.size());

System.out.println (" Berapa kali ingin melakukan pop :");

String b = masuk.readLine();

int c = Integer.parseInt(b);

for (int d=c; d>0; --d){

            System.out.println (" Pop :"+ lifo.pop());

            System.out.println (" Stack :"+ lifo);

}

System.out.println (" top :"+ lifo.peek());

System.out.println (" noel :"+ lifo.size());

System.out.println (" Terima kasih atas Kunjungannya");

}

}

           

Gambar 2

Hasil output stack II

BAB IV

KESIMPULAN

IV.1 Kesimpulan

                  Kesimpulan dari pembuatan stack  adalah bahwa 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.

Pada stack, jarang sekali dilakukan traversal, karena keunikan Stack justru pada operasi yang hanya menyangkut elemen TOP. Namun dibutuhkan traversal misalnya untuk mencetak isi Stack.

Pada stack, elemen yang diproses hanyalah elemen pada TOP. Maka hampir tidak pernah dilakukan search.

IV.2 Saran

 Penggunaan stack pada struktur data sangat bermanfaat untuk para pemrogram untuk melakukan suatu pemakain dalam informatika misalnya untuk meresenpetasi pemanggilan prosedur, perhitungan ekspresi aritmatika, rekursifitas, backtracking. Gunakan stack pada program yang operasinya selalu dilakukan pada elemen yang paling atas.