ALGORITMA DAN PEMROGRAMAN 2
MATERI STACK
1. Pengertian stack
Stack merupakan bentuk struktur data seperti tumpukan yang memiliki konsep Last In First Out (LIFO). Bermakna, data yang terakhir masuk merupakan data yang paling pertama dikeluarkan. Stack hanya memiliki satu pintu saja. Satu pintu itu untuk masuk dan keluar. dapat dibayangkan seperti menyusun buku ke dalam kotak. Maka buku yang dimasukkan terakhirlah yang harus dikeluarkan pertama kali.
Stack atau tumpukan, merupakan salah satu teknik dalam struktur data yang cukup mudah dipahami. Biasanya kita akan menjumpai topik ini pada awal materi setelah mempelajari array, karena array dibutuhkan dalam implementasi stack. Beberapa macam struktur data lain memiliki algoritma yang lebih rumit bila dibandingkan dengan stack. ilustrasi stack sapat digambarkan sebagai berikut.
Untuk menjelaskan pengertian diatas kita dapat mengambil contoh sebagai berikut. Misalnya kita mempunyai dua buah kotak yang kita tumpuk, sehingga kotak kita terletak di atas kotak yang lain. Jika kemudian stack dua buah kotak tersebut kita tambah dengan kotak ketiga dan seterusnya, maka akan kita peroleh sebuah stack kotak, yang terdiri dari N kotak.
2. Penggunaan stack
Pada beberapa literatur menyebutkan, bahwa stack umumnya digunakan untuk memisahkan ekspresi aritmatika.Stack dapat digunakan untuk mengubah notasi infix menjadi postfix.
3. Algoritma stack
a. Algoritma push
Kita bisa melakukan Push data atau memasukkan data jika Top terletak pada indeks yang bernomor kurang dari n-1 (<n-1). Ilustrasinya seperti pada kondisi Stack Bisa Diisi. Kemudian jika Top<n-1 kita melakukan proses untuk memindah Top ke Top+1. Lalu data yang kita masukkan tadi akan mengisi Top.
Contoh lain :
public void push(String value) {
stack[++top] = value;
}
b. Algoritma pop
Kita Bisa Melakukan Pop data atau mengeluarkan data jika Top terletak lebih dari indeks -1 (Top>-1). Ilustrasinya seperti pada Kondisi Stack yang memiliki isi. Kemudian data yang ada pada Top akan dipindahkan ke variabel x. Yang kemudian nanti dapat menampilkan data yang di pop.
Contoh lain :
public String pop() {
return stack[top — ];
}
c. IsEmpty()
Operasi untuk memeriksa apakah suatu stack kosong atau tidak. Bila stack dalam keadaan kosong, maka empty akan menghasilkan nilai TRUE, sebaliknya akan bernilai FALSE. Berikut contoh programnya.
public boolean isEmpty() {
return top == -1;
}
d. IsFull()
Operasi untuk memeriksa apakah stack sudah penuh atau belum. Bila stack sudah penuh, akan mengembalikan nilai TRUE, dan kondisi sebaliknya bernilai FALSE. berikut contoh programnya.
public boolean isFull() {
return top == max-1;
}
Jika melakukan operasi POP(e) sebanyak 2 kali lagi maka akan terjadi UNDERFLOW, yaitu suatu keadaan dimana tidak ada lagi elemen didalam stack yang dapat di ambil.
Karena itu untuk operasi POP(e) selalu terkait dengan pengecekan status stack, apakah stack dalam keadaan kosong, apabila pada pengecekan dengan EMPTY(S) menghasilkan nilai TRUE, maka operasi POP(e) tidak bisa dilakukan. Begitu pula sebaliknya pada operasi PUSH(e,S) tidak dapat dilakukan apabila stack penuh. Dalam hal ini, fungsi FULL(S) menghasilkan nilai TRUE. Nilai TRUE yang dihasilkan oleh fungsi FULL(S) dikarenakan terdapatnya batas jumlah elemen dalam stack.
Berikut adalah contoh program stack dalam bahasa pemrograman C++, beserta hasil runningnya.
Untuk program yang lebih detail, disini saya memiliki contoh program yang ditulis lebih rinci. Berikut contoh program stack, beserta hasil running nya.
#include
<conio.h>
#include
<stdlib.h>
#define max 4
using namespace
std;
struct Tumpukan
{
int atas;
int
data[max];//array
}T;//T sebagai
objek, jadi T ynag akan diakses kemana pun dia pergi
void awal()
{
T.atas=-1;
}
int kosong()
{
if(T.atas==-1)
return 1;
else
return 0;
}
int penuh()
{
if(T.atas==max-1)
return 1;
else
return 0;
}
void input(int
data)
{
if(kosong()==1)
{
T.atas++;//T.atas=T.atas+1;
T.data[T.atas]=data;
cout<<"Data
awal "<<T.data[T.atas]<<" masuk ke stack";
}
else
if(penuh()==0)
{
T.atas++;
T.data[T.atas]=data;
cout<<"Data
selanjutnya "<<T.data[T.atas]<<" masuk ke stack";
}
else
cout<<"Tumpukan
penuh";
}
void hapus()
{
if(kosong()==0)
{
cout<<"Data
teratas sudah terambil";
T.atas--;//T.atas=T.atas-1;
}
else
cout<<"Data
kosong";
}
void tampil()
{
if(kosong()==0)
{
for(int
i=T.atas;i>=0;i--)
{
cout<<"\nTumpukan
ke "<<i<<"="<<T.data[i];
}
}
else
cout<<"Tumpukan
kosong";
}
void bersih()
{
T.atas=-1;
cout<<"Tumpukan
kosong!";
}
//--------------------------------------->
int main()
{
int pil,data;
awal();
do
{
system("cls");
cout<<"1.
Input (PUSH)\n2. Hapus (POP)\n3. Tampil\n4. Bersihkan\n5. Keluar\nMasukkan
pilihan :";
cin>>pil;
switch(pil)
{
case
1:cout<<"Masukkan data = ";cin>>data;
input(data);
break;
case 2:hapus();
break;
case 3:tampil();
break;
case 4:bersih();
break;
//case 5:top();
// break;
// case
6:isempty();
// break;
// case 7:Noel()
//break
case 8:
cout<<"Terimakasih,
tekan enter untuk keluar";
}
getch();
}
while(pil!=5);
}
Hasil running
Ini adalah tampilan hasil output menu dari program stack, terdapat beberapa menu di dalamnya.
Berikutnya adalah hasil output ketika memilih menu nomor 1, yaitu input atau push
Kemudian hasil running ketika memilih menu nomor 2, yaitu hapus data dari stack atau pop.
Lalu hasil running dari hasil memilih menu nomor 3, yaitu menu untuk menampilkan tumpukan data dalam stack.
Hasil running ketika memilih menu nomor 4, yaitu menghapus stack, atau menu is empty pada program.
Kemudian yang terakhir adalah menu ke 5, keluar dari proghram stack.
4. Pemanfaatan stack
Salah satu pemanfaatan stack adalah untuk menulis ungkapan dengan menggunakan notasi tertentu. Seperti kita ketahui, dalam penulisan ungkapan numeris, kita selalu menggunakan tanda kurung untuk mengelompokkan bagian mana yang akan dikerjakan terlebih dahulu.
Sebagai contoh, perhatikan ungkapan berikut ini.
(C+D) * (E-F)
Dari contoh diatas (C+D) akan dikerjakan lebih dahulu, kemudian baru (E-F) dan hasilnya akan dikalikan. Lain halnya dengan contoh berikut ini.
C+D*E-F
D*E akan dikerjakan terlebih dahulu, kemudian diikuti yang lain. Dalam hal ini pemakaian tanda kurung sangat penting karena akan mempengaruhi hasil akhir. Cara penulisan ungkapan sering disebut dengan notasi infix , yang artinya bahwa operator ditulis diantara 2 operator.
Seorang ahli matematika yang bernama Jan Lukasiewiccz kemudian mengembangkan suatu cara penulisan ungkapan numeris yang kemudian dikenal dengan nama notasi prefix, yang artinya adalah bahwa operator ditulis sebelum kedua operand yang akan disajikan.
Perhatikan contoh dari notasi infix dan prefix berikut ini.
Infix Prefix
A+B +AB
A+B-C -+ABC
(A+B)*(C-D) *+AB-CD
5. Kelebihan dan kekurangan stack
A. Kelebihan
penambahan dan penghapusan data dapat dilakukan dengan cepat, yaitu O (1), selama memori masih tersedia, penambahan data bisa terus dilakukan. Dengan demikian tidak ada kekhawatiran terjadinya stack overflow.
B. Kelemahan
Setiap sel tidak hanya menyimpan value saja, melainkan juga pointer ke sel berikutnya. Hal ini menyebabkan implementasi stack memakai linked list dan memerlukan memori yang lebih banyak dari pada di implementasikan dengan Array. Tiap elemen pada linked list hanya bisa diakses dengan cara sekuensial, sehingga lambat, yaitu O (n).
Referensi :
http://arna.lecturer.pens.ac.id/Praktikum_ASD/02%20Stack.pdf
http://vandedjoel.blogspot.com/2016/05/makalah-stack-beserta-contoh-programnya.html
http://suputradwipratama274.blogspot.com/2015/06/v-behaviorurldefaultvmlo.html
0 komentar:
Posting Komentar