STACK adalah salah satu list linear dalam struktur data yang digunakan untuk menyimpan dan mengambil data dengan konsep LIFO (Last In First Out). Dimana dalam stack ini kumpulan data yang masuk diletakkan di atas data yang lain. Dan berdasar konsep LIFO maka data yang terakhir kali disimpan dalam stack akan menjadi data yang pertama kali diambil. 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.
Stack secara umum :
S = [S1, S2, ..., SNOEL]
bahwa : SI berada di atas elemen SJ, untuk I > J
SI akan dikeluarkan lebih dulu dari elemen di bawahnya.
Contoh stack : Tumpukan baki dalam cafetaria
Empat operasi dasar yang berlaku pada stack :
1. CREATE(stack)
2. ISEMPTY(stack)
3. PUSH(elemen, stack)
4. POP(stack)
v CREATE
adalah operator yang menunjukkan suatu stack kosong dengan nama S.
Jadi : NOEL(CREATE(S)) = 0
TOP(CREATE(S)) adalah TIDAK TERDEFINISI.
v ISEMPTY
adalah operator yang menentukan apakah stack S kosong.
Operandnya terdiri dari type data stack. Hasilnya merupakan type data Boolean.
ISEMPTY(S) = True. Jika S hampa, yakni bila NOEL(S) = 0.
v PUSH
adalah operator yang menambahkan elemen E pada puncak stack S. Hasilnya merupakan stack yang lebih besar.
PUSH(E,S). E ditempatkan sebagai TOP(S).
v POP(stack)
adalah operator yang menghapus sebuah elemen dari puncak stack S. Hasilnya merupakan stack yang lebih kecil.
· POP(S) mengurangi NOEL(S)
· POP(CREATE(S)) ® kondisi error
· POP(PUSH(E,S)) = S
Penerapan stack :
Stack digunakan untuk menuliskan ungkapan menggunakan notasi tertentu (Notasi Polish). Biasanya ungkapan yang digunakan adalah ungkapan numeris. Sebagai contoh ungkapan (A + B)*(C – D) apabila ditulis dengan menggunakan notasi Polish menjadi * + A B – C D.
APLIKASI STACK
1. Penjodohan Tanda Kurung/Matching Parantheses
ALGORITMA
a. Amati barisan elemen dari kiri ke kanan
b. bila bertemu ‘(‘, maka ‘(‘ di push ke dalam stack.
c. bila bertemu ‘)’, maka periksa stack hampa atau tidak.
d. bila hampa ® ada ‘)’ dan tidak ada ‘(‘ (error)
e. bila tidak hampa ® ada sepasang ‘(‘ & ‘)’ & POP elemen keluar
APLIKASI STACK
· Prefix adalah metode penulisan dengan meletakkan operator di depan operand dan tanpa menuliskan tanda kurung.
· Contoh pemakaian prefix adalah +AB, – +ABC, * + AB – CD.
· Infix adalah cara penulisan ungkapan dengan meletakkan operator di antara dua operand dalam hal ini pemakaian tanda kurung sangat menentukan hasil operasi.
· Contoh pemakaian infix adalah A+B, A+B-C, (A+B)*(C-D).
· Postfix adalah metode penulisan dengan menuliskan operator setelah operand dan tanpa menuliskan tanda kurung.
· Contoh penulisan sufix adalah AB + , AB + C – , AB + CD -*.
· Salah satu contoh proses pengubahan infix menjadi postfix dari karakter:
( A + B ) / (( C – D ) * E ^ F)
Karakter
dibaca
|
Isi
Stack
|
Karakter tercetak
|
Postfix
yang terbentuk
|
(
|
(
| ||
A
|
(
|
A
|
A
|
+
|
( +
| ||
B
|
B
|
A B
| |
)
|
+
|
A B +
| |
/
|
/
| ||
(
|
/ (
| ||
(
|
/ ( (
| ||
C
|
/ ( (
|
C
|
A B + C
|
-
|
/ ( ( -
| ||
D
|
/ ( ( -
|
D
|
A B + C D
|
)
|
/ (
|
-
|
A B + C D -
|
*
|
/ ( *
| ||
E
|
/ ( *
|
E
|
A B + C D – E
|
^
|
/ ( * ^
| ||
F
|
/ ( * ^
|
F
|
A B + C D – E F
|
)
|
/ ( *
|
^
|
A B + C D – E F ^
|
/ (
|
*
|
A B + C D – E F ^ *
| |
/
| |||
/
|
A B + C D – E F ^ * /
|
