STACKSTACKKuliah Struktur Data PascalKuliah Struktur Data Pascal

Definisi

Adalah tumpukan data yang seolah-olah ada data di atas data lain. data yang terakhir terakhir kali dimasukkan akan pertama kali

keluar dari stack tersebut. Stack dapat diimplementasikan sebagai representasi berkait atau

kontigu (dengan tabel fix) Ciri-Ciri Stack :

1.Elemen TOP (puncak) diketahui2.penyisipan dan penghapusan elemen selalu dilakukan di TOP3. LIFO ( Last In First Out)

Contoh : 5. Guntur, 4. aditya, 3.Tyas, 2.Hendra, 1.Dyah Data nomor 1 datang/masuk duluan, data nomor 5 yang paling atas

yang keluar terlebih dahulu. Suatu metode untuk Input dan hapus di dalam memori komputer

LIFOLIFO

Jika ingin mengambil 90, maka harus melakukan POP Jika ingin mengambil 90, maka harus melakukan POP untuk 37 dan 12 terlebih dahulu kemudian POP untuk untuk 37 dan 12 terlebih dahulu kemudian POP untuk 9090

Pemanfaatan Stack :Pemanfaatan Stack :

Perhitungan ekspresi aritmatika (posfix) Perhitungan ekspresi aritmatika (posfix) algoritma back traking (runut balik) algoritma back traking (runut balik) algoritma rekursif algoritma rekursif

AlgoritmaAlgoritma

Input/tambah dataInput/tambah data

Jika ada input maka no stack/no tumpukan yang Jika ada input maka no stack/no tumpukan yang semula 0 semula 0 akan tambah 1 demi 1 sampai maksimal tumpukan.akan tambah 1 demi 1 sampai maksimal tumpukan.

Pengambilan data Pengambilan data

Jika ada pengambilan data maka data Jika ada pengambilan data maka data dipindahkan di dipindahkan di variabel lain variabel lain contohnyacontohnya tempat Dan posisi tumpukann yang tempat Dan posisi tumpukann yang semula maksimal akan berkurang 1 demi 1 semula maksimal akan berkurang 1 demi 1 sampai sampai posisi 0 posisi 0 kembali. kembali.

Operasi pada STACKOperasi pada STACK

CREATECREATEMembuat stack baru yang masih kosong.Membuat stack baru yang masih kosong.

Procedure create;Procedure create;BeginBeginStack.top:=0;Stack.top:=0;End;End;

FULLFULLUntuk memeriksa apakah stack sudah penuh atau Untuk memeriksa apakah stack sudah penuh atau belum.belum.

Fuction full:bolean;Fuction full:bolean;BeginBeginStack.top:=max;Stack.top:=max;End;End;

PUSHPUSHMenambah sebuah elemen ( data ) kedalam stackMenambah sebuah elemen ( data ) kedalam stack

(Syarat: tidak bisa dilakukan jika stack sudah penuh)(Syarat: tidak bisa dilakukan jika stack sudah penuh)

Stack.data:=input;Stack.data:=input;

End;End;

End;End;

Procedure push ( input:string );Procedure push ( input:string );

BeginBegin

If not full thenIf not full then

BeginBegin

Stack.top:=stack.top;Stack.top:=stack.top;

POPPOPMengambil elemen teratas dari stack.Mengambil elemen teratas dari stack.

Syarat: Stack tidak boleh kosong.Syarat: Stack tidak boleh kosong.

Procedure Pop ( elemen:string );Procedure Pop ( elemen:string );

BeginBegin

If not empty thenIf not empty then

BeginBegin

Elemen:=stack.data;Elemen:=stack.data;

Stack.top:=top – 1;Stack.top:=top – 1;

End;End;

End;End;

Awal Program

Memastikan posisi tumpukan kosongElement yang terambil belum ada

InputanDipastikan tumpukan belum penuhMenginput satu persatu

PengambilanDipastikan tumpukan tidak kosongPengambilan satu persatu atau lebih dari satu

(optional)

PENGGUNAAN/APLIKASI STACKPENGGUNAAN/APLIKASI STACK

Logika stackLogika stack digunakan untuk menyelesaikan digunakan untuk menyelesaikan berbagai macam masalah. Antara lain digunakan pada berbagai macam masalah. Antara lain digunakan pada compiler, operating system dan dalam program-compiler, operating system dan dalam program-program aplikasi lainprogram aplikasi lain

Berikut ini tiga buah contoh aplikasi stack, yaitu Berikut ini tiga buah contoh aplikasi stack, yaitu

MATCHING PARENTHESES MATCHING PARENTHESES

NOTASI POSTFIXNOTASI POSTFIX

PROSES REKURSIFPROSES REKURSIF

MATCHING PARENTHESESMATCHING PARENTHESES

Proses ini dilakukan compiler untuk Proses ini dilakukan compiler untuk memeriksa kelengkapan tanda kurung memeriksa kelengkapan tanda kurung yang terdapat pada suatu ekspresi yang terdapat pada suatu ekspresi aritmetik aritmetik

Sedangkan stack di sini digunakan Sedangkan stack di sini digunakan sebagai tempat prosesnya sebagai tempat prosesnya

NOTASI POSTFIXNOTASI POSTFIX

mengubah suatu ekspresi aritmatik (string) ke mengubah suatu ekspresi aritmatik (string) ke dalam notasi postfixdalam notasi postfix

Notasi postfix ini digunakan oleh compiler untuk Notasi postfix ini digunakan oleh compiler untuk menyatakan suatu ekspresi aritmatik dalam bahasa menyatakan suatu ekspresi aritmatik dalam bahasa tingkat tinggi (high level language)tingkat tinggi (high level language)

Stack digunakan oleh compiler untuk Stack digunakan oleh compiler untuk mentransformasikan ekspresi aritmatik menjadi mentransformasikan ekspresi aritmatik menjadi suatu ekspresi dalam bentuk/notasi postfixsuatu ekspresi dalam bentuk/notasi postfix

ContohContoh : :

diberikan ekspresi aritmatik : A + B diberikan ekspresi aritmatik : A + B

Maka bentuknya dalam notasi postfix menjadi : AB+Maka bentuknya dalam notasi postfix menjadi : AB+

Urutan (prioritas) dari operator adalahUrutan (prioritas) dari operator adalah

1.1. Perpangkatan (^)Perpangkatan (^)

2.2. Perkalian (*) atau Pembagian (/)Perkalian (*) atau Pembagian (/)

3.3. Penjumlahan (+) atau Pengurangan (-)Penjumlahan (+) atau Pengurangan (-)

PROSES REKURSIFPROSES REKURSIF

Rekursi mempunyai Rekursi mempunyai artiarti suatu proses yang bias suatu proses yang bias memanggil dirinya sendiri. Dalam sebuah rekursi memanggil dirinya sendiri. Dalam sebuah rekursi sebenarnya tekandung pengertian sebuah prosedur sebenarnya tekandung pengertian sebuah prosedur atau fungsiatau fungsi

Perbedaannya dengan prosedur adalah bahwa rekursi Perbedaannya dengan prosedur adalah bahwa rekursi bisa memanggil dirinya sendiri, kalau prosedur atau bisa memanggil dirinya sendiri, kalau prosedur atau fungsi harus diipanggil melalui pemanggil prosedur fungsi harus diipanggil melalui pemanggil prosedur atau fungsiatau fungsi