Struktur Data Apa itu Stack (Tumpukan) ?
- Apa Itu Stack (Tumpukan)
Stack merupakan bagian dari
struktur data yang dikategorikan ke dalam bentuk linear data, dimana operasi
pemasukan maupun pengeluaran data selalu dilakukan pada salah satu sisinya.
Dalam dunia komputer, penggunaan stack (tumpukan) merupakan suatu hal yang umum
digunakan seperti untuk penentuan alamat memory, penempatan ruang data dan
aplikasi lain. Sebagai bagian dari struktur data, aplikasi stack juga digunakan
untuk berbagai macam keperluan seperti pengujian kalimatpalindrome, penguji
tanda kurung (matching parentheses), dan juga berfungsi sebagai konversi dari
notasi infix menjadi notasi postfix.
Pada perhitungan aritmatika,
notasi infix adalah notasi yang menempatkan operator ditengah dua operand
sedangkan notasi Postfix adalah notasi yang menempatkan operator setelah dua
operand. Penggunaan notasi infix merupakan hal yang lumrah digunakan dalam
perhitungan aritmatika dibandingkan dengan penggunaan notasi Postfix, akan
tetapi bagi mesin kompilasi notasi Postfixmerupakan notasi yang digunakan untuk
melakukan suatu perhitungan.
Suatu susunan koleksi data
dimana data dapat ditambahkan dan
dihapus selalu dilakukan pada bagian akhir data, yang disebut dengan top of
stack
Stack bersifat LIFO (Last In
First Out)
1.
Operasi
Stack
Ø Push
: digunakan untuk menambah item pada stack pada tumpukan paling atas
Ø Pop : digunakan untuk
mengambil item pada stack pada tumpukan paling atas
Ø Clear
: digunakan untuk mengosongkan stack
Ø IsEmpty
: fungsi yang digunakan untuk mengecek apakah stack sudah kosong
Ø IsFull
: fungsi yang digunakan untuk mengecek apakah stack sudah penuh
Fungsi IsFull
• Untuk memeriksa apakah stack sudah penuh?
• Dengan cara memeriksa top of stack, jika
sudah sama dengan MAX_STACK-1 maka full, jika belum (masih lebih kecil dari
MAX_STACK-1) maka belum full
Ilustrasi Stack pada
kondisi Full
int
IsFull(){
if(tumpuk.top
== max_stack-1)
return
1;
else
return
0;
}
Fungsi IsEmpty
·
Untuk memeriksa apakah data
Stack masih kosong?
·
Dengan cara memeriksa top of
stack, jika masih -1 maka berarti data Stack masih kosong!
int
IsEmpty(){
if(tumpuk.top
== -1)
return
1;
else
return
0;
}
Fungsi Push
·
Untuk memasukkan elemen ke
data Stack. Data yang diinputkan selalu
menjadi elemen teratas Stack (yang ditunjuk oleh ToS)
·
Jika data belum penuh,
·
Tambah satu (increment)
nilai top of stack lebih dahulu setiap kali ada penambahan ke dalam array data
Stack.
·
Isikan data baru ke stack
berdasarkan indeks top of stack yang telah di-increment sebelumnya.
·
Jika tidak, outputkan
“Penuh”
Fungsi Clear
·
Untuk mengosongkan atau menghapus semua elemen
(isi) stack
Fungsi Pop
·
Untuk mengambil data Stack
yang terletak paling atas (data yang ditunjuk oleh TOS).
·
Tampilkan terlebih dahulu
nilai elemen teratas stack dengan mengakses indeksnya sesuai dengan top of
stacknya, baru dilakukan di-decrement nilai top of stacknya sehingga jumlah
elemen stack berkurang.
Fungsi Print
·
Untuk menampilkan semua elemen-elemen
data Stack
·
Dengan cara me-loop semua
nilai array secara terbalik, karena kita harus mengakses dari indeks array
tertinggi terlebih dahulu baru ke indeks yang lebih kecil!
2.
Inisialisasi
Stack
·
Pada mulanya isi top dengan
-1, karena array dalam bahasa C dimulai dari 0, yang berarti bahwa data stack
adalah KOSONG!
·
Top adalah suatu variabel
penanda dalam Stack yang menunjukkan elemen teratas data Stack sekarang. Top Of Stack akan selalu bergerak hingga
mencapai MAX of STACK yang menyebabkan stack PENUH!
3.
Stack
with Array of Struct
·
Definisikan Stack dengan
menggunakan suatu struct
·
Definisikan konstanta
MAX_STACK untuk menyimpan maksimum isi stack
·
Elemen struct Stack adalah
array data dan top untuk menadakan posisi data teratas
·
Buatlah variabel tumpuk
sebagai implementasi dari struct Stack
Deklarasikan
operasi-operasi/function di atas dan buat implemetasinya