Assalamu'alaikum wr.wb.......
Semangat Pagi, Pagi ini saya akan membahas tentang STACK DAN QUEUE
1. STACK
a. Pengertian Stack (Tumpukan)
Stack
(Tumpukan) adalah kumpulan elemen-elemen data yang disimpan dalam satu lajur
linear. Kumpulan elemen-elemen data hanya boleh diakses pada satu lokasi saja
yaitu posisi ATAS (TOP) tumpukan. Tumpukan digunakan dalam algoritma pengimbas
(parsing), algoritma penilaian (evaluation) dan algoritma penjajahan balik
(backtrack). Elemen-elemen di dalam tumpukan dapat bertipe integer, real,
record dalam bentuk sederhana atau terstruktur.
Stack adalah
suatu tumpukan dari benda. Konsep utamanya adalah LIFO (Last In First Out),
benda yang terakhir masuk dalam stack akan menjadi benda pertama yang
dikeluarkan dari stack. Tumpukan disebut juga “Push Down Stack” yaitu
penambahan elemen baru (PUSH)ndan penghapusan elemen dari tumpukann(POP).
Contoh pada PDA (Push Down Automaton). Sistem pada pengaksesan pada tumpukan
menggunakn system LIFO (Last In First Out), artinya elemen yang terakhir masuk
itu yang akan pertama dikeluarkan dari tumpukan (Stack). Ilustrasi tumpukan
(Stack) dapat digambarkan seperti tumpukan CD atau tumpukan sate. Stack
merupakan suatu susunan koleksi data dimana dapat ditambahkan dan dihapus
selalu dilakukan pada bagian akhir data, yang disebut dengan Top Of Stack.
Sebelum struktur
data tumpukan ini bisa digunakan, harus dideklarasikan dahulu dalam kamus data.
Ada beberapa cara pendeklarasian struktur data ini, salah satunya dengan
menggunakan tata susunan linear (larik) dan sebuah variable, yang dikemas dalam
tipe data record. Stack (tumpukan) adalah struktur data bertipe record yang
terdiri dari field elemen, bertipe larik/array dengan indek dari 1 sampai
dengan MaksTum (Maksimum Tumpukan), atas, bertipe interger berkisar dari 0
(saat kosong) sampai dengan MaksTum (Maksimum Tumpukan).
b. Operasi – operasi pada Stack (Tumpukan)
Operasi yang sering diterapkan pada struktur data Stack
(Tumpukan) adalah Push dan Pop.
Operasi – operasi yang dapat diterapkan adalah sebagai
berikut :
1. Push : digunakan untuk menembah 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. Create Stack : membuat Tumpukan baru S, dengan jumlah
elemen kosong.
5. MakeNull : mengosongkan Tumpukan S, jika ada elemen maka
semua elemen dihapus.
6. IsEmpty : fungsi yang digunakan untuk mengecek apakah
Stack sudah kosong.
7. Isfull : fungsi yang digunakan untuk mengecek apakah
Stack sudah penuh.
Pada proses Push,
Tumpukan (Stack) harus diperiksa apakah jumlah elemen sudah mencapai masimum
atau tidak. Jika sudah mencapai maksimum maka OVERFLOW, artinya Tumpukan penuh
tidak ada elemen yang dapat dimasukkan ke dalam Tumpukan. Sedangkan pada proses
Pop, Tumpukan harus diperiksa apakah ada elemen yang hendak dikeluarkan atau
tidak. Jika tidak ada maka UNDERFLOW, artinya tumpukan kosong tidak ada elemen
yang dapat diambil.
c. Macam – macam Stack
1. Stack dengan Array
Sesuai dengan sifat stack, pengambilan atau penghapusan
elemen dalam stack harus dimulai dari elemen teratas.
2. Double Stack dengan Array
Metode ini adalah teknik khusus yang dikembangkan untuk
menghemat pemakaian memori dalam pembuatan dua stack dengan array. Intinya
adalah penggunaan hanya sebuah array untuk menampung dua stack.
Ilustrasi Stack pada saat Inisialisasi
Ilustrasi Stack pada saat full
Contoh :
Hasil :
2. QUEUE (ANTRIAN)
a. Definisi Queue (Antrian)
Queue
merupakan suatu struktur data linear. Konsepnya hampir sama dengan Stack,
perbedaannya adalah operasi penambahan dan penghapusan pada ujung yang bebeda.
Penghapusan dilakukan pada bagian depan (front) dan penambahan berlaku pada
bagian belakang (Rear). Elemen-elemen di dalam antrian dapat bertipe integer,
real, record dalam bentuk sederhana atau terstruktur.
Tumpukan
disebut juga “Waiting Line” yaitu penambahan elemen baru dilakukan pada bagian
belakang dan penghapusan elemen dilakukan pada bagian depan. Sistem pada
pengaksesan pada Queue menggunakan sistem FIFO (First In First Out), artinya
elemen yang pertama masuk itu yang akan pertama dikeluarkan dari Queue. Queue
jika diartikan secara harfiah, queue berarti antrian. Queue merupakan salah
satu contoh aplikasi dari pembuatan double linked list yang cukup sering kita
temui dalam kehidupan sehari-hari, misalnya saat anda mengantri diloket untuk
membeli tiket.
Istilah yang
cukup sering dipakai apabila seseorang masuk dalam sebuah antrian adalah
enqueue. Sedang istilah yang sering dipakai bila seseorang keluar dari antrian
adalah dequeue.
b. Operasi-operasi pada Queue
1. Create Queue (Q) : membuat antrian baru Q, dengan jumlah
elemen kosong.
2. Make NullQ (Q) : mengosongkan antrian Q, jika ada elemen
maka semua elemen dihapus.
3. EnQueue : berfungsi memasukkan data kedalam antrian.
4. DeqQueue : berfungsi mengeluarkan data terdepan dari
antrian.
5. Clear : Menghapus seluruh Antrian
6. IsEmpty : memeriksa apakah antrian kosong
7. IsFull : memeriksa apakah antrian penuh.
Contoh :
Hasil :