A. Pengertian Stack
Stack pada
struktur data adalah sebagai tumpukan dari benda, sekumpulan data yang
seolah-olah diletakkan diatas data yang lain, koleksi dari objek-objek
homogeny, atau suatu urutan elemen yang elemennya dapat diambil dan ditambah hanya
pada posisi akhir.
F
|
E
|
D
|
C
|
B
|
A
|
Stack pada
struktur data dapat diilustrasikan dengan dua buah kotak yang ditumpuk, pada
kotak satu akan ditumpuk di bagian atas daripada kotak yang lainnya. Jika
kemudian stack pada 2 kotak tadi,
ditambah kotak ketiga, keempat, kelima, dan seterusnya, maka akan diperoleh
sebuah kotak yang terdiri dari N kotak.
Stack bersifat LIFO (Last in Fisrt Out) artinya benda yang
terakhir masuk ke dalam stack akan
menjadi yang pertama keluar dari stack.
Ciri tumpukan:
·
TOP
merupakan sebutan untuk elemen paling atas dari suatu stack.
·
Elemen
TOP merupakan elemen yang paling akhir ditambahkan.
·
Elemen
TOP diketahui.
·
Penambahan
dan penghapusan elemen selalu dilakukan di TOP
·
LIFO
(Last in Fisrt Out)
Pemanfaatan tumpukan:
·
Perhitungan
ekspresi aritmetika (posfix).
·
Algoritme
backtracking (runut balik).
·
Algoritme
rekursif.
Operasi tumpukan:
1. InsertFirst()
biasa disebut Push (input E: typeelmt, input/output data: stack):
menambahkan sebuah elemen ke tumpukan.
2. deleteFirst()
biasa disebut Pop (output E: typeelmt, input/output data: stack): menghapus sebuah elemen
tumpukan.
3. IsEmpty():
mengecek apakah stack kosong atau ada
elemennya.
4. IsFull():
mengecek apakah stack telah penuh
atau belum.
5. Clear():
menghapus semua data.
6. Peek():
melihat data TOP.
B. Kode Program Stack
1. Preprocessor dan Headerfile
#include<iostream>
#define
MAX 10
using
namespace std;
|
Disini hanya menggunakan dua baris pre-processor untuk mendefinisikan header file iostream untuk standard input/output stream dan MAX
untuk maksimum data array pada stack/tumpukan.
2. Struct data
//Deklarasi struct tumpukan
struct
stack
{
int top, data[MAX];
}tumpukan;
|
Pada struct dideklarasikan top untuk menunjukkan data teratas pada
tumpukan dan array data[] dengan
jumlah array dari data maksimum yang
telah didefinisikan sebelumnya yaitu MAX.
3. Inisialisasi Nilai top
bool isEmpty()
{
return Tumpukan.top == -1;
}
bool isFull()
{
return Tumpukan.top == MAX-1;
}
|
Untuk memastikan penunjuk (top)
berada pada posisi indeks ke 0 pada saat menambahkan data ke tumpukan maka
disini perlu memberikan nilai awal yaitu -1.4.
4. Memeriksa Tumpukan
bool isEmpty()
{
return Tumpukan.top == -1;\
}
bool isFull()
{
return Tumpukan.top == MAX-1;
}
|
kedua fungsi ini akan digunakan
untuk memeriksa apakah tumpukan penuh isFull()
(fungsi pertama) dan tumpukan kosong isEmpty(),
keduanya mengembalikan nilai Boolean,
jadi cukup mengembalikan nilai perbandingan pada fungsi masing-masing.
1. Pada fungsi isEmpty() akan mengembalikan nilai true jika nilai Tumpukan.top sama dengan -1, atau false jika tidak sama.
2. Pada fungsi isFull() akan mengembalikan nilai true jika nilai Tumpukan.top sama dengan maksimum data array yang telah ditentukan dikurang
satu MAX-1, atau false jika tidak
sama.
5. Menambahkan Data ke Tumpukan
void push()
{
if (isFull())
{
cout << “\n Tumpukan penuh” << endl;
}
else
{
Tumpukan.top++;
cout << “\n Masukkan data = “; cin >>
Tumpukan.data[Tumpukan.top];
cout << Tumpukan.data[Tumpukan.top] << “Masuk ke stack”
<<endl;
}
}
|
Untuk menginputkan data ke tumpukan
hak utama yang perlu dilakukan adalah memeriksa apakah tumpukan penuh atau
tidak. Jika penuh, maka tidak dapat menambahkan data ke tumpukan karena sudah
tidak ada ruang lagi yang tersedia. Jadi cukup tampilkan pesan bahwa
tumpukannya penuh. Jika masih ada ruang maka tambahkan nilai Tumpukan.top
dengan 1. Kemudian masukkan data ke ruang yang ditunjukkan oleh top.
6. Mengambil Data dari Tumpukan
void pop()
{
if (isEmpty())
{
cout << “\n Data kosong” << endl;
}
else
{
cout << “\n Data” <<
Tumpukan.data[Tumpukan.top]<<”sudah terambil”<<endl;
Tumpukan.top--;
}
}
|
Sebelum mengambil data, perlu
memeriksa apakah tumpukan kosong atau tidak, karena tidak dapat mengambil data
yang tidak ada pada tumpukan. Jika tumpukan kosong maka cukup tampilkan pesan
bahwa tidak ada data di tumpukkan tersebut. Jika masih ada data pada tumpukkan
maka tampilkan data dengan mengambil data teratas dari tumpukkan dan menghapus
data tersebut dengan mengurangi nilai top.
7. Menampilkan Data pada Tumpukan
void printStack()
{
if(isEmpty())
{
cout << “Tumpukan kosong”
}
else
{
cout << “\n Tumpukan : “;
for (int i = Tumpukan.top; i >= 0; i--)
cout <<
Tumpukan.data[i] << ((i == 0) ? “” : “,”);
}
}
|
sama halnya pada saat mengambil data
dari tumpukan, dan juga perlu memeriksa apakah tumpukan tersebut kosong atau
tidak. Jika tidak ada data di tumpukan maka tampilkan pesan bahwa tumpukan
kosong dan data tidak dapat ditampilkan. Jika masih ada data maka tampilkan
satu-persatu dari tumpukan dengan menggunakan perulangan.
8. Menampilkan Menu
int main()
{
int pilihan;
init();
do
{
printStack();
cout
<< "\n1. Input (Push)\n"
<<"2. Hapus (Pop)\n"
<<"3. Keluar\n"
<<"Masukkan Pilihan:
";
cin
>> pilihan;
switch
(pilihan)
{
case
1:
push();
break;
case
2:
pop();
break;
default:
cout << "Pilihan
tidak tersedia" << endl;
break;
}
} while (pilihan!=3);
}
|
Setelah semua data, variabel dan
fungsi selesai deklarasikan dan di inisialisasikan, selanjutnya bisa membuat
menu dengan do…while dengan switch didalamnya. Sebelum menampilkan
menu disini menampilkan data yang ada di stack
menggunakan printstack(), sehingga user dapat melihat data pada tumpukan.
C. Contoh Program
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<windows.h>
#define
max 20
using
namespace std;
struct
tong
{
int top;
char tmp[20][max];
}
tong;
void
push (char sampah[20]);
void
pop();
void
awal();
int
isEmpty();
int
isFull();
int
main()
{
int pilih;
char sampah[20];
string i;
awal();
do
{
system("cls");
cout << "\n
----------Program Stack---------- \n";
cout << "\n
---------- Tugas ----------- \n";
cout << "\n ------Tumpukan
Tong Sampah------- \n";
cout << "\n 1. PUSH
(Simpan) " << endl;
cout << "\n 2. POP (Ambil)
" << endl;
cout << "\n 3. EXIT
(Keluar) " << endl;
cout <<
"-----------------------------------------------\n\n";
if (!isEmpty())
{
for(int i = tong.top; i>=0;
i--)
{
cout << "["
<<tong.tmp[i] << "]" << endl;
}
}
else
{
cout << "[ tong sampah
kosong ]";
}
cout << "\n Masukkan
pilihan : "; cin >> pilih;
switch (pilih)
{
case 1:
cout << "\n Buang
Sampah : "; cin >> sampah;
push(sampah);
break;
cout << endl;
case 2:
pop();
break;
cout << endl;
case 3:
cout << "\n Tekan
enter untuk keluar : ";
break;
default:
cout << "\n
ERROR!";
break;
}
}
while (pilih!=3);
cout<<endl;
}
void
push (char sampah[20])
{
if (!isFull())
{
tong.top = tong.top+1;
strcpy(tong.tmp[tong.top], sampah);
}
else
cout << "\n isi tong
sampah penuh "<<endl;
}
void
pop()
{
if (!isEmpty())
{
tong.top--;
cout << "\n Sampah pada
tumpukan ke- " << tong.top+2 << " sudah diambil ";
}
else
cout << "\n Sampah dalam
tong kosong "<< endl;
}
void
awal ()
{
tong.top = -1;
}
int
isEmpty()
{
if (tong.top==-1)
return 1;
else
return 0;
}
int
isFull()
{
if (tong.top == max-1)
return 1;
else
return 0;
}
|
Hasil running:
Sumber: