Tumpukan (struktur data)

Dalam ilmu komputer, tumpukan (bahasa Inggris: stack) 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. Operasi untuk memasukkan data biasa disebut push dan operasi untuk mengeluarkan biasanya disebut pop. Tumpukan dapat diimplementasikan sebagai senarai berantai atau larik. Tumpukan tergolong struktur data linear dan operasi push dan pop hanya bisa dilakukan di satu ujung struktur yang biasa disebut top dari tumpukan. Untuk melihat data yang ada di top tanpa mengeluarkannya, biasanya dilakukan menggunakan operasi peek.

Pemanfaatan

sunting

Perhitungan ekspresi aritmetika dan penguraian sintaks

sunting

Di kalkulator yang menggunakan notasi Polandia terbalik (letak operator bersifat posfiks) menggunakan tumpukan untuk menyimpan nilai. Selain itu, kebanyakan kompilator menggunakan tumpukan untuk menguraikan sintaks ekspresi dan blok program sebelum diterjemahkan ke bahasa level rendah.

Backtracking

sunting

Tumpukan bisa dimanfaatkan untuk algoritma backtracking. Misalkan ada sebuah maze. Kita bisa menyimpan daftar lokasi yang kita kunjungi menggunakan Tumpukan. Jadi, apabila kita mencapai jalan buntu, kita tinggal melakukan pop pada tumpukan daftar lokasi lalu mencoba jalan lain. Contoh algoritma backtracking yang sering digunakan adalah pencarian depth-first search pada struktur data pohon.