MAKALAH STRUKTUR DATA STACK

MAKALAH STRUKTUR DATA

STACK

Oleh:

Adita Julian(1163001)

Dosen Pengampu:

I Made Yadi Dharma, S.Kom.,M.Kom.

  

POLITEKNIK POS INDONESIA 2017

DAFTAR ISI

KATA PENGANTAR

Puji syukur kehadirat Allah Yang Maha Esa atas segala rahmatNYA sehingga makalah ini dapat tersusun hingga selesai . Tidak lupa saya juga mengucapkan banyak terimakasih atas bantuan dari pihak yang telah berkontribusi dengan memberikan sumbangan baik materi maupun pikirannya.

Dan harapan saya semoga makalah ini dapat memenuhi tugas tugas mata kuliah Struktur Data dan semoga dapat menambah pengetahuan saya. Saya selaku penyusun berusaha mengerjakan dan menyelesaikannya dengan semaksimal mungkin. Walaupun sangat jauh dari kesempurnaan dan bahkan mungkin tidak sesuai dengan yang diharapkan, namun penyusun berharap Bapak dosen dapat menerima Makalah yang penyusun buat dengan berjudul “STACK ( TUMPUKAN )” ini.

Karena keterbatasan pengetahuan maupun pengalaman saya, saya berharap Bapak dapat memberi saran atau masukan agar makalah ini menjadi baik ataupun lebih baik lagi.

                                                                                         

                                                                                                      Bandung, April 2017

                 

                                                                                                      Penyusun

BAB I

PENDAHULUAN

A.  Latar Belakang

Salah satu konsep yang sangat berguna dalam ilmu komputer adalah satu bentuk struktur data yang disebut dengan stack (tumpukan). Dalam ilmu komputer sering sekali istilah stack (tumpukan) disebutkan. Dengan ini kami coba mengenali apa itu stack dan bagaimana uraian-uraiannya menurut 5w+1h.

Makalah berjudul (stack) ini dipilih berdasarkan undian kelompok tugas materi kuliah struktur data.

B.  Rumusan Masalah

1. Apa itu Stack?
2. Kenapa bisa tersusun menjadi stack?
3. Siapa pengguna Stack?
4. Mengapa aplikasi Stack digunakan?
5. Dimana mendeklarasikan Stack?
6. Kapan operasi pada Stack digunakan?
7. Bagaimana kelebihan dan kekurangan Stack?
8. Bagaimana contoh program stack?

C.  Tujuan

1. Untuk mengetahui definisi stack.
2. Untuk mengetahui apa yang ada dalam stack.
3. Untuk mengetahui siapa pengguna stack.
4. Untuk mengetahui tujuan penggunaan aplikasi stack.
5. Untuk mengetahui mendeklarasikan stack.
6. Untuk mengetahui penggunaan operasi stack.
7. Untuk mengetahui kelebihan dan kekurangan stack.
8. Untuk mengetahui contoh program stack.

BAB II

PEMBAHASAN

 1.    Apa itu Stack?

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

Stack adalah suatu koleksi atau kumpulan item data yang terorgaisasi dalam bentuk urutan linear, yang operasi pemasukan dan penghapusan datanya dilakukan pada salah satu sisinya.Sedangkan pengertian stack pada struktur data adalah sebagai tumpukan dari benda, sekumpulan data yang seolah-olah diletakkan di atas data yang lain, koleksi dari objek-objek homogen, atau Suatu urutan elemen yang elemennya dapat diambil dan ditambah hanya pada posisi akhir (top) saja.Stack merupakan bentuk khusus dari suatu struktur data, dimana node yang ditambahkan ke dalam list dan diambil dari list hanya pada kepalanya, atau dengan prinsip pengolahannya adalah last-in first-out (LIFO). Pada struktur ini hanya ada dua fungsi utama, yaitu push (memasukkan node ke dalam stack), dan pop (mengambil node dari stack).
PENGERTIAN TUMPUKANSecara sederhana tumpukan bisa diartikan sebagai kumpulan data yang seolaholah diletakkan di atas data yang lain. Dalam suatu tumpukan akan dapat dilakukan operasi penambahan (penyisipan) dan pengambilan (penghapusan) data melalui ujung yang sama, ujung ini merupakan ujung atas tumpukan.Contoh Kasus :Terdapat dua buah kotak yang ditumpuk, kotak yang satu akan ditumpuk diatas kotak yang lainnya. Jika kemudian tumpukan 2 kotak tadi, ditambah kotak ketiga, keempat, kelima, dan seterusnya, maka akan diperoleh sebuah tumpukan kotak yang terdiri dari N kotak.
F (ATAS)
EDCBA (BAWAH)
Dapat dilihat bahwa kotak B terletak diatas kotak A dan ada dibawah kotak C. Berdasarkan pada tumpukan tersebut dapat disimpulkan bahwa penambahan dan pengambilan sebuah kotak hanya dapat dilakukan dengan melewati satu ujung saja, yaitu bagian atas. Kotak F adalah kotak paling atas sehingga jika ada kotak lain yang akan disisipkan maka kotak tersebut akan diletakkan pada posisi paling atas (diatas kotak F). Demikian juga pada saat pengambilan kotak, kotak F akan diambil pertama kali.
Ilustrasi StackTerdapat dua buah kotak yang ditumpuk, kotak yang satu akan ditumpuk diatas kotak yang lainnya. Jika kemudian stack 2 kotak tadi, ditambah kotak ketiga, keempat, kelima, dan seterusnya, maka akan diperoleh sebuah stack kotak yang terdiri dari N kotakStack bersifat LIFO (Last In First Out) artinya Benda yang terakhir masuk ke dalam stack akan menjadi yang pertama keluar dari stack Const MaxElemen = 255;Type Tumpukan = record                                            isi : array[1 .. MaxElemen] of Integer;                                            atas : 0 .. MaxElemen                                      end;Var T : TumpukanDengan deklarasi di atas kita menganggap bahwa elemen tumpukan T, yang tersimpan dalam larik T.Isi adalah bertipe integer dan banyaknya elemen tumpukan maksimum adalah sebesar MaxElemen, yang dalam hal ini 255 elemen.
Pada medan Atas, nilainya menunjukkan banyaknya elemen yang ada dalam suatu tumpukan, yang sekaligus menunjukkan posisi elemen teratas dalam tumpukan yang dimaksud. Jika T.Atas = 5, berarti dalam tumpukan ada 5 elemen, yaitu T.isi[1],T.isi[2],….., T.isi[5]. Jika data yang diambil, maka nilai Medan T.Atas dikurangi 1 menjadi 4, yang berarti T.isi[4] adalah elemen teratas. Jika data ditambah maka nilai T.atas ditambah dengan 1 menjadi 6, sehingga T.isi[6] adalah elemen teratas.

2.    Kenapa bisa tersusun menjadi stack?

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. Tumpukan disebut juga “Push Down Stack” yaitu penambahan elemen baru (PUSH)ndan penghapusan elemen dari tumpukann(POP). Contoh pada PDA (Push Down Automaton). Sistem pada pengaksesan pada tumpukan menggunakn system LIFO (Last In First Out), artinya elemen yang terakhir masuk itu yang akan pertama dikeluarkan dari tumpukan (Stack). Ilustrasi tumpukan (Stack) dapat digambarkan seperti tumpukan CD atau tumpukan sate. Stack merupakan suatu susunan koleksi data dimana dapat ditambahkan dan dihapus selalu dilakukan pada bagian akhir data, yang disebut dengan Top Of Stack.

3.    Siapa pengguna stack?

Stack digunakan oleh seseorang yang akan meresenpetasi pemanggilan prosedur, perhitungan ekspresi aritmatika, rekursifitas, backtracking. Adapun contoh aplikasi stack, diantaranya:

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.

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.

4.    Mengapa aplikasi Stack digunakan?

Aplikasi stack 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 aritmetika, 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 aritmetika dibandingkan dengan notasi postfix, akan tetapi bagi mesin komplikasi postfix merupakan notasi yang digunakan untuk melakukan suatu perhitungan.

Stack juga biasa digunakan dalam mengontrol operasi dalam sebuah sistem operasi. Selain itu stack juga merupakan algoritma yang baik yang dapat digunakan untuk membuat phaser (membaca urutan operasi dari sebuah persamnaan matematika).

5.    Dimana mendeklarasikan stack?

Sebelum struktur data tumpukan ini bisa digunakan, harus dideklarasikan dahulu dalam kamus data. Ada beberapa cara pendeklarasian struktur data ini, salah satunya dengan menggunakan tata susunan linear (larik) dan sebuah variable, yang dikemas dalam tipe data record. Stack (tumpukan) adalah struktur data bertipe record yang terdiri dari field elemen, bertipe larik/array dengan indek dari 1 sampai dengan MaksTum (Maksimum Tumpukan), atas, bertipe interger berkisar dari 0 (saat kosong) sampai dengan MaksTum (Maksimum Tumpukan).

6.    Kapan operasi pada stack digunakan?

Operasi yang sering diterapkan pada struktur data Stack (Tumpukan) adalah Push dan Pop. Operasi – operasi yang dapat diterapkan adalah sebagai berikut :

Push                : digunakan untuk menembah item pada Stack pada Tumpukan paling atas.

Pop                  : digunakan untuk mengambil item pada Stack pada Tumpukan paling atas.

Clear                : digunakan untuk mengosongkan Stack

Create Stack    : membuat Tumpukan baru S, dengan jumlah elemen kosong.

MakeNull        : mengsongkan tumpukan S,jika ada elemen maka semua elemen dihapus.

sEmpty            : fungsi yang digunakan untuk mengecek apakah Stack sudah kosong.

Isfull                : fungsi yang digunakan untuk mengecek apakah Stack sudah penuh.

Pada proses Push, Tumpukan (Stack) harus diperiksa apakah jumlah elemen sudah mencapai masimum atau tidak. Jika sudah mencapai maksimum maka OVERFLOW, artinya Tumpukan penuh tidak ada elemen yang dapat dimasukkan ke dalam Tumpukan. Sedangkan pada proses Pop, Tumpukan harus diperiksa apakah ada elemen yang hendak dikeluarkan atau tidak. Jika tidak ada maka UNDERFLOW, artinya tumpukan kosong tidak ada elemen yang dapat diambil.

7.    Bagaimana kelebihan dan kekurangan stack?

Kelebihan stack yaitu penambahan dan penghapusan data dapat dilakukan dengan cepat, yaitu selama memori masih tersedia penambahan data bisa terus dilakukan. Dengan demikian tidak ada kekuatiran terjadinya stack overflow.

Kekurangan stack yaitu setiap sel tidak hanya menyimpan value saja, melainkan juga pointer ke sel berikutnya. Hal ini menyebabkan implementasi stack memakai linked list akan memerlukan memori yang lebih banyak daripada di implementasikan dengan array. Setiap halaman pada linked list hanya bisa di akses dengan cara sekuensial, sehingga lambat.

8.    Contoh codingan program stack(push,pop)

// Adita program

#include <cstdlib>

#include <string>

#include <iostream>

using namespace std;

int top=-1;

char stack[2];//asumsi max stack 100

char x;

void push()

{

    cout<<"masukkan satu karakter: ";

    cin>>x;

    top++;

    stack[top]=x;

}

void pop()

{

            if(top<0){

            cout<<"stack kosong"<<endl;

        return;

        }

    x=stack[top];

    top--;

    cout<<"karakter yang di 'POP' adalah "<<x<<endl;

}

void cetak()

{

    if(top<0){

                        cout<<"stack kosong" <<endl;

        return ;

            }

            int i=0;

            for(i=top;i>=0;i--)

            cout<<stack[i]<<endl;

            cout<<"\n'ADITA'"<<endl;

}

int main(int argc, char *argv[])

{

    char input;

    cout<<"\t\t\tPROGRAM STACK ADITA\n"<<endl;

    cout<<"MASUKKAN PILIHAN: "<<endl;

    cout<<"\t1.PUSH"<<endl;

    cout<<"\t2.POP"<<endl;

    cout<<"\t3.TAMPILKAN"<<endl;

    cout<<"\t4.QUIT"<<endl;

    while(true)

    {

        cout<<"\nMasukan pilihan: ";

        cin>>input;

        if(input=='1'){

                        push();

                        }else if(input=='2'){

                        pop();

                        }else if(input=='3'){

                        cetak();

                        }else if(input=='4'){

                        break;

                        }else{

        cout<<"Perintah ' "<<input<<" tidak dikenal"<<endl;

        }

    }

system("PAUSE");

return EXIT_SUCCESS;

}

SCREENSHOTNYA

BAB III

PENUTUP

Kesimpulan

Stack adalah suatu koleksi atau kumpulan item data yang terorganisasi dalam bentuk urutan linier, 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 hanya elemen pada TOP. Maka hampir tidak pernah dilakukan search atau bersifat LIFO (Last In First Out). Operasi-operasi pada Stack :

Create(Stack)Operasi Create(Stack) digunakan untuk membuat suatu stack baru dengan nama stack, yang nilai elemen saat stack tersebut dibuat adalah NOEL(S) = 0, TOP(S) = NULL (tidak terdefinisikan).IsEmpty(Stack)Operasi ini merupakan operasi untuk mencek isi dari suatu stack dalam keadaan kosong atau berisi.Operasi ini memiliki kondisi boolean yaitu :

• True jika stack tersebut kosong atau dapat dikatakan NOEL(S) = 0.
• False jika stack tersebut tidak dalam kondisi kosong atau dapat dikatakan NOEL(S)
• Push(Stack, Elemen)

Operasi ini merupakan operasi untuk menambahkan satu elemen dengan nilai X pada puncak suatu stack, sehingga posisi TOP(S) akan bernilai X, penerapan operasi push pasa suatu stack S akan berakibat overflow jika NOEL(S) dari stack tersebut telah bernilai maksimum.

Saran

Penulis menyadari bahwa dalam pembuatan makalah ini masih banyak kesalahan dan kekurangan, baik dari segi penulisan maupun dari segi pemaparan. Maka dari itu pemakalah menerima dan mengharapkan kritik dan saran dari pembaca yang sifatnya membangun, agar makalah ini dapat menjadi lebih baik dan menjadi rujukan bagi pembaca nantinya.