Struktur Data
Stack & Queue
Stack
adalah sebagai sekumpulan data yang seolah-olah
diletakkan di atas data yang lain (Ditumpuk), koleksi dari
objek-objek homogen, atau suatu urutan elemen yang
elemennya dapat diambil dan ditambah hanya pada posisi
akhir/atas (top) saja.
Dapat diilustrasikan dengan dua buah kotak yang
ditumpuk, kotak yang satu akan ditumpuk diatas kotak yang
lainnya. Jika ditambah kotak ketiga, keempat, kelima, dan
seterusnya, maka akan diperoleh sebuah stack kotak yang
terdiri dari beberapa kotak
Stack
bersifat LIFO (Last In First Out)
artinya benda yang terakhir masuk ke
dalam stack akan menjadi yang pertama
keluar dari stack .
Stack
Operasi-operasi yang biasanya tredapat pada Stack yaitu:
1. Push : digunakan untuk menambah item pada stack pada
tumpukan paling atas
2. Pop : digunakan untuk mengambil item pada stack pada
tumpukan paling atas
3. Clear : digunakan untuk mengosongkan stack
4. Is Empty : fungsi yang digunakan untuk mengecek apakah
stack sudah kosong
5. IsFull : fungsi yang digunakan untuk mengecek apakah
stack sudah penuh.
Stack
Cara mendefenisikan Stack dengan Array of Struct
yaitu:
1. Definisikan Stack dengan menggunakan struct
2. Definisikan konstanta MAX_STACK untuk menyimpan
maksimum isi stack
3. Buatlah variabel array data sebagai implementasi
stack
4. Deklarasikan operasi-operasi/function di atas dan buat
implemetasinya.
Stack
Inisialisasi Stack
Pada mulanya isi top dengan -1, karena array dalam C
dimulai dari 0, yang berarti stack adalah kosong.
– Top adalah suatu variabel penanda dalam STACK yang menunjukkan
elemen teratas Stack sekarang. Top Of Stack akan selalu bergerak
hingga mencapai MAX of STACK sehingga menyebabkan stack
penuh.
– IsFull berfungsi untuk memeriksa apakah stack sudah penuh atau
tidak. 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.
Stack
Ilustrasi Stack pada kondisi Full
– IsEmpty berfungsi untuk memeriksa apakah stack masih kosong atau tidak.
Dengan cara memeriksa top of stack, jika masih -1 maka berarti stack
masih kosong.
– Push berfungsi untuk memasukkan elemen ke stack, selalu menjadi
elemen teratas stack (yang ditunjuk oleh TOS). Tambah satu (increment)
nilai top of stack lebih dahulu setiap kali ada penambahan elemen stack.
Asalkan stack masih belum penuh, isikan data baru ke stack berdasarkan
indeks top of stack setelah diincrement sebelumnya.
– Pop berfungsi untuk mengambil elemen teratas (data yang ditunjuk oleh
TOS) dari stack. Ambil dahulu nilai elemen teratas stack dengan
mengakses top of stack, tampilkan nilai yang akan dipop, baru dilakukan
decrement nilai top of stack sehingga jumlah elemen stack berkurang.
Stack
– Print berfungsi untuk menampilkan semua elemen-elemen stack dengan
cara looping semua nilai array secara terbalik, karena kita harus mengakses
dari indeks array tertinggi terlebih dahulu baru ke indeks yang kecil.
Queue
adalah sekumpulan data yang mana penambahan
elemen hanya bisa dilakukan pada suatu ujung disebut
dengan sisi belakang (rear), dan penghapusan (pengambilan
elemen) dilakukan lewat ujung lain (disebut dengan sisi
depan atau front).
Pada Stack atau tumpukan menggunakan prinsip
“Masuk terakhir keluar pertama” atau LIFO (Last In First
Out), maka pada Queue atau antrian prinsip yang digunakan
adalah “Masuk Pertama Keluar Pertama” atau FIFO (First In
First Out).
Queue
Pada Queue atau antrian Terdapat satu buah
pintu masuk di suatu ujung dan satu buah pintu
keluar di ujung satunya dimana membutuhkan
variabel Head dan Tail ( depan/ front, belakang/
rear).
Queue
Karakteristik Queue atau antrian :
[Link] antrian
[Link] (elemen terdepan antrian)
[Link] (elemen terakhir)
[Link] elemen pada antrian
[Link] antrian
Queue
Operasi pada Queue atau antrian
[Link](menambah item pada belakang
antrian)
[Link] (menghapus elemen depan dari
antrian)
[Link]( mendeteksi apakah pada antrian
mengandung elemen atau tidak)
Queue
Operasi-operasi Queue :
1. Create() Untuk menciptakan dan menginisialisasi Queue
dengan cara membuat Head dan Tail = -1
2. IsEmpty() Untuk memeriksa apakah Antrian sudah penuh
atau belum Dengan cara memeriksa nilai Tail, jika Tail = -1
maka empty. Kita tidak memeriksa Head, karena Head
adalah tanda untuk kepala antrian (elemen pertama dalam
antrian) yang tidak akan berubah-ubah.
3. IsFull Untuk mengecek apakah Antrian sudah penuh atau
belum. Dengan cara mengecek nilai Tail, jika Tail >= MAX-1
(karena MAX-1 adalah batas elemen array pada C) berarti
sudah penuh
Queue
Operasi-operasi Queue :
4. Enqueue Untuk menambahkan elemen ke dalam Antrian, penambahan
elemen selalu ditambahkan di elemen paling belakang. Penambahan
elemen selalu menggerakan variabel tail dengan cara increment counter
Tail terlebih dahulu
5. Dequeue() Digunakan untuk menghapus elemen terdepan/pertama
(head) dari Antrian dengan cara menggeser semua elemen antrian
kedepan dan mengurangi Tail dgn 1. Penggeseran dilakukan dengan
menggunakan looping.
6. Clear() Untuk menghapus elemen-elemen antrian dengan cara membuat
Tail dan Head = -1. Penghapusan elemen-elemen antrian sebenarnya
tidak menghapus arraynya, namun hanya mengeset indeks
pengaksesan-nya ke nilai -1 sehingga elemen-elemen Antrian tidak lagi
terbaca.
Queue
Operasi-operasi Queue :
7. Tampil() Untuk menampilkan nilai-nilai elemen Antrian.
Menggunakan looping dari head s/d tail