TUGAS MANDIRI

STRUKTUR DATA DENGAN

OPERASI STACK (TUMPUKAN)

MATA KULIAH : STRUKTUR DATA

PROGRAM STUDI TEKNIK INFORMATIKA

UNIVERSITAS PUTERA BATAM

2013

Nama : Asep Jaenudin

NPM : 120210034

Kode kelas : 122-IF211-M5

Dosen : Ganda Sirait, S.Si., M.SI.

KATA PENGANTAR

Segala puji dan syukur penyusun panjatkan kehadirat Allah SWT yang

telah menganugerahkan rahmat, karunia serta ridha-Nya, sehingga penyusun dapat

menyelesaikan makalah Tugas mandiri tentang ”STRUKTUR DATA DENGAN

OPERASI STACK (TUMPUKAN)”. Makalah Tugas mandiri ini disusun sebagai

salah satu tugas pada mata kuliah Struktur Data.

Dalam penyusunan makalah ini, penyusun telah banyak menerima

bimbingan dan saran-saran dari berbagai pihak. Maka pada kesempatan ini

penyusun ingin mengucapkan terima kasih yang setulusnya kepada:

1. Bapak Ganda Sirait, selaku Dosen mata kuliah Struktur Data di Universitas

Putera Batam yang telah banyak memberikan penjelasan teori yang

berkaitan dengan tugas makalah ini.

2. Rekan-rekan serta semua pihak yang tidak dapat penyusun sebutkan satu

persatu yang telah membantu dalam pembuatan makalah ini.

Akhirnya penyusun berharap makalah ini dapat berguna dan dapat

dipergunakan sebagaimana mestinya. Penyusun mengharapkan kritik dan saran

untuk kemajuan di masa-masa mendatang. Atas perhatiannya penyusun ucapkan

terima kasih.

Batam, 3 Juni 2013

Penyusun

i

DAFTAR ISI

KATA PENGANTAR......................................................................................... i

DAFTAR ISI........................................................................................................ ii

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

1.1 Latar Belakang Masalah.......................................................................... 1

1.2 Rumusan Masalah................................................................................... 2

1.3 Tujuan dan Manfa’at Penyusunan........................................................... 2

BAB II. PEMBAHASAN.................................................................................... 3

2.1 Pengertian dari Stack............................................................................... 3

2.2 Pendeklarasian Stack............................................................................... 6

2.3 Skema Traversal Pada Stack................................................................... 7

2.4 Skema Search Pada Stack........................................................................ 7

2.5 Operasi Dan Fungsi Pada Stack.............................................................. 7

2.6 Deklarasi Stack Pada Bahasa Pemrograman........................................... 11

2.7 Penggunaan/Aplikasi Stack..................................................................... 13

2.8 Operasi Logika Pada Struktur Data Stack............................................... 14

2.9 Aplikasi Stack Pada Pemrograman Pascal.............................................. 19

BAB III. PENUTUP............................................................................................ 25

3.1 Kesimpulan............................................................................................. 25

3.2 Saran ....................................................................................................... 26

DAFTAR PUSTAKA.......................................................................................... 27

ii

BAB I

PENDAHULUAN

1.1 Latar Belakang

Pemakaian struktur data yang tepat di dalam proses pemrograman akan

menghasilkan algoritma yang lebih jelas dan tepat, sehingga menjadi program secara

keseluruhan lebih efisien dan sederhana seperti stack merupakan bagian dari struktur

data yang dikategorikan ke dalam bentuk linier data, dimana operasi pemasukan

maupun pengeluaran data selalu dilakukan pada salah satu sisinya.

Dalam dunia komputer, penggunaan stack (tumpukan) merupakan suatu hal

yang umum digunakan seperti untuk penentuan alamat memory, penempatan ruang

data dan aplikasi lain. Stack bersifat LIFO (Last In First Out) dan benda yang terakhir

masuk ke dalam stack akan menjadi benda pertama yang dikeluarkan dari stack itu.

Dalam prosesnya, untuk memasukkan sebuah data ke dalam stack atau dengan

kata lain ke bagian atas dari sebuah tumpukan digunakan perintah push. Pada stack

jarang sekali dilakukan operasi traversal, karena keunikan stack justru pada operasi

yang hanya menyangkut elemen TOP (atas).

Struktur ini sering dipakai dalam informatika misalnya untuk

merepresentasikan pemanggilan prosedur, perhitungan ekspresi aritmatika,

rekursifitas, dan backtracking. Satu hal yang perlu diingat adalah bahwa di dalam

suatu tumpukan dapat menambah (menyisipkan) data dan mengambil (menghapus)

data lewat ujung yang sama yang disebut sebagai ujung atas tumpukan.

Penyajian stack bisa menggunakan array, namun kurang tepat. Array bisa

digunakan kalau elemen stack tidak melebihi batas maksimum. Tipe yang bisa

digunakan adalah record.

Manipulasi dengan menggunakan record mempunyai dua medan, yaitu medan

penyimpanan elemen tumpukan dan medan pencatat posisi ujung atas tumpukan.

Stack dapat diimplementasikan sebagai representasi berkait atau kontinyu (dengan

tabel fix). “TOP“ merupakan pintu untuk keluar masuknya elemen – elemen stack.

1

1.2 Rumusan Masalah

Berdasarkan latar belakang tadi, maka penyusun menemukan beberapa

permasalahan yang kiranya akan menjadi bahasan pada penyusunan makalah ini,

diantaranya yaitu :

1. Apa pengertian dari stack pada struktur data?

2. Bagaimana pendeklarasian Stack?

3. Bagaimana skema traversal dari stack?

4. Bagaimana skema search dari stack?

5. Apa saja operasi-operasi dan fungsi dasar pada stack?

6. bagaimana deklarasi stack pada Bahasa Pemrograman?

7. Bagaimana penggunaan/aplikasi dari stack?

8. Bagaimana operasi logika pada Struktur Data stack?

9. Bagaimana aplikasi Stack pada pemrograman pascal?

1.3 Tujuan dan Manfaat Penyusunan

Tujuan makalah ini adalah untuk mengetahui lebih jauh tentang penggunaan

operasi stack dalam struktur data. Sehingga tentunya akan dapat memberikan sebuah

manfaat bagi diri kita maupun orang lain. Dengan penyusunan makalah ini, semoga

ada manfaat yang dapat kita rasakan, terutama bagi rekan-rekan yang belajar tentang

struktur data dan bagaimana implementasi dari struktur data tersebut dalam suatu

aplikasi sederhana.

2

BAB II

PEMBAHASAN

2.1 Pengertian Stack

Stack  (tumpukan) dapat dikatakan sebagai list  yang operasi penghapusan dan

pemyisipan elemennya dilakukan disatu ujung. Dalam kehidupan sehari-hari, terdapat

banyak kejadian yang mempunyai sifat seperti stack, salah satunya adalah  cerita di

bawah ini:

Perhatikan sebuah tumpukian piring disebuah warung makan. Piring-piring

tersebut tersusun rapat dari atas ke bawah (membentuk barisan berurutan). Setiap kali

ada pembeli datang, maka piring yang paling atas akan diambil (menghapus elemen)

yang berarti mengurangi jumlah piring dalam tumpukan. Bila tumpukan

itu sudah habis atau tinggal sedikitmaka pegawai warung akan menambahkan piring

lain yang masih bersih (menambah elemen) piring yang paling terakhir diletakkan

pasti akan terletak ditumpukan paling atas dan piring yang terletak paling atas dalam

tumpukan itu pasti merupakan tumpukan piring yang terakhir kali dimasukkan.

Kesimpulannya adalah penambahan dan penghapusan elemen hanya dapat

dilakukan di ujung atas tumpukan piring. Proses seperti itu biasa disebut Last In First

Out (LIFO).

Secara formal sebuah stack bertipe T didefinisikan sebagai sebuah barisan

berhingga atas elemen-elemen bertipe T, bersama-sama dengan operasinya berikut:

1) Inisiasi stack menjadi kosong.

2) Mencari tahu status stack kosong atau tidak.

3) Mencari tahu stack penuh atau tidak.

4) Mencari panjang stack (jumlah elemen stack).

5) Memasukkan elemen baru pada stack, yaitu top stack jika stack tidak penuh.

6) Jika stack tidak kosong, mengambil elemen teratas(top stack).

Stack pada Struktur Data dapat diilustrasikan dengan 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 kotak.

3

Gambar 1. Ilustrasi Stack 1

Gambar 2. Ilustrasi Stack 2

Dalam prosesnya, untuk memasukkan sebuah data ke dalam stack atau dengan

kata lain ke bagian atas dari sebuah tumpukan digunakan perintah push, dan untuk

memindahkan data dari tempat tersebut digunakan perintah pop. Sedangkan dalam

penyajiannya, stack bisa memakai array atau linked list.

Adapun definisi-definisi seperti :

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.

Definisi 2: Diberikan suatu himpunan yang terurut himpunan sebagai S = {S1,

S2, ......., ST}, T pada anggota S merupakan linier order, sehingga stack dari

himpunan tersebut memiliki informasi sebagai berikut:

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

TOP[S} = ST ............................................................................(1)

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

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

S = {S1, S2, .........., SNOEL} ..................................................(2)

Dari dua definisi tersebut di atas maka suatu stack dapat digambarkan sebagai

berikut :4

1. Suatu stack dalam keadaan kosong akan memiliki informasi NOEL(S) = 0 dan

TOP(S) = undefined.

S

2. Untuk stack yang bukan kosong, maka akan memiliki informasi seperti yang

digambarkan di bawah ini dimana informasi yang ada adalah NOEL(S) = 1 dan

TOP(S) = Merah.

S

3. Untuk stack yang berisi lebih dari n jumlah data maka informasi yang ada pada

stack tersebut berisikan NOEL(S) = 2 (jika berisi 2 data) dan TOP(S) = Biru

seperti ditunjukan pada gambar di bawah ini :

S

Elemen-elemen yang berada dalam stack tersebut di atas, memiliki prinsip

dasar dalam pengoperasiannya yaitu prinsip LIFO (Last In First Out) atau yang masuk

paling belakang akan memiliki prioritas untuk keluar paling depan.

Suatu stack dapat digambarkan sebagai suatu array (larik) berdimensi satu

yang elemen-elemennya berkisar antara 1 sampai n elemen. Dengan demikian jika

5

suatu stack didefinisikan dengan n elemen maka dapat dikatakan jumlah maksimum

dari stack atau NOEL(S) nya adalah n, sehingga penambahan elemen stack yang ke

n+1 tidak diperkenankan atau stack tersebut dalam kondisi overflow.

Hal tersebut juga berlaku untuk stack dengan nilai minimum yaitu NOEL(S)

dari stack dalam kondisi 0, jika dilakukan operasi pengambilan elemen atas stack

tersebut akan mengakibatkan stack tersebut dalam kondisi underflow. Dua kondisi

tersebut merupakan dasar dalam merancang suatu aplikasi pemrograman komputer.

2.2 Pendeklarasian Stack

Stack dapat dideklarasikan sebuah record yang mempunyai sebuah array data

untuk menyimpan elemen stack dan sebuah variabel Top untuk menunjuk stack

elemen atas (top element). Deklarasi selengkapnya sebagai berikut:

Tipestack adalah nama pengenal tipe untuk stack.

Maks_stack merupakan jumlah meksimum elemen stack.

Data adalah array yang digunakan untuk menyimpan data-data stack. Array

yang digunakan disini adalah model array linier. Indeks array dimulai dari s/d

maks_stack.

Tipedata adalah tipe data dari elemen-elemen stack.

Top dipakai untuk menunjuka elemen teratas dari stack. Nilai yang diizinkan

adalah 0 s.d. maks-stack. Jika array diakses dari indeks kecil (1)  ke arah

indeks besar (maks_stack), maka nilai ini akan bertambah 1 bila ada

penambahan elemen; dan berkurang 1 jika ada penghapusan elemen.

S adalah nama variabel yang bertipe stack.

2.3 Skema Traversal Pada Stack

6

Tipestack = record      Data  :  array[1..maks_stack] of tipe data        Top   :  0..maks_stack;     End;Var S  : tipestack;

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. Pemrosesan traversal yaitu mengolah seluruh

elemen tabel secara sistematik. Skemanya adalah :

Contoh penggunaan skema pada pascal:

- Prosedur memasukkan nilai seluruh elemen tabel.

2.4 Skema Search Pada Stack

Skema search adalah algoritma pencarian yang mirip dengan pencarian berkas.

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

pernah dilakukan search. Penggunaan search pada stack tidak dijamin untuk

menemukan solusi optimal untuk masalah pencarian.

2.5 Operasi dan Fungsi Dasar Pada Stack

Dalam penggunaannya suatu stack memiliki beberapa operasi yang dapat

diterapkan seperti membuat stack, penambahan elemen ke dalam stack, menghapusan

elemen dari dalam stack, dan operasi lain yang berhubungan dengan stack tersebut.

Ada empat operasi dasar yang didefinisikan pada stack, yaitu :

7

Procedure ProsesTraversal (Var TI:TabInt);Vari:integer;Begin Inisialisasi; {prosedur persiapan sebelum pemrosesan} For i:=IdxMin to IdxMax do Begin Proses (TI[i]); {proses terhadap elemen saat itu} End; Terminasi; {prosedur aksi setelah pemrosesan selesai}End;

Procedure InputTabInt (Var TI : TabInt);Vari : Integer;Begin For i := IdxMin to IdxMax do Begin Write (‘Elemen ke-‘,i); Readln (TI[i] ); End;End;

1. CREATE (stack)

2. ISEMPTY (stack)

3. PUSH (elemen,stack)

4. POP (stack)

1. Create

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). Operator ini berfungsi untuk membuat sebuah stack

kosong dan didefinisikan bahwa :

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

Algoritma Create(S)

Algoritma ini memuat suatu prosedur untuk membuat stack, yang memberikan

kondisi noel dari stack akan bernilai nol dan top dari stack tersebut belum dapat

didefinisikan, sehingga implementasi dari algoritma create stack adalah:

2. IsEmpty

Operasi ini merupakan operasi untuk mencek isi dari suatu stack dalam

keadaan kosong atau berisi. Operasi ini memiliki 2 (dua) kondisi boolean yaitu :

a. True jika stack tersebut kosong atau dapat dikatakan NOEL(S) = 0.

b. False jika stack tersebut tidak dalam kondisi kosong atau dapat dikatakan

NOEL(S) > 0.

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.

Algoritma IsEmpty(S)

8

Procedure Create(var S : Stack);BeginS.Noel := 0; .End;

Catatan : ISEMPTY(CREATE(S)) = true

Algoritma untuk operasi Isempty memberikan informasi Boolean yaitu kondisi

benar (true) atau salah (False), sehingga pada implementasinya algoritma ini

menggunakan fungsi yang dibuat sendiri. Implementasinya sebagai berikut :

3. Push

Operasi ini merupakan operasi untuk menambahkan satu elemen dengan nilai

E pada puncak suatu stack, sehingga posisi TOP(S) akan bernilai E, penerapan operasi

push pada suatu stack S akan berakibat overflow jika NOEL(S) dari stack tersebut

telah bernilai maksimum. 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).

Algoritma Push(S, E)

Dalam merancang algoritma untuk operasi push dimulai dengan melakukan

pengecekan atas isi dari stack tersebut dalam keadaan penuh atau tidak. Kondisi stack

dalam keadaan maksimum akan mengakibatkan overflow pada stack tersebut

sehingga prosedur error trapping perlu didefinisikan untuk mencegah terjadinya

overflow condition tersebut. Implementasi dari algoritma push tersebut adalah :

4. Pop9

Function IsEmpty(Var S : Stack) : Boolean;BeginIsEmpty

Procedure Push(Var S : Stack; TipeBAru : Eon);BeginIf S.Noel = NoelStack ThenStackerror(1)ElseBeginS.Noel := S.Noel + 1;S.Top[S.Noel] := TipeBaruEnd;End;

Operasi ini berfungsi untuk menghapus satu elemen dari stack S, sehingga

posisi NOEL(S) akan berkurang satu elemen, dan TOP(S) akan berubah. Operasi pop

dapat menyebabkan kondisi underflow jika suatu stack S yang berada dalam kondisi

minimum dikenakan operasi 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

Algoritma Pop(S)

Operasi terakhir dari stack adalah operasi pop yang berfungsi untuk

mengeluarkan isi dari dalam stack. Seperti halnya operasi push, pada operasi pop

penggunaan error trapping dipakai untuk men-cek kondisi underflow yaitu kondisi

stack kosong yang dikenakan operasi pop. Algoritma dari pop ini adalah :

Penggunaan error trapping untuk operasi push dan pop didefinisikan lebih

lanjut dalam algoritma stackerror yang digunakan untuk menentukan kondisi

overflow atau underflow suatu stack. Adapun algoritma dari error trapping ini adalah:

2.6 Deklarasi Stack pada Bahasa Pemrograman (Pascal)

10

Procedure Pop(Var S : Stack; Var NilaiStack : Eon);BeginIf S.Noel = 0 ThenStackError(2)ElseBeginNilaiStack := S.Top[s.Noel];S.Noel := S.Noel -1End;End;

Procedure StackError(TingkatanError : Integer);BeginCase TingkatanError of1 : WriteLn(‘Isi Stack sudah penuh... kondisi overflow’);2 : WriteLn(‘Isi Stack Kosong ... kondisi underflow’)End;End;

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 :

Selanjutnya, untuk keperluan operasi PUSH dan POP harus dibuat suatu

prosedur tersendiri, yaitu :

11

TYPE Stack_Struct = RecordStack:array[1..100] of integer;

TopPtr : integer;End;

VAR S : Stack_Struct;

PROCEDURE PUSH(Eon : integer);BeginIf (S.TopPtr < NoelMax) Then BeginS.TopPtr := S.TopPtr + 1; S.Stack [S.TopPtr] := EonEndElse Overflow_ConditionEnd;

PROCEDURE POP(Eoff : integer);BeginIf (S.TopPtr > 0) Then Begin

Eoff := S.Stack[S.TopPtr];S.TopPtr := S.TopPtr-1EndElse Underflow_Condition

End;

Catatan : Overflow adalah suatu keadaan di mana kita melakukan operasi PUSH

terhadap stack dalam keadaan penuh. Underflow adalah keadaan di mana kita

melakukan operasi POP terhadap stack kosong. Eon adalah elemen yang

akandimasukkan ke dalam stack dan Eoff adalah elemen yang akan dikeluarkan dari

dalam stack.

Tabel 1. Perbandingan Operator dalam stack dan operator yang dibaca

Operator Nilai operator dalam stack Nilai operator yang dibaca

) 0

( 0 5

+,- 2 1

*,/ 4 3

Berdasarkan tabel tersebut suatu operator yang dibaca dan akan dimasukan ke

dalam stack, terlebih dahulu melalui proses perbandingan nilai dengan operator yang

ada di dalam stack sebelumnya.

Dalam arti kata lain jika nilai dari operator yang berada dalam stack lebih

besar dari nilai operator yang dibaca maka operator yang berada di dalam stack akan

dikeluarkan sampai nilai tersebut sama atau lebih kecil. Implementasi dari

algoritmanya dapat dijabarkan dalam bentuk fungsi berikut ini :

Fungsi IsiDlmstack tersebut di atas merupakan fungsi level operator yang

posisinya berada dalam suatu stack, adapun fungsi untuk menentukan level operator

yang dibaca adalah :

12

Function IsiDlmStack(Operator:Char):Integer;BeginCase Operator Of‘(‘ : IsiDlmStack := 0;‘+‘,’-‘ : IsiDlmStack := 2;‘*‘,’/’ : IsiDlmStack := 4;EndEnd;

Function Stackyangdibaca(Operator : Char) : Integer;BeginCase Operator Of‘)‘ : Stackyangbaca := 0;‘+‘,’-‘ : Stackyangbaca := 1;‘*‘,’/’ : Stackyangbaca := 3;‘(‘ : Stackyangbaca := 5EndEnd;

Setelah fungsi pengecekan dilakukan, proses yang perlu dirancang selanjutnya

adalah membentuk suatu prosedur untuk menyimpan operator yang dibaca ke dalam

suatu susunan array yang implementasinya dibuat sebagai berikut :

2.7 Penggunaan/Aplikasi Stack

Suatu perhitungan aritmatika biasanya berhubungan dengan operand dan

operator. Operand merupakan suatu karakter atau elemen yang nilainya dioperasikan

dengan bantuan suatu operator untuik 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.

Suatu ekspresi aritmatika dapat dibedakan dalam tiga bentuk notasi

perhitungan yaitu :

1) Notasi prefix, jika operator ditempatkan sebelum dua operand.

2) Notasi infix, jika operator ditempatkan diantara dua operand.

3) Notasi postfix, jika operator ditempatkan setelah dua operand.

Dalam penggunaannya di kehidupan sehari-hari, notasi infix merupakan notasi

aritmatika yang paling banyak digunakan untuk mengekspresikan suatu perhitungan

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

Berdasarkan teori yang diterangkan tersebut di atas, proses konversi infix

menjadi notasi postfix dalam implementasinya membutuhkan stack pada proses

konversinya, adapun proses tersebut memiliki aturan yang digunakan, yaitu :

1) Jika ditemukan simbol kurung buka “(“, maka operasi push pada stack akan

digunakan untuk menyimpan simbol tersebut ke dalam stack.

13

Procedure SimpanChar(Ch : Char);Var Ekspost : TipeEks;Var Indekspost : TipeIndex);BeginIndekspost :=Indekspost + 1;Ekspost := chEnd;

2) Jika ditemukan simbol kurung buka “)”, operasi pop digunakan untuk

mengeluarkan operator-operator yang berada di dalam stack.

3) Jika terdapat simbol operator, maka operasi yang dilakukan pada stack terbagi

atas:

a. Jika TOP(S) dari stack tersebut kosong atau berisi simbol “(“ maka

operasi push akan digunakan untuk memasukan operator tersebut pada

posisi di TOP(S).

b. Jika operator yang berada dipuncak stack merupakan elemen yang

memiliki tingkat yang sama atau lebih tinggi maka operasi pop

digunakan untuk mengeluarkan operator tersebut diikuti operasi push

untuk menyimpan operator hasil scanning untai.

c. Jika operator yang berada di puncak stack memiliki tingkat yang lebih

rendah dari operator yang discan, maka operator baru akan langsung

dimasukan ke dalam stack dengan operasi push.

Adapun tingkatan operator yang dilacak menurut urutan tingkat adalah:

Tabel 2. Level Operator dalam Stack

Operator Level Operator

** Tinggi

* atau / Menengah

+ atau - Rendah

2.8 Operasi Logika Pada Struktur Data Stack

Seorang ahli matematika “Jan Lukasiewicz“ mengembangkan satu cara

penyusunan ungkapan numeris yang selanjutnya disebut “Notasi Polish“ atau “Notasi

Prefix” yang artinya: operator ditulis sebelum kedua operand yang akan disajikan.

Dalam struktur data yang banyak dipelajari, kita ketahui adanya 3 notasi

operasi yang dilakukan untuk suatu operasi aritmatika, yaitu prefix, infix, dan

postfix.

Sebelum kita kupas mengenai notasi di atas, perlu dipahami terlebih dahulu

indikator yang membentuk terjadinya notasi dalam struktur data. Notasi terbentuk dari

14

operand dan operator. Operand adalah data atau nilai yang membantu dalam proses

sedangkan operator adalah fungsi yang digunakan dalam proses.

Contoh :

A + B * C

2 + 3 * 5

Keterangan : A, B, C, 2, 3, 5 adalah operand , + dan * adalah operator.

Sekarang kita sudah dapat mengetahui indikator yang membentuk suatu notasi.

Selanjutnya kita harus mengetahui level/hirarkhi dari operator seperti:

1. ^ (pangkat).

2. * (kali) atau / (bagi).

3. + (jumlah) atau – (kurang).

Seperti yang telah dibahas di awal, diketahui notasi pada struktur data terdiri atas

3 macam, yaitu:

1. Prefix

Yaitu notasi yang terbentuk atas operator dengan operand, dimana operator

berada didepan operand.

Contoh : 

A + B * C (Infix)

Maka notasi prefix-nya adalah   +A*BC

Pemecahannya :

A  +  B  *  C

Diketahaui ada 3 operand yaitu : A, B, C, dan 2 operator yaitu : +, *.

Proses dimulai  dengan melihat dari hirarkhi operator. Contoh diatas operator

yang tertinggi adalah * kemudian +.

Tanda * diapit oleh dua operand yaitu B dan C yaitu B * C , prefixnya dengan

menggabungkan operand dan memindahkan operator kedepan dari operand, sehingga

fungsi B * C, notasi prefixnya menjadi *BC. Sehingga hasil sementara dari notasi

prefix adalah A + *BC.

Selanjutnya mencari prefix untuk operator yang berikutnya, yaitu +, cara yang

dilakukan sama seperti di atas, operator +, diapit oleh 2 operand, yaitu A dan *BC,

gabungkan operand, sehingga menjadi A*BC, lalu pindahkan operator kedepan

operand, sehingga hasil akhir menjadi + A * B C.  

15

Contoh yang lain:

1.  A + B  – C * D

2     3     1    —–>    hirarkhi level

A + B – * CD   —–>    1

+ AB – * CD     —–>    2

– + AB * CD     —–>    3

2. A * B ^ C – D

2   1    3      —–>    hirarkhi

A * ^ BC – D     —–>    1

* A ^ BC – D     —–>    2

– * A ^ BCD      —–>    3

3. A + ( B – C ) * D

3      1      2   —–> hirarkhi

A + – BC * D    —–>  1 (karena diapit tanda paranthesis atau kurung buka/tutup,( ))

A + * – BCD     —–>   2

+ A * – BCD      —–>  3 

2. Infix

Yaitu notasi yang terbentuk atas operator dengan operand, dimana operator

berada diantara operand. Notasi ini hanya dikenal oleh manusia dan selalu digunakan

dalam perhitungan aritmatika.

Contoh : 

A + B * C

( A + B ) * C

A – ( B + C ) * D ^ E

3. Postfix

Yaitu notasi yang terbentuk atas operator dengan operand, dimana operator

berada dibelakang operand. Notasi ini hanya dikenal oleh processor dan dipahami

dalam ALU. 

16

Contoh :  A + B * C (Infix)

maka notasi postfix-nya adalah   ABC*+

Pemecahannya :

A  +  B  *  C

Diketahaui ada 3 operand yaitu : A, B, C, dan 2 operator yaitu : +, *. Proses

dimulai  dengan melihat dari hirarkhi operator. Contoh diatas operator yang tertinggi

adalah * kemudian +.

Tanda * diapit oleh dua operand yaitu B dan C yaitu B * C ,

Postfixnya dengan menggabungkan operand B dan C menjadi BC lalu

memindahkan operator ke belakang operand C, sehingga fungsi B * C, notasi

postfixnya menjadi BC*.

Sehingga hasil sementara dari notasi postfix adalah: A + BC*

Selanjutnya mencari postfix untuk operator yang berikutnya, yaitu +, cara

yang dilakukan sama seperti di atas, operator +, diapit oleh 2 operand, yaitu A dan

BC*, gabungkan operand tersebut, sehingga menjadi ABC*, lalu pindahkan operator

+ ke belakang operand ABC*, sehingga hasil akhir menjadi : ABC*+

Contoh yang lain:

1.  A + B  – C * D

2     3     1    —–>    hirarkhi level

A + B – CD *   —–>    1

AB + – * CD    —–>    2

AB + * CD –    —–>    3

2. A * B ^ C – D

2   1    3      —–>    hirarkhi

A * BC ^ – D    —–>    1

ABC ^ * – D     —–>    2

ABC ^ * D –     —–>    3

3.  A + ( B – C ) * D

3      1      2   —–> hirarkhi

A + BC – * D    —–>  1 (karena diapit tanda paranthesis atau kurung buka/tutup,( ) )

A + BC – D *    —–>   2

ABC – D * +     —–>  3 

17

Contoh lain:

Notasi Infix-Prefix

Cara penyusunan ungkapan yaitu dengan menggunakan notasi infix, yang

artinya operator ditulis diantara 2 operator. Jan Lukasiewiccz mengembangkan suatu

cara penyusunan ungkapan numeris yang disebut prefix, yang artinya operator ditulis

sebelum kedua operand yang akan disajikan.

Contoh :

Proses konversi

dari infix ke prefix :

= ( A + B ) * ( C – D )

= [ + A B ] * [– C D ]

= * [ + A B ] [– C D ]

= * + A B – C D

Notasi Infix-Postfix

Cara penyusunan ungkapan yaitu dengan menggunakan notasi postfix, yang

artinya operator ditulis sesudah operand.

Contoh :

Proses konversi dari infix ke postfix :

= ( 6 – 2 ) * ( 5 + 4 )

= [ 6 2 – ] * [ 5 4 + ]

= [ 6 2 – ] [ 5 4 + ] *

= 6 2 – 5 4 + *

18

2.9 Contoh Aplikasi Stack Pada Pemrograman Pascal

1. Program Pascal Dengan Operasi Stack Pada Nilai

Program Nilai_Stack;uses wincrt;const MaxElemen=5;type Tumpukan =recordisi:array[1..MaxElemen] of integer;atas: 0..MaxElemenend;

type isi=array[0..maxelemen] of integer;const isilama1:isi=(3,7,2,6,4,8);isibaru1:isi=(4,8,3,6,5,1);varNilailama,Nilaibaru:isi;T:tumpukan;

{———————————————————————}Procedure Ganti_NilaiStack(T:tumpukan;Nilailama,Nilaibaru:isi);varpenuh,habis: boolean;x,i:integer;

{———————————————————————}procedure push( var T:tumpukan; var penuh:boolean;x:integer);beginif T.atas = maxElemen then penuh:=trueelsebeginpenuh :=false;T.isi[T.atas]:=x;T.atas:=T.atas+1;end;end;

{———————————————————————}procedure pop(var T:tumpukan;var habis:boolean; var x:integer);beginif T.atas =0 then habis:=trueelsebeginhabis:=false;T.atas:=T.atas-1;x:=T.isi[T.atas];end;end;

{———————————————————————}beginclrscr;write('Nilai Lama Sebelum Masuk Tumpukan : ');for i:=0 to maxelemen dowrite(isilama1[i]);writeln;write('Nilai Baru Sebelum Masuk Tumpukan : ');

19

for i:=0 to maxelemen dowrite(isibaru1[i]);writeln;penuh:=false;while penuh=false dobeginpush(T,penuh,Nilailama[T.atas]);end;write('Isi Tumpukan Lama : ');while T.atas<>0 dobeginpop(T,habis,x);write(x);end;writeln;penuh:=false;while penuh=false dobeginpush(T,penuh,Nilaibaru[T.atas]);end;write('Isi Tumpukan Baru : ');while T.atas<>0 dobeginpop(T,habis,x);write(x);end;end;

{———————————————————————}beginNilailama:=isilama1;Nilaibaru:=isibaru1;Ganti_NilaiStack(T,Nilailama,Nilaibaru);readkey;end.

Output Program:

20

2. Program Pascal Membalik Sebuah Kalimat

Program Membalik_Kalimat;Uses wincrt;Const Elemen = 255;Type S255 = String[Elemen];

Tumpukan = record isi : s255; atas : 0..elemen

end;Var

T : Tumpukan;I : Integer;Kalimat : S255;

Procedure Awalan(Var T : Tumpukan);Begin

T.Atas := 0End;Procedure PUSH (Var T : Tumpukan; X : char);Begin

T.Atas := T.Atas + 1;T.Isi[T.Atas] := X

End;Function POP (Var T : Tumpukan) : char;Begin

POP := T.Isi[T.Atas];T.Atas := T.Atas - 1;

End;

{Program Utama}Begin

clrscr;Awalan(T);write ('Masukan sembarang kalimat : ');ReadLn (Kalimat);WriteLn;

{ mempush kalimat ke dalam tumpukan}For I := 1 to length(Kalimat) do PUSH(T, Kalimat[I]);

{mempop isi tumpukan sehingga diperoleh kalimat yang dibaca terbalik}For I := 1 to length(Kalimat) do write(POP(T));WriteLn;

End.

Output Program :

21

3. Program Pascal Membuat animasi STACK

Program AnimasiStack;Uses wincrt;const max = 10;vartop,i : byte;pil,tem,E : char;stack : array [1..max] of char;

procedure pushanim; begin for i :=1 to 18 do begin gotoxy(23+i,7); write(tem); {Delay(30);} gotoxy(23,7); clreol; end; for i:=1 to 14-top do begin {delay(30);} gotoxy(41,6+i); write(' '); gotoxy(41,7+i); write(tem); end; end;

procedure popanim(tem:char); begin for i:=1 to 14-top do begin {delay(30);} gotoxy(41,22-i-top); write(' '); gotoxy(41,21-i-top); write(tem); end; for i:=1 to 19 do begin gotoxy(40+i,7); write(tem); {delay(30);} gotoxy(16,7); clreol; end; end;

procedure push(e:char); begin inc(top); stack[top] :=e; pushanim; end;

procedure pop(e:char); begin if top<> 0 then begin E:=stack[top];popanim(e); dec(top); end else begin gotoxy(1,7); write('stack telah kosong'); readkey; gotoxy(1,7); clreol; end;

22

end;

begin clrscr; writeln('ANIMASI STACK'); writeln('1. PUSH'); writeln('2. POP'); writeln('3. QUIT'); writeln('Pilihan anda[1/2/3] = '); gotoxy(37,10);write('\ /'); for i:=1 to 11 do begin gotoxy(38,10+i); if i=11 then write('|_____|')else write ('| |'); end; top := 0; repeat gotoxy(23,5);clreol; pil := readkey;write(pil); if pil ='1' then begin if top<> max then begin gotoxy(1,7);write('Masukkan satu Huruf = '); tem := readkey;write(tem); push(tem); gotoxy(1,7);clreol; end else begin gotoxy(1,7);write('Stack sudah penuh'); readkey; gotoxy(1,7);clreol; end; end else if pil='2' then pop(tem); until pil='3'; donewincrt; end.

Output Program:

23

4. Program Pascal Nilai Ganjil-Genap

program tigastack;uses wincrt;type tumpukan = record isi : array[1..25] of byte; top : 0..25; end;var t1,t2,t3 : tumpukan; x,n,angka,bantu : byte;procedure tumpuk(var t : tumpukan;angka : byte);begin inc(t.top); t.isi[t.top] := angka;end;

procedure keluarkan(var t : tumpukan;var angka : byte);begin angka := t.isi[t.top]; dec(t.top);end;

{procedure atur(var t : tumpukan; angka : byte);begin repeat keluarkan(t,bantu); tumpuk(t3,bantu); until (t.isi[t.top] > angka) or (t.top = 0); tumpuk(t,angka); repeat keluarkan(t3,bantu); tumpuk(t,bantu); until t3.top = 0;end; }

24

procedure cetak(t : tumpukan);begin repeat keluarkan(t,angka); write(angka:3); until t.top = 0;end;begin t1.top := 0; t2.top := 0; t3.top := 0; repeat clrscr; writeln('PROGRAM APLIKASI STACK(tumpukan data)':50); writeln; write('Banyaknya angka acak ?? [5 sampai 25] : ');readln(n); until n in[5..25]; for x := 1 to n do begin write('Angka ke ',x,' : ');readln(angka); if angka mod 2 = 0 then tumpuk(t1,angka) else tumpuk(t2,angka); end; repeat keluarkan(t1,angka); if t3.top = 0 then tumpuk(t3,angka) else begin if angka > t3.isi[t3.top] then tumpuk(t3,angka) else begin repeat keluarkan(t3,bantu); tumpuk(t2,bantu); until (t3.isi[t3.top] < angka) or (t3.top = 0); tumpuk(t3,angka); repeat keluarkan(t2,bantu); tumpuk(t3,bantu); until t2.isi[t2.top] mod 2 = 1; end; end; until t1.top=0; repeat keluarkan(t3,angka); tumpuk(t1,angka); until t3.top = 0; writeln; write('Angka genap = '); if t1.top = 0 then write('Tidak ada angka genap !') else cetak(t1); writeln; write('Angka ganjil = '); if t2.top = 0 then

25

write('Tidak ada angka ganjil !') else cetak(t2); readkey;

donewincrt;end.

Output Program :

BAB III

PENUTUP

4.1 Kesimpulan

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.

Operasi-operasi pada Stack :

1) 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).

2) IsEmpty(Stack)

26

Operasi ini merupakan operasi untuk mencek isi dari suatu stack dalam

keadaan kosong atau berisi.

Operasi ini memiliki 2 (dua) kondisi boolean yaitu :

1) True jika stack tersebut kosong atau dapat dikatakan NOEL(S) = 0.

2) False jika stack tersebut tidak dalam kondisi kosong atau dapat

dikatakan NOEL(S) > 0.

3) 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.

4) Pop(Stack)

Operasi ini berfungsi untuk menghapus satu elemen dari stack S, sehingga

posisi NOEL(S) akan berkurang satu elemen, dan TOP(S) akan berubah.

Operasi pop dapat menyebabkan kondisi underflow jika suatu stack S yang

berada dalam kondisi minimum dikenakan operasi pop.

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

27

DAFTAR PUSTAKA

M. Shalahuddin, Rosa A.S. 2010. Modul Pembelajaran Struktur Data. Penerbit:

Modula. Bandung.

Marcus, Zakaria, Teddy. Prijono, Agus. Konsep dan Implementasi Struktur Data.

Penerbit: Informatika. Bandung.

Dewa. 2009. Struktur Data – Pengertian Stack. http://dewa18.wordpress.com/

2009/10/28/struktur-data-pengertian-stack/. Diakses pada 30 Mei

2013, Pukul 10.23 WIB.

Hastuti, Nor Fitriana. 2009. Program Implementasi Stack dalam Pascal.

http://terminaltechno.blog.uns.ac.id/2009/11/07/program-

implementasi-stack-dalam-pascal/. Diakses pada 30 Mei2013, Pukul

10.37 WIB.

Hendradhy, Oke. 2008. Aplikasi Stack Pada Struktur Data Untuk Mengkonversikan

Notasi Infix Menjadi Notasi Postfix. http://mugi.or.id/blogs/oke/

archive/2008/08/27/aplikasi-stack-pada-struktur-data-untuk-

mengkonversikan-notasi-infix-menjadi-notasi-postfix.aspx. Diakses

pada 30 Mei 2013, Pukul 11.09 WIB.

28

29