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 kalimat palindrome, 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 Postfix merupakan 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)
“Benda yang terakhir masuk ke dalam stack akan menjadi
yang pertama keluar dari stack
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
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
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!
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
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!
Notasi ada 3 jenis, yaitu Prefix,Infix dan Postfix
yang seperti kita ketahui di atas:
1.Prefix adalah notasi yang terbentuk atas operator
dengan operand, dimana oprator didepan operand.
contoh: A + B
* C (infix).
maka notasi
prefixnya adalah: +A*BC.
Pemecahannya:
A+B*C
Diketahui ada 3 operand yaitu: A, B, C dan 2 operand yaitu: +, *.proses
dimulai dengan melihat dari hirarkhi oprator.Contoh diatas operator yang
tertinggi adalah * kemudian +. Tanda * diapit oleh 2 operand yaitu B*C,
prefixnya dengan menggabungkan operand dan memindahkan operator ke depan dari
operand,sehingga fungsi B*C, notasi prefixnya menjadi *BC.
Sehingga hasil sementara dari notasi prefix adalah:
A+*BC
Selanjutnya mencari prefix untuk operator yang berikutnya yaitu +, cara yang dilakukan sama seperti diatas,
operator + diapit oleh operand, yaitu A dan *BC, gabungkan operand,sehingga
menjadi A*BC,lalu pindahkan operator kedepan operand,sehingga hasil akhir
menjadi :
+A*BC.
2.Infix adalah notasi yang membentuk atas operator
dengan operand,dimana operator berada diantara operand.
Contoh :
- A + B * C
- (A + B) * C
- A - (B + C) * D ^ E
3.Postfix adalah notasi yang membentuk atas operator
dengan operand, dimana operator berada dibelakang operand.
Contoh : A +
B * C ( infix).
maka notasi postfix adalah ABC*+.
Pemecahannya:
A + B * C
Diketahui
ada 3 operand yaitu : A,B,C dan 2 operator yaitu : +, *. proses dimulai dengan
melihat dari hirarkhi operator.Contoh diatas operator yang tertinggi adalah *
kemudian +.
Tanda * diapit oleh kedua operand yaitu B dan C yaitu
B*C, postfix dengan menggabungkan operand B dan C menjadi BC,lalu memindahkan
operator ke belakang operand C, sehingga fungsi B*C, notasi postfixnya menjadi
BC*.Sehingga hasil sementara dari notasi postfix adalah A + BC*
Selanjutnya mencari postfix untuk operator yang berikutnya, yaitu +,
dengan cara yang dilakukan sama seperti di atas, operator + diapit oleh 2
operand, yaitu : A dan BC* gabungkan operand tersebut,sehingga menjadi
ABC*,lalu pindahkan operator + kebelakang operand ABC*.
Sehingga hasil akhir
menjadi : ABC*+.
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.
Queue
1. 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.
2. 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
Komentar
Posting Komentar