Tumpukan (Stack) • Susunan koleksi data dimana proses penambahan data (add) dan penghapusan data (delete) selalu dilakukan melalui posisi akhir data. • Posisi akhir data Æ top of stack • Stack bersifat LIFO (Last In First Out) LIFO Æ Data yang terakhir masuk ke dalam stack menjadi data yang pertama keluar dari stack
struktur data - tumpukan
1
Operasi Stack Macam-macam operasi stack: • • • • • •
Push: menambah data pada stack (tumpukan paling atas) Pop: menghapus data pada stack (tumpukan paling atas) IsEmpty: menguji apakah stack dalam keadaan kosong IsFull: menguji apakah stack dalam keadaan penuh Print: menampilkan semua elemen (isi) stack Clear: mengosongkan atau menghapus semua elemen (isi) stack • Peek (‘mengintip’): menampilkan atau melihat isi stack pada posisi teratas (top of stack) saja struktur data - tumpukan
2
Implementasi stack dengan struct Langkah-langkah... • Definisikan konstanta MAX_STACK untuk menyimpan nilai maksimum isi stack • Definisikan stack menggunakan tipe data struct (struct stack) • Elemen struct stack adalah: int top dan int data[MAX_STACK - 1] (top Æ mencatat posisi data teratas data Æ mencatat isi stack) • Definisikan variabel tumpuk (yang bertipe stack) struktur data - tumpukan
3
Deklarasi awal • Deklarasi MAX_STACK #define MAX_STACK 8
• Deklarasi STACK dengan tipe data struct typedef struct STACK { int top; int data[MAX_STACK - 1]; };
• Deklarasi tumpuk yang bertipe STACK STACK tumpuk; struktur data - tumpukan
4
Inisialisasi Inisialisasi Stack • Inisialisasi isi top = -1 , berarti isi stack masih kosong, atau belum berisi data. (ingat indeks array dalam bahasa C dimulai dari 0) • top Æ variabel penanda yang menunjukkan cacah data di dalam stack.
struktur data - tumpukan
5
Stack dalam keadaan kosong
Ilustrasi stack pada awal inisialisasi, stack dalam kondisi kosong. struktur data - tumpukan
6
Stack dalam keadaan penuh Ilustrasi stack dalam keadaan penuh.
struktur data - tumpukan
7
Fungsi IsEmpty dan IsFull Fungsi IsEmpty (memeriksa apakah Stack masih kosong?) • Memeriksa top, jika top == -1, berarti stack masih kosong
Fungsi IsFull (memeriksa apakah Stack sudah penuh?) •
Memeriksa top, jika top == [MAX_STACK-1], berarti stack sudah penuh
struktur data - tumpukan
8
Fungsi Push Fungsi Push • Untuk menambah data pada stack (tumpukan paling atas). Data yang diinputkan selalu menjadi elemen teratas Stack (Top of Stack). Algoritma Push • Apabila stack belum terisi penuh, lakukan: – Perbarui nilai top, dengan menambah satu (increment) nilai top (top=top+1 atau top++) – Isikan data baru ke stack (pada posisi top yang baru) • Apabila stack telah terisi penuh, batalkan penambahan data, tampilkan pesan “stack telah terisi penuh“ struktur data - tumpukan
9
Ilustrasi fungsi Push
struktur data - tumpukan
10
Fungsi POP Fungsi Pop • Untuk menghapus data pada stack (tumpukan paling atas). Data yang dihapus selalu menjadi elemen teratas Stack (Top of Stack) Algoritma Pop • Apabila stack tidak dalam keadaan kosong, lakukan: – Tampilkan data yang akan dihapus, hapus data tersebut. – Perbarui nilai top, dengan mengurangi satu (decrement) nilai top (top=top-1 atau top--) • Apabila stack dalam keadaan kosong, batalkan penghapusan data, tampilkan pesan “stack dalam keadaan kosong“ struktur data - tumpukan
11
Ilustrasi fungsi Pop
struktur data - tumpukan
12
Fungsi Print Fungsi Print • Untuk menampilkan semua elemen (isi) stack. • Menggunakan proses perulangan, dimulai dari indeks array terbesar, diteruskan ke indeks yang lebih kecil. • Nilai top tidak diubah (karena hanya menampilkan isi stack saja)
struktur data - tumpukan
13
Ilustrasi fungsi Print
struktur data - tumpukan
14
Fungsi Clear Fungsi Clear • Untuk mengosongkan atau menghapus semua elemen (isi) stack • Cara1. Menggunakan proses Pop yang diulang sebanyak Top+1 kali Perhatikan, perulangan bukan sebanyak MAX_STACK • Cara2. Mengubah nilai Top dengan -1 (Top = -1)
struktur data - tumpukan
15
Fungsi Peek Fungsi Peek (‘mengintip’) • Digunakan untuk menampilkan atau melihat isi stack pada posisi teratas (top of stack) saja. Perhatikan, Bedakan dengan menampilkan nilai top.
struktur data - tumpukan
16
Sumber Referensi – James Roberge, Stefan Brandle, dan David Whittington, 2003, C++ Data Structures 2nd Edition, Jones and Bartlett Publishers, Inc., Sudbury, Massachusetts. – Antonius Rachmat Chrismanto – UKDW Yogyakarta. – P. Insap Santosa, 1992, Struktur Data Menggunakan Turbo Pascal 6.0, Penerbit Andi, Yogyakarta. – Berbagai sumber dari Internet. struktur data - tumpukan
17
