Pengertian Stack atau Tumpukan dan Aplikasinya

 Nah Gan, kali ini kita bakalan ngobrolin tentang Stack atau tumpukan. Belum tahu kan tentang istilah ini? Simak di bawah ini

Stack merupakan salah satu spesial linked list, yang mempunyai karakteristik sebagai berikut :

1.  Operasi penyisipan (inserting) dan penghapusan (deleting) hanya dapat dilakukan pada elemen PUNCAK (TOP STACK), sehingga elemen yang pertama masuk akan menjadi elemen terakhir yang dikeluarkan dari stack (First In Last Out

/FILO),  atau  sebaliknya  elemen  yang  terakhir  masuk  akan  menjadi  elemen pertama yang dikeluarkan dari stack (Last In First Out / LIFO).

2.  Hanya terdapat 2 (dua) operasi pada STACK, yaitu penyisipan/inserting (PUSH)

dan penghapusan/Pengambilan/Deleting (POP).

Representasi Stack Pada List Berkait

Bila data yang disisipkan (PUSH) ke stack berturut-turut adalah Kadir, Tarsan, Eko, Basuki, dan Gogon, maka representasi data di memori adalah sebagai berikut :

Model Logika

Alm Info Next 1 Eko 4 2 Basuki 1 3 4 Tarsan 7 5 6 Gogon 2 7 Kadir 0

Operasi Dasar Pada Stack 

a. Operasi Inserting (PUSH) Algoritma operasi inserting / PUSH

Temp->Info = X; Temp->Next = TOP; TOP = Temp;

PUSH(TOP, X) Malloc(Temp);

Return;

b.Operasi Deleting (POP) Algoritma operasi Deleting / POP

POP(TOP, X);

If (TOP == NULL) Write(‘Stack kosong’)

Else

X   = TOP->Info; P   = TOP;

TOP = TOP->Next;

Free(P); Endif;

Return;

APLIKASI STACK

1.  Pemanggilan Sub Program

Ketika dijumpai instruksi RETURN, komputer harus mengetahui alamat instruksi mana yang harus dilaksanakan berikutnya. Untuk mengetahui alamat instruksi yang harus dilaksanakan berikutnya, pada saat ditemukan perintah CALL (sub program: procedure atau function) komputer akan menyimpan alamat instruksi setelah CALL sebagai elemen TOP stack, dan ketika ditemukan instruksi RETURN,  maka  komputer  akan  mengambil  elemen  TOP  dari  stack  sebagai alamat instruksi yang harus dikerjakan berikutnya, dan harga tersebut dihapus dari stack.

2.  Mengavakuasi Ekspresi Aritmatika

Cara kita menuliskan ekspresi aritmatik adalah dalam notasi INFIX yaitu notasi yang meletakkan OPERATOR diantara dua OPERAND. Kompiler akan mengubah notasi tersebut ke dalam notasi POSTFIX yaitu notasi yang meletakkan OPERATOR setelah OPERAND.

Contoh :

Notasi Infix      : A + B * C Notasi Postfix  : ABC * +

Keunggulan notasi POSTFIX adalah:

a)  tidak diperlukan tanda kurung ( )

b) prioritas OPERATOR tidak lagi penting

c)  proses penghitungan dapat diselesaikan dalam sekali scan/pembacaan  dari kiri ke kanan.

Cara mengeksekusi notasi aritmatik (notasi POSTFIX) adalah: notasi dibaca dari kiri  ke  kanan,  jika  ditemukan  OPERAND,  disimpan  ke  dalam  STACK.  Jika ditemukan  OPERATOR,  kompiler  akan  mengoperasikan  OPERATOR  tersebut dengan mengambil dua OPERAND dari stack dan hasilnya akan disimpan kembali ke dalam stack.

3. Mengubah Notasi Infix Menjadi Postfix

Algoritma mengubah notasi INFIX ke Notasi POSTFIX

1.  Baca ekspresi infix (E)

2.  Tentukan panjang E, misalkan N

3.  Tentukan derajat masing operator operator

Contoh : * dan /  = 2, + dan - = 1, kurung buka ‘ ( ‘ = 0

4.  Untuk I = 1 s/d N kerjakan a. X = E[I]

b. Jika X adalah:

ƒ  Operand    :  Langsung tuliskan sebagai output

ƒ  ‘(‘              :  PUSH ke STACK

ƒ  ‘)’              :  POP dan tulis (ke output) semua isi STACK sampai

‘(‘ pasangannya. Tanda ‘(‘ juga diPOP tetapi tidak ditulis ke output

ƒ  Operator   :  Jika stack kosong atau derajat X lebih tinggi dari elemen top stack, PUSH X ke stack.

Jika tidak, POP top stack dan tulis ke output kemudian lakukan pembandingan X dengan top stack

yang baru. Jika memenuhi syarat PUSH X ke stack.

5.  Jika akhir ekspresi telah tercapai dan stack belum kosong, POP isi stack dan tulis hasilnya.

Contoh Kasus

Ubah notasi INFIX berikut ke dalam notasi POSTFIX

E = A + B * C

Step	Simbol	Stack	Output
0	#	#	#
1	A	#	A
2	+	+	A
3	B	+	A B
4	*	+ *	A B
5	C	+ *	A B C
6	↵	#	A B C * +

Notasi POSTFIX-nya adalah ABC*+

Latihan:

Ubah notasi INFIX berikut ke dalam notasi POSTFIX

a.  E = A / B + C * D – F

b.  E = A / (B + C) * (D – F)

c.  E = (A + B) / (C – D) * F

4. Reversing String (Membalik Urutan String)

Untuk  membalik  urutan  string  dapat  dilakukan  dengan  membaca  masing-

masing karakter mulai karakter pertama sampai karakter terakhir dan memasukkanya ke stack (PUSH ke stack). Setelah semua karakter masuk, keluarkan (POP) semua isi stack dan cetak hasilnya.

Algoritma Reversing String

Reversing(StringAwal, StringHasil) Panjang = Length(StringAwal);

I = 1; StringHasil = ‘’; While I <= Panjang do

X = StringAwal[I];

PUSH(TOP, X);

I++; Ewhile I = 1;

While (I <= Panjang) do

POP(TOP, X);

StringHasil = StringHasil + X;

I++; Ewhile

{

Jika ingin menampilkan hasilnya

Cout << ‘String awal adalah : ‘ << StringAwal; Cout << ‘String hasil adalah : ‘ << StringHasil;

}

Return

5. Konversi Bilangan

Konversi bilangan desimal dapat dilakukan dengan membagi bilangan tersebut dengan DIV basis bilangan yang diinginkan, dan memasukkan sisa baginya ke stack. Jika bilangan asal sudah sama dengan 0 (nol), keluarkan isi stack dan tulis hasilnya.

Contoh kasus: konversi bilangan desimal ke biner

13(10) = ……..(2)

Cara menghitung

Step	Proses	Hasil	Sisa
1	13 DIV 2	6	1
2	6  DIV 2	3	0
3	3  DIV 2	1	1
4	1 DIV 2	0	1

Hasilnya dibaca dari bawah ke atas : 1 1 0 1

KonversiDesimal2Biner(IntNumber) While IntNumber > 0 do

Sisa = IntNumber MOD 2

Push(Top, Sisa)

IntNumber = IntNumber DIV 2

Ewhile

While Top <> NUUL do

Pop(Top, X); Cout << X;

Ewhile

Return