Referensi Stack (Tumpukan)_Struktur Data

A. Pengertian Stack (Tumpukan)
Stack (Tumpukan) adalah kumpulan elemen-elemen data yang disimpan dalam satu lajur linear. Kumpulan elemen-elemen data hanya boleh diakses pada satu lokasi saja yaitu posisi ATAS (TOP) tumpukan. stack atau tumpukan merupakan sebuah koleksi objek yang menggunakan prinsip LIFO (Last In First Out), yaitu data yang terakhir kali dimasukkan akan pertama kali keluar dari tumpukan tersebut. Tumpukan digunakan dalam algoritma pengimbas (parsing), algoritma penilaian (evaluation) dan algoritma penjajahan balik (backtrack). Elemen-elemen di dalam tumpukan dapat bertipe integer, real, record dalam bentuk sederhana atau terstruktur.           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). stack termasuk dalam linear list karena stack merupakan suatu bentuk dari linear list dimana operasi penyisipan dan penghapusan elemen-elemennya hanya dapat dilakukan pada satu sisi saja yaitu pada saat posisi akhir list.posisi ini disebut juga sebagai posisi puncak atau (TOP)
Stack dalam kondisi hampa dapat kita ketahui dengan menggunakan ESMPTY(S). yang hasilnya merupakan type data Boolean,jika ESMPTY(S)=True berarti stack dalam kondisi hampa atau kosong atau tidak mempunyai elemen dapat juga diketahui jika NOEL(S)=0. Sebaliknya jika False dapat dipastikan stack dalam keadaan tidak kosong NOEL(S)>0. Penghapusan elemen di stack dapat kita lakukan dengan operasi POP(S) dan penghapusannya dilakukan saat elemen berada dipuncak stack

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

1. Push : digunakan untuk menembah item pada Stack pada Tumpukan paling atas.
2. Pop : digunakan untuk mengambil item pada Stack pada Tumpukan paling atas.
3. Clear : digunakan untuk mengosongkan Stack.
4. Create Stack : membuat Tumpukan baru S, dengan jumlah elemen kosong.
5. MakeNull : mengosongkan Tumpukan S, jika ada elemen maka semua elemen dihapus.
6. IsEmpty : fungsi yang digunakan untuk mengecek apakah Stack sudah kosong.
7. Isfull : fungsi yang digunakan untuk mengecek apakah Stack sudah penuh.
8. InsertFirst () biasa disebut Push (input E : typeelmt, input/output data : stack): menambahkan sebuah elemen ke tumpukan
9. DeleteFirst () biasa disebut Pop (output E : typeelmt, input/output data : stack ) : menghapus sebuah elemen tumpukan
10. IsEmpty () : mengecek apakah stack kosong atau ada elemennya
11. IsFull () : mengecek apakah stack telah penuh atau belum
12. Clear () : menghapus semua data
13. Peek () : melihat data TOP

C. Macam – macam Stack

1. Stack dengan Array

Sesuai dengan sifat stack, pengambilan atau penghapusan elemen dalam stack harus dimulai dari elemen teratas.

2. Double Stack dengan Array

Metode ini adalah teknik khusus yang dikembangkan untuk menghemat pemakaian memori dalam pembuatan dua stack dengan array. Intinya adalah penggunaan hanya sebuah array untuk menampung dua stack.
D. Pemanfaatan tumpukan:

• Perhitungan ekspresi aritmatika (posfix)
• algoritma backtraking (runut balik)
• algoritma rekursif

E. Prinsip Kerja Stack

Prinsip kerja stack adalah LIFO (Last In Fist Out).atau disebut terakhir masuk pertama yang keluar. Dimana data terakhir dimasukkan adalah data yang akan pertama kali dikeluarkan.

Sedangkan FIFO (Fist In Fist Out) pertama masuk  pertama keluar, atau bisa diartikan pertama datang pertama dilayani ,apa yang datang disamping menunggu sampai yang pertama selesai. Sehingga perbedaannya sudah Nampak jelas antara LIFO dengan FIFO. Perbedaan itu tidak dalam data tetapi dalam mengakses konten

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
Algoritma IsEmpty(S) 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 : Function IsEmpty(Var S : Stack) : Boolean; Begin IsEmpty Procedure Push(Var S : Stack; TipeBAru : Eon); Begin If S.Noel = NoelStack Then Stackerror(1) Else Begin S.Noel := S.Noel + 1; S.Top[S.Noel] := TipeBaru End; End;

Deklarasi Stack pada Bahasa Pemrograman (Pascal) 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 : TYPE Stack_Struct = Record Stack:array[1..100] of integer; TopPtr : integer; End; VAR S : Stack_Struct; PROCEDURE PUSH(Eon : integer); Begin If (S.TopPtr < NoelMax) Then Begin S.TopPtr := S.TopPtr + 1; S.Stack [S.TopPtr] := Eon End Else Overflow_Condition End; PROCEDURE POP(Eoff : integer); Begin If (S.TopPtr > 0) Then Begin Eoff := S.Stack[S.TopPtr]; S.TopPtr := S.TopPtr-1 End Else Underflow_Condition End;

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 : Function IsiDlmStack(Operator:Char):Integer; Begin Case Operator Of ‘(‘ : IsiDlmStack := 0; ‘+‘,’-‘ : IsiDlmStack := 2; ‘*‘,’/’ : IsiDlmStack := 4; End End; Function Stackyangdibaca(Operator : Char) : Integer; Begin Case Operator Of ‘)‘ : Stackyangbaca := 0; ‘+‘,’-‘ : Stackyangbaca := 1; ‘*‘,’/’ : Stackyangbaca := 3; ‘(‘ : Stackyangbaca := 5 End End;

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 memilikiaturan yang digunakan, yaitu : 
1) Jika ditemukan simbol kurung buka ―(―, maka operasi push pada stack akan digunakan untuk menyimpan simbol tersebut ke dalam stack. Procedure SimpanChar(Ch : Char); Var Ekspost : TipeEks; Var Indekspost : TipeIndex); Begin Indekspost :=Indekspost + 1; Ekspost := ch End; 
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.8Operasi 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 operand dan operator.Operand adalah data atau nilai yang membantu dalam proses sedangkan operator adalah fungsi yang digunakan dalam proses.

Contoh Aplikasi Stack Pada Pemrograman Pascal 1. Program Pascal Dengan Operasi Stack Pada Nilai Program Nilai_Stack; uses wincrt; const MaxElemen=5; type Tumpukan =record isi:array[1..MaxElemen] of integer; atas: 0..MaxElemen end; type isi=array[0..maxelemen] of integer; const isilama1:isi=(3,7,2,6,4,8); isibaru1:isi=(4,8,3,6,5,1); var Nilailama,Nilaibaru:isi; T:tumpukan; {———————————————————————} Procedure Ganti_NilaiStack(T:tumpukan;Nilailama,Nilaibaru:isi); var penuh,habis: boolean; x,i:integer; {———————————————————————} procedure push( var T:tumpukan; var penuh:boolean;x:integer); begin if T.atas = maxElemen then penuh:=true else begin penuh :=false; T.isi[T.atas]:=x; T.atas:=T.atas+1; end; end; {———————————————————————} procedure pop(var T:tumpukan;var habis:boolean; var x:integer); begin if T.atas =0 then habis:=true else begin habis:=false; T.atas:=T.atas-1; x:=T.isi[T.atas]; end; end; {———————————————————————} begin clrscr; write('Nilai Lama Sebelum Masuk Tumpukan : '); for i:=0 to maxelemen do write(isilama1[i]); writeln; write('Nilai Baru Sebelum Masuk Tumpukan : '); for i:=0 to maxelemen do write(isibaru1[i]); 
writeln; penuh:=false; while penuh=false do begin push(T,penuh,Nilailama[T.atas]); end; write('Isi Tumpukan Lama : '); while T.atas<>0 do begin pop(T,habis,x); write(x); end; writeln;penuh:=false; while penuh=false do begin push(T,penuh,Nilaibaru[T.atas]); end; write('Isi Tumpukan Baru : '); while T.atas<>0 do begin pop(T,habis,x); write(x); end; end; {———————————————————————} begin Nilailama:=isilama1;Nilaibaru:=isibaru1; Ganti_NilaiStack(T,Nilailama,Nilaibaru); readkey; end. Output Program:

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 := 0 End; 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 :

Program Pascal Membuat animasi STACK Program AnimasiStack; Uses wincrt; const max = 10; var top,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; 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:

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; } 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 write('Tidak ada angka ganjil !') else cetak(t2); readkey; donewincrt; end. Output Program : 

* 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) 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.
Penggunaan Stack Dalam Kehidupan sehari- hari Misalnya:
• Setumpuk koran, dimana koran yang paling terakhir ditambahkan dan ditaruh di atas tumpukan yang dapat dilihat.
• Tumpukan kotak rokok, koin, buku, dll