STACK

STACK

                Pengertian Stack atau tumpukan adalah suatu stuktur data yang penting dalam pemrograman yang mempunyai sifat LIFO (Last In First Out), Benda yang terakhir masuk ke dalam stack akan menjadi benda pertama yang dikeluarkan dari stack.  Stack (Tumpukan) adalah list linier yang dikenali elemen puncaknya (TOP) dan Aturan penyisipan dan penghapusan elemennya tertentu. Penyisipan selalu dilakukan “di atas“  TOP dan Penghapusan selalu dilakukan pada TOP. TOP adalah satu-satunya alamat tempat terjadi operasi. Elemen yang ditambahkan paling akhir akan menjadi elemen yang akan dihapus.Dikatakan bahwa elemen Stack akan tersusun secara LIFO (Last In First Out).

OPRASI-OPRSI/ FUNGSI 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

Berikut ini merupakan karakteristik yang dimiliki oleh stack :

- Data hanya dapat di-insert pada posisi top stack

- Data hanya dapat di-delete pada posisi top stack

- Data tidak dapat di-delete dari tengah-tengah stack tanpa memindahkan item yang ada pada atasnya terlebih dahulu

Terdapat 2 operasi basic dalam stack :

- PUSH

- POP

Ketika kita memasukkan data kedalam sebuah stack, kita dapat menyebutnya PUSH. Sebaliknya, jika kita mengeluarkan data dari sebuah stack, kita dapat menyebutnya POP. Untuk lebih memperjelas PUSH dan POP, Simaklah gambar berikut ini.

IMPLEMENTASI STACK MENGGUNAKAN ARRAY

                Sebuah array dapat kita manfaatkan untuk mengimplementasikan stack jika jumlah elemen maksimum diketahui. Ketika kita hendak meng- implementasikan stack menggunakan array, kita harus memastikan bahwa array yang dideklarasikan cukup untuk menyimpan data atau elemen maksimum pada stack.

Untuk menerapkan stack menggunakan array, tentunya kita harus mendeklarasikan array terlebih dahulu. Misalkan :

int stack[10];

Pendeklarasian diatas berarti kita membuat sebuah array dengan ukuran/size sebesar 10, dan hanya dapat menampung maksimal 10 nilai integer.

Setelah mendeklarasikan array, kita perlu mendeklarasikan variabel untuk menyimpan index terakhir (top position), misalnya kita deklarasikan seperti ini :

int top;

Untuk kondisi stack yang masih kosong, mari kita set top = -1

Nah, baru setelah ini kita akan mengimplementasikan operasi PUSH dan POP.

PUSH

Dengan menjalankan operasi PUSH, berarti kita menyimpan data pada posisi top didalam stack. Langkah selanjutnya yang dapat kita tempuh adalah :

1. Melakukan increment terhadap top sebesar 1

2. Menyimpan nilai/value pada index top didalam array

(Sekarang top mengandung index dari elemen yang paling atas)

Perhatikan gambar dibawah ini :

Ketika stack di implementasikan didalam sebuahh array, size/ukuran dari stack adalah fixed. Hal ini berarti terdapat batas atas pada jumlah maksimum elemen yang dapat ditampung dalam stack.

Ketika stack sudah menampung data secara maksimum, maka dapat kita berikan status stack telah penuh/full. Ketika kita mencoba melakukan operasi push pada stack yang sudah penuh, maka akan terjadi overflow. Maka dari itu sebelum  kita melakukan operasi push, kita harus melakukan pengecekan apakah stack sudah full atau belum.

Jika stack sudah penuh, maka kondisi stack tsb adalah :

top = MAX -1

Jika kondisi tersebut true, maka operasi push seharusnya tidak dapat dilaksanakan.

Sehingga kita dapat membuat kondisi seperti berikut :

If top = MAX-1:

a. Display “Stack Full”

b. Exit

POP

Operasi POP berarti memindahkan atau menghapus item pada posisi top didalam stack. Untuk mengimplementasikannya kita dapat menggunakan langkah berikut ini :

1. Memungut kembali nilai dari index top

2. Melakukan decrement terhadap top sebesar 1

Bagaimanapun juga, sebelum melakukan operasi pop, kita harus melakukan pengecekan apakah stack itu kosong atau tidak. Jika kosong, tentu tidak ada elemen yang harus kita pop. Masih ingat dengan pendeklarasian diatas? Ya, sebelumnya kita telah mendeklarasikan bahwa jika kondisi stack kosong, maka top = -1

Sehingga kita dapat menerapkan kondisi berikut ini :

if top = -1

a. Display “Stack empty”

b. Exit

Contoh Program Stack PUSH / POP 

                Mengisi (PUSH) stack sampai PENUH, dan mengambil (POP) isi stack sampai KOSONG. Susun program untuk menyiapkan array satu dimensi yang akan digunakan sebagai stack S sebanyak 10 elemen, bertipe integer. Kemudian inputkan data (nilai numerik) dan simpan (PUSH) ke stack S. Proses input dan PUSH selesai bila data yang diinput bernilai = 999, atau stack S penuh. (nilai 999 dipakai sebagai end of data, tidak ikut dipush ke stack S). setelah itu dikeluarkan (POP) isi stack dan cetak ke layar satu persatu sampai stack menjadi KOSONG.

Contoh program sederhana single stack:

#include <iostream.h>
#include<stdio.h>
#define MAX 5
#define true 1
#define false 0

char stack[MAX];
int top;

void init(void);
int full(void);
int empty(void);
char pop(void);
void clear(void);
void push(char info);
void baca(void);

void main()
{
char pilih,elm;
cout<<"demo operasi single stack"<<endl;
init();
do
{
cout<<"OPERASI SINGLE STACK :"<<endl;
cout<<"[1]PUSH"<<endl;
cout<<"[2]POP"<<endl;
cout<<"[3]clear"<<endl;
cout<<"[4]BACA"<<endl;
cout<<"[5]selesai"<<endl;
cout<<"pilihan:";cin>>pilih;
switch(pilih)
{
case '1':cout<<"PUSH-->";cin>>elm;
push(elm);
break;
case '2':elm=pop();
cout<<"pop"<<elm;
break;
case '3':clear();
break;
case '4':baca();
break;
case '5':break;
default:cout<<"salah pilih..."<<endl;
}
cout<<endl;
}
while(pilih!='5');
}

void init(void)
{
top=0;
}
void push(char info)
{
if(full()!=true)
{
top++;
stack[top]=info;
}
else
cout<<"stack overflow..."<<endl;
}
char pop(void)
{
char info;
if(empty()!=true)
{
info=stack[top];
top--;
return(info);
}
else
cout<<"stack underflow..."<<endl;
}
void clear(void)
{
top=0;
}
int full(void)
{
if(top==MAX)
return(true);
else
return(false);
}
int empty(void)
{
if(top==0)
return(true);
else
return(false);
}
void baca(void)
{ int i;
cout<<"isi stack:"<<endl;

if(top>0)
{
for(i=1;i<=top;i++)
cout<<stack[i];
}
else
cout<<"(kosong)";
cout<<endl;
}

 

DAFTAR PUSTAKA:

http://www.purwadhikapress.com/konsep-stack.html

http://bekokmarley.blogspot.com/2014/01/pengertian-dan-penjelasan-struktur-data.html