Stack ( Tumpukan )

Dalam ilmu komputer, stack atau tumpukan merupakan sebuah koleksi objek yang menggunakan prinsip LIFO (Last In First Out), yaitu data yang terakhr kali dimasukkan akan pertama kali keluar dari stack tersebut. Stack dapat diimplementasikan sebagai representasi berkait atau kontigu (dengan tabel fix).

Secara sederhana stack di artikan sebagai :
•sebagai tumpukan dari benda
•sekumpulan data yang seolah-olah diletakkan di atas data yang lain
•koleksi dari objek-objek homogen

Ciri Stack :
1. Elemen TOP (puncak) diketahui
2.penisipan dan penghapusan elemen selalu dilakukan di TOP
3 LIFO

Pemanfaatan Stack :
Perhitungan ekspresi aritmatika (posfix)
algoritma backtraking (runut balik)
algoritma rekursif.

Empat operasi dasar yang berlaku pada stack :
1. CREATE(stack)
2. ISEMPTY(stack)
3. PUSH(elemen, stack)
4. POP(stack)

1. CREATE
Adalah operator yang menunjukkan suatu stack kosong dengan nama S.
Jadi : NOEL(CREATE(S)) = 0
TOP(CREATE(S)) adalah TIDAK TERDEFINISI.

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

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

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


CONTOH PEMANFAATAN STACK
• Notasi Infix Prefix
• Notasi Infix Postfix
Pemanfaatan stack antara lain untuk menulis ungkapan dengan menggunakan notasi tertentu.
Contoh :
( A + B ) * ( C – D )
Tanda kurung selalu digunakan dalam penulisan ungkapan numeris untuk mengelompokkan bagian mana yang akan dikerjakan terlebih dahulu.
Dari contoh ( A + B ) akan dikerjakan terlebih dahulu, kemudian baru ( C – D ) dan terakhir hasilnya akan dikalikan.
A + B * C – D
B * C akan dikerjakan terlebih dahulu, hasil yang didapat akan berbeda dengan hasil notasi dengan tanda kurung.
Notasi Infix Prefix
Cara penulisan ungkapan yaitu dengan menggunakan notasi infix, yang artinya operator ditulis diantara 2 operator.
Seorang ahli matematika bernama Jan Lukasiewiccz mengembangkan suatu cara penulisan 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 ]
= *+AB – C D
Penggunaan notasi postfix dalam stack, misal :
2 14 + 5 * = 80