STACK
STACK
Pendahuluan :
•
Penyimpanan dan
pengambilan data yang sangat efektif apabila data yang terakhir masuk adalah
data yang akan diambil pertama kali.
•
Tumpukan
memungkinkan akses ke satu item data saja, yaitu item terakhir yang disisipkan.
•
Bila kita
menghilangkan item ini maka kita bisa mengakses ke sebelah item terakhir yang
disisipkan, dan seterusnya.
Sejarah :
•
Tumpukan pertama
kali diusulkan pada tahun 1955, dan kemudian dipatenkan pada tahun 1957, oleh
Friedrich L. Bauer Jerman.
•
Konsep yang sama
dikembangkan secara independen, pada sekitar waktu yang sama, oleh Leonard
Charles Australia Hamblin.
Pengertian :
•
Merupakan tumpukan
data yang seolah-olah diletakkan di atas data yang lain.
•
Kita dapat
menambahkan (menyisipkan) data dan mengambil (menghapus) data melalui ujung
yang sama, yang disebut sebagai ujung atas stack (top of stack).
•
Stack
bersifat LIFO (Last In First Out).
•
Benda
yang terakhir masuk ke dalam stack akan menjadi yang pertama keluar
dari stack.
Ilustrasi :
Misalnya :
Terdapat stack S=(a1, a2, a3,
…, an)
- Elemen mana yang merupakan elemen terbawah.
- Elemen mana yang merupakan elemen paling atas.
- Elemen mana yang akan dikeluarkan.
4. Elemen mana yang paling akhir dikeluarkan
Karakteristik :
•
Elemen stack yaitu
item-item data di elemen stack.
•
Top (elemen puncak
dari stack)
•
Jumlah elemen pada
stack.
•
Status / kondisi
stack.
Kondisi Stack :
Kondisi stack yang perlu diperhatikan adalah:
- Penuh: bila elemen stack mencapai kapasitas
maksimum. Pada kondisi ini tidak mungkin dilakukan penambahan ke stack.
Penambahan elemen menyebabkan kondisi kesalahan overflow.
- Kosong: bila tidak ada elemen di stack. Pada
kondisi ini, tidak mungkin dilakukan pengambilan elemen dari stack.
Pengambilan elemen menyebabkan kondisi kesalahan underflow.
Stack Representasi Statis :
•
Biasanya
diimplementasikan dengan menggunakan array.
•
Karena itu, stack
dengan representasi statis dapat mengalami kondisi elemen penuh.
Stack Representasi Dinamis :
•
Biasanya
diimplementasikan dengan menggunakan pointer yang menunjuk pada elemen-elemen
yang dialokasikan pada memori.
•
Elemen ditambahkan
akan menggunakan penambahan elemen pada awal stack (addfirst).
•
Saat pengambilan
atau penghapusan elemen menggunakan penghapusan di awal stack (delfirst).
OPERATOR-OPERATOR DALAM STACK
OPERASI PUSH
•
Adalah operasi
menambahkan elemen baru pada sebuah stack.
•
Aturan penambahan
stack:
▫
Sebagai kondisi
awal ada sebuah stack yang telah memiliki beberapa elemen dengan elemen paling
atas sebagai top.
▫
Dibuat sebuah
elemen baru yang akan dimasukkan ke dalam stack.
▫
Elemen baru
dimasukkan ke dalam stack.
▫ Penunjuk top pada stack diubah menunjuk ke elemen yang baru saja ditambahkan.
OPERASI POP
•
Adalah operasi
mengambil sebuah elemen dari sebuah stack. Aturan mengambil sebuah elemen dari
sebuah stack adalah sebagai berikut:
▫
Sebagai kondisi
awal ada sebuah stack yang telah memiliki beberapa elemen dengan elemen paling
atas sebagai top.
▫
Penunjuk top
diubah menjadi menunjuk elemen di bawah elemen atas.
Elemen atas diambil dari stack
Contoh :
•
Ada sekumpulan perintah stack yaitu push(3), push(5),
pop, push(2), pop, pop.
• Maka apabila dijalankan maka hasilnya adalah:
CREATE :
•
Operator ini
berfungsi untuk membuat sebuah stack kosong.
ISEMPETY :
•
Operator ini
berfungsi untuk menentukan apakah suatu stack adalah stack kosong. Operasinya
akan bernilai boolean, dengan definisi sebagai berikut :
ISEMPTY(S)
= true, jika S adalah stack kosong
= false,
jika S bukan stack kosong
atau
ISEMPTY(S) = true, jika (S) = NULL
= false, jika (S)= 1
Catatan : ISEMPTY(CREATE(S))
= true.
PENGGUNAAN
STACK :
•
Dalam dunia
komputer, penggunaan stack (tumpukan) merupakan suatu hal yang umum
digunakan seperti untuk penentuan alamat memory, penempatan ruang data dan
aplikasi lain.
•
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.
•
Sebuah kompilator
mempunyai tugas, salah satu di antaranya adalah menyelidiki apakah Pemrogram
telah dengan cermat mengikuti aturan tata bahasa, atau sintaks dari bahasa
pemrograman yang bersangkutan.
•
Misalnya untuk
parantheses kiri (tanda kurung buka) yang diberikan, harus dipastikan
adanya parantheses kanan (tanda kurung
tutup) yang bersangkutan.
MATCHING
PARENTHESES :
•
Proses ini
dilakukan compiler untuk memeriksa kelengkapan tanda kurung yang terdapat pada
suatu ekspresi aritmetik. Sedangkan stack di sini digunakan sebagai tempat
prosesnya.
•
Algoritma yang
digunakan adalah :
1. Elemen-elemen suatu ekspresi aritmetik (string)
di-Scan dari kiri ke kanan.
2. Jika ditemukan simbol "(" atau "Left
parenthesis", maka simbol tersebut di-push ke dalam stack.
3. Jika ditemukan simbol ")" atau "Right
parenthesis", maka isi stack diperiksa.
•
Jika stack kosong
terjadi kesalahan.
•
berarti : ada
simbol ")", tetapi tidak ada simbol "(" yang seharusnya
mendahului.
•
Jika stack tidak
kosong artinya ada pasangannya dan langsung di-POP keluar stack.
INTERPRETER
POSTFIX :
•
Contoh lain
penggunaan stack adalah pemeriksaan dan eksekusi ekpresi postfix.
•
Ekspresi postfix
merupakan ekpresi dengan aturan L R B dengan L adalah operand kiri, R operand
kanan dan B adalah operatornya.
•
Ekspresi yang kita
biasa gunakan sehari-hari adalah ekspresi infix dengan aturan L B R. Contoh,
jika ekspresi infixnya "6*7-2" maka ekspresi postfixnya adalah
"6 7 * 2 -".
NOTASI
INFIX DAN POSTFIX
•
Suatu perhitungan
aritmatika biasanya berhubungan dengan operand dan operator. Operand merupakan
suatu karakter atau elemen yang nilainya dioperasikan dengan bantuan suatu
operator untuk menghasilkan suatu solusi.
•
Misalkan jika
diberikan suatu ekspresi aritmatika 2 * 3, maka elemen ‘dua’ dan elemen ‘tiga’
merupakan operand dari ekspresi tersebut dan elemen ‘*’ merupakan operator
perkalian atas dua operand yang menghasilkan suatu solusi.
•
Dalam
penggunaannya, dalam kehidupan sehari-hari notasi infix merupakan notasi
aritmatika yang paling banyak digunakan untuk mengekspresikan suatu perhitungan
artimatik dibanding dengan dua notasi yang lain.
•
Akan tetapi
notasi Postfix merupakan notasi yang digunakan oleh mesin kompilasi pada
komputer dengan maksud untuk mempermudah proses pengkodean, sehingga mesin
kompilasi membutuhkan stack untuk proses translasi ekspresi tersebut
NOTASI
POSTFIX :
•
Bentuk aplikasi
stack yang lain adalah mengubah suatu ekspresi aritmatik (string) ke dalam
notasi postfix. Notasi postfix ini digunakan oleh compiler untuk menyatakan
suatu ekspresi aritmatik dalam bahasa tingkat tinggi (high level language). Stack
digunakan oleh compiler untuk mentransformasikan ekspresi aritmatik menjadi
suatu ekspresi dalam bentuk/notasi postfix.
Contoh
:
•
Misal diberikan
ekspresi aritmatik : A + B ;
•
Maka bentuknya
dalam notasi postfix menjadi : AB+
Urutan (prioritas) dari operator adalah :
- Perpangkatan (^)
- Perkalian (*) atau Pembagian (/)
- Penjumlahan (+) atau Pengurangan (-)
•
Ekspresi aritmatik
yang diberikan di- "Scan" dari kiri ke kanan.
•
Bila simbol yang
di-scan adalah "(", maka simbol tersebut di push ke dalam stack.
•
Bila simbol yang
di-scan adalah ")", maka seluruh isi stack di pop keluar mulai dari
simbol "(" yang pertama ditemukan dalam stack.
•
Bila simbol adalah
operator, maka dilakukan perbandingan dulu dengan simbol (operator) yang berada
pada posisi top dalam stack:
▫
Jika derajatnya
setara atau lebih rendah dari simbol yang berada pada posisi top, maka top
stack di-pop keluar sebagai output dan simbol yang baru di-push ke dalam stack.
▫
Jika derajatnya
lebih tinggi dari simbol yang berada pada posisi top, maka simbol (operator)
yang di-scan tersebut di-push ke dalam stack.
•
Bila simbol yang
di-scan adalah operand, maka simbol tersebut langsung sebagai output.
•
Bila simbol adalah
";" maka seluruh isi stack di-pop sebagai output.
Contoh
:
•
3 + 2 * 5 = 325*+
•
(A + B) * (C – D)
/ E; = AB+*CD-E/
Ubah
bentuk aritmetika berikut ke dalam bentuk postfix
•
( (A + B) * C / D
+ E ^ F ) / G ; A B + C * D / E F ^ + G /
•
((A
* B) + C / D – E * F) * G;
A B
* C D / + E F * - G *
•
STACK
PADA ARRAY
Deklarasi MAX_STACK
#define MAX_STACK 5
Deklarasi STACK dengan struct dan array data
typedef struct STACK{
int top;
int data[5];
};
Deklarasi variabel stack dari struct
STACK tumpuk;
Inisialisasi
•
Pada mulanya isi
top dengan -1, karena array dalam C/C++ dimulai dari 0, berarti stack adalah
KOSONG
•
TOP adalah
variabel penanda dalam STACK yang menunjukkan elemen teratas Stack.
•
TOP of STACK akan
selalu bergerak hingga mencapai MAX of STACK sehingga menyebabkan stack PENUH
Fungsi
IsEmpty
•
Digunakan untuk
memeriksa apakah stack masih dalam kondisi kosong
•
Dengan cara
memeriksa TOP of STACK.
Jika TOP masih = -1 maka berarti
stack masih kosong
Fungsi
IsFull
•
Digunakan untuk memeriksa
apakah kondisi stack sudah penuh
•
Dengan cara
memeriksa TOP of Stack.
Jika TOP of STACK = MAX_STACK-1 maka
FULL (Penuh).
Jika TOP of STACK < MAX_STACK-1
maka belum penuh
Fungsi
PUSH
•
Digunakan untuk
memasukkan elemen ke dalam stack dan selalu menjadi elemen teratas stack
•
Dengan cara :
1.
Menambah satu (increment) nilai
TOP of STACK setiap ada penambahan elemen stack selama stack masih belum penuh
2.
Isikan nilai baru ke stack
berdasarkan indeks TOPof STACK setelah ditambah satu (diincreament)
Fungsi
POP
•
Digunakan untuk
menghapus elemen yang berada pada posisi paling atas dari stack.
•
Dengan cara :
1.
Ambil dahulu nilai elemen
teratas stack dengan mengakses TOP of STACK
2.
Tampilkan nilai yang akan
diambil
3.
Lakukan decrement nilai TOP of
STACK sehingg jumlah elemen stack berkurang 1
Fungsi
CLEAR
•
Digunakan
untuk mengosongkan stack / membuat stack hampa sehingga Top pada Stack berada
kembali di posisi Top = -1
Komentar
Posting Komentar