Stack adalah bentuk khusus dari list linear. Pada stack penghapusan dan penambahan elemennya hanya pada satu posisi yaitu pada posisi terakhir dari list. Posisi ini disebut sebagai posisi puncak dari list linear ini atau sering disebut sebagai TOP(s). Contohnya : S = ( A, B, C, D, E) maka TOP(S) adalah E dan untuk menentukan banyaknya jumlah tumpukan yang ada biasanya disebut sebagai NOEL(S), sehingga nilai dari NOEL(S) adalah 5. Seperti halnya dalam link list dalam stack juga ada operasi penambahan dan penghapusan. Untuk penambahan element dinamakan PUSH(e), dan untuk penghapusan disebut sebagai POP(S). Didalam stack terdapat beberapa perintah diantaranya :
Create
Operator ini menyebabkan Stack menjadi suatu Stack hampa. Jika terdapat operasi NOEL(CREATE(S)) hasilnya adalah 0 dan TOP(CREATE(S)) hasilnya adalah tidak terdefinisi.
ISEMPTY
Operator ini berfungsi untuk memeriksa apakah Stack S hampa atau tidak. Keluaran dari operator ini bertipe boolean. Jika NOEL(S) = 0 maka ISEMPTY(S) = True dan jika NOEL(S) > 0 maka ISEMPTY(S) = False. Kita menerapkan ISEMPTY sebagai sebuah Function
POP
Operator ini digunakan jika kita ingin menghapus elemen terakhir dari stack. Di lakukan jika stack tidak kosong (ISEMPTY = False).
PUSH
Operator ini digunakan untuk menambahkan elemen pada Stack elemen baru ditempatkan pada posisi paling atas / TOP(S).
Aturan di postfix menggunakan stack :
- Jika simbol adalah “(“ (kurung buka), maka ia kita PUSH ke dalam Stack.
- Jika simbol adalah “)” (kurung tutup), maka POP dari Stack elemen-elemen Stack sampai pertama kali kita POP simbol “(“. Semua elemen stack yang di POP tersebut merupakan output, kecuali “(“ tadi.
- Jika simbol adalah sebuah Operand, tanpa melakukan perubahan elemen stack, operand tersebut langsung merupakan output.
- Jika simbol adalah sebuah operatot, maka jika TOP stack adalah operator dengan level lebih tinggi atau sama, maka elemen TOP kita POP, sekaligus keluar sebagai output, dilanjutkan proses seperti ini sampai TOP merupakan “(“ atau operator dengan level yang lebih rendah. Kalau hal ini terjadi, operator (yang diamati) kita PUSH kedalam stack.
Dapat dicatat bahwa terdapat 3 level operator yakni :
Level tertinggi :Pemangkatan (^)
Level menengah :Perkalian (*) dan Pembagian (/)
Level terendah :Penjumlahan (+) dan Pengurangan (-).
APLIKASI STACK
Notasi Postfix
Contoh :
Notasi Infix : ((A+B) * C/D+E^F)/G;
Simbol yang diamati
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
16
|
17
|
18
|
(
|
(
|
A
|
+
|
B
|
)
|
*
|
C
|
/
|
D
|
+
|
E
|
^
|
F
|
)
|
/
|
G
|
;
| |
TOP dari
STACK
|
(
|
(
(
|
(
(
|
+
(
(
|
+
(
(
|
(
|
*
(
|
*
(
|
/
(
|
/
(
|
+
(
|
+
(
|
^
+
(
|
^
+
(
|
/
|
/
| ||
OUTPUT
|
A
|
B
|
+
|
C
|
*
|
D
|
/
|
E
|
F
|
^+
|
G
|
/
|
Soal :
1. A * B - (C + D) -(E - F) + F/H ^ I;
2. ((B * C) + C/D ^ F) + G;
3. A ^ B * C - D + E/F / (G + H);
Postingan
0 komentar:
Posting Komentar