STACK
(TUMPUKAN)
(TUMPUKAN)
- PENGERTIAN STACK
Pengertian Stack pada Struktur Data adalah sebagai tumpukan dari benda, sekumpulan
data yang seolah-olah diletakkan di atas data yang lain, koleksi dari
objek-objek homogen, atau Suatu urutan elemen yang elemennya dapat diambil dan
ditambah hanya pada posisi akhir (top) saja. Stack pada Struktur Data dapat diilustrasikan dengan dua buah kotak
yang ditumpuk, kotak yang satu akan ditumpuk diatas kotak yang lainnya. Jika
kemudian stack 2 kotak tadi, ditambah kotak ketiga, keempat, kelima, dan
seterusnya, maka akan diperoleh sebuah stack kotak yang terdiri dari N
kotak.
Suatu
struktur 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.
- DEKLARASI STACK
Stack
dapat dideklarasikan sebuah record yang mempunyai sebuah array data untuk
menyimpan elemen stack dan sebuah vafriabel top untuk menunjuk stack elemen
atas (top element). Deklarasi selengkapnya sebagai berikut:
Tipestack = record
Data : array[1..maks_stack] of tipe data
Top : 0..maks_stack;
End.
Var S : tipestack;
Tipestack
adalah nama pengenal tipe untuk stack
Maks_stack merupakan
jumlah meksimum elemen stack.
Cara
mendefenisikan Stack dengan Array of Struct yaitu:
1.
Definisikan Stack dengan menggunakan struct
2.
Definisikan konstanta MAX_STACK untuk menyimpan maksimum isi stack
3.
Buatlah variabel array data sebagai implementasi stack
4.
Deklarasikan operasi-operasi/function di atas dan buat implemetasinya.
contoh
:
//Deklarasi
MAX_STACK
#define MAX_STACK 10
//Deklarasi
STACK dengan struct dan array data
typedef struct STACK{
int top;
char data[10][10];
};
//Deklarasi/buat
variabel dari struct
STACK tumpuk;
- OPERASI PADA STACK
a)
Instalasi
. instalasi adalah proses untuk membuat stack dalam keadaan kosong. Proses ini
dilakukan dengan mengisi variabel top dengan nilai yang tidak menunjuk salah
satu elemen array. Pada model deklarasi di atas, maka top diisi dengan 0. Top adalah suatu variabel penanda dalam STACK yang
menunjukkan elemen teratas Stack sekarang. Top Of Stack
akan selalu bergerak hingga mencapai MAX of STACK sehingga menyebabkan stack
penuh.
b)
Push.
Push adalah proses memasukkan elemen baru kedalam stack. Prosesnya meliputi
mengalokasikan ruang dengan mengubah nilai top untuk menunjuk ruang di
sebelahnya, kemudian memasukan data ke dalam lokasi tersebut.
Asalkan stack
masih belum penuh, isikan data baru ke stack berdasarkan indeks top of stack setelah diincrement
sebelumnya.
c)
Pop
adalah proses untuk mengambil elemen
teratas
dari stack. Prosesnya meliputi mengambil data dari elemen paling atas, kemudian
menghapus elemen tersebut dengan cara mengubah nilai top untuk elemen dibawahnya sehingga jumlah elemen stack berkurang.
d)
Empty/Kosong.
Empty adalah operasi untuk mengetahui status stack, kosong atau tidak.
Dengan
cara memeriksa top of stack, jika masih -1 maka berarti stack masih kosong.
e)
Full/Penuh.
Full adalah operasi untuk mengetahui status stack, penuh atau tidak.
Dengan
cara, memeriksa top of stack, jika sudah sama dengan MAX_STACK-1 maka full,
jika belum (masih lebih kecil dari MAX_STACK-1) maka belum full.
Printberfungsi untuk menampilkan semua elemen-elemen
stack dengan cara looping semua nilai array secara terbalik, karena kita harus
mengakses dari indeks array tertinggi terlebih dahulu baru ke indeks yang
kecil.
- Bila stack diimplementasikan dengan array yang diakses dari arah indeks terkecil ke arah indeks terbesar, maka operasi-operasi di atas dapat dituliskan dengan prosedur-prosedur berikut.
procedure inisialisasi
( var S : tipestack) ;
begin
S. top := 0
End ;
Funcition penuh
(S : tipestack) : boolean ;
Begin
Penuh := ( S. top = 0)
End ;
Function size (S :
tipestack) : integer ;
Begin
Size := S. top = 0
End ;
Procedure push (X ;
tipedata; var S :
Tipestack);
Begin
If
penuh (S) then
Error
{procedure untuk memberitahukan
Stack penuh}
else
begin
top := top + 1;
S. data [top] := X;
end;
endprocedure pop (var X
; tipedata; var S : tipestack) ;
begin
if kosong (S) then
Error {procedure untuk memberitahukan
Stack kosong}
else
Begin
X := S.data [top] ;
end;
End.
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.
- Abstract Data Type (ADT)
ADT
adalah definisi TYPE dan sekumpulan PRIMITIF (operasi dasar)
terhadap TYPE tersebut. Selain itu, dalam sebuah ADT yang lengkap, disertakan
pula definisi invarian dari TYPE dan aksioma yang berlaku. ADT merupakan
definisi statik. Definisi type dari sebuah ADT dapat mengandung sebuah
definisi ADT lain.
Misalnya
:
Ø
ADT Waktu yang terdiri dari ADT JAM dan ADT DATE
Ø
GARIS yang terdiri dari dua buah POINT
Ø
SEGI4 yang terdiri dari pasangan dua buah POINT (Top, Left) dan (Bottom, Right)
Pentingnya
sebuah ADT (Abstract Data Type) :
Ø
Struktur yang besar memungkinkan sistem menjadi komponen berlapis.
Ø
Memungkinkan kode program menjadi lebih generik / reusable.
Ø
Biarkan fokus apa (spesifikasi) untuk dipisahkan dari bagaimana (implementasi)
Ø
Digunakan modularitas untuk perubahan lokal
- CONTOH PROGRAM STACK DALAM PASCAL
program
stack;
uses
winCrt;
const
max = 100;
var
L : array [1..max] of char;
sisa, i, j, top : integer;
jawab : char;
kondisi : string;
procedure
inisiasi;
begin
top :=0;
end;
procedure
CEK;
begin
sisa := max - top;
if top = max then
kondisi := 'penuh'
else
if ((top < max) and (top > 0)) then
kondisi := 'belum penuh'
else
kondisi := 'kosong'
end;
procedure
PUSH;
begin
write('Masukan data : ');
readln(L[top+1]);
top := top + 1;
end;
procedure TAMPIL;
begin
writeln('Stack Yang Dihasilkan : ');
for i := top downto 1 do
begin
writeln(L[i]);
end;
end;
procedure POP;
begin
top := top - 1
end;
BEGIN
clrscr;
inisiasi;
jawab := 'Y';
while ((jawab = 'Y') or (jawab = 'y')) do
begin
writeln('PROGRAM STACK');
writeln('1. PUSH');
writeln('2. POP');
write('PILIH 1 ATAu 2 ? ');
readln(j);
case j of
1 : begin
CEK;
if kondisi = 'penuh' then
writeln('STACK PENUH, ANDA TIDAK BISA
MENAMBAH TUMPUKAN')
else
begin
if
kondisi <> 'penuh' then
begin
CEK;
writeln ('Stack ', kondisi, ', Masih
Bisa Menampung : ', sisa, ' data');
write ('Apakah Anda mau Menambah Data ?
(Y/T) ');
readln (jawab);
while (((jawab = 'Y') or (jawab = 'y'))
and (kondisi <> 'penuh')) do
begin
PUSH;
writeln;
writeln;
CEK;
writeln;
writeln;
TAMPIL;
writeln;
writeln;
writeln
('Stack ', kondisi, 'Masih Bisa Menampung : ', sisa, ' data');
write ('Apakah Anda mau Menambah Data ?
(Y/T) ');
readln (jawab);
end;
end
else
writeln ('STACK PENUH');
end;
end;
2 : begin
write ('Apakah Anda Yakin Mau Menghapus
Data ? (Y/T) ');
readln (jawab);
while (((jawab = 'Y') or (jawab = 'y'))
and (kondisi <> 'kosong')) do
begin
POP;
writeln;
writeln;
CEK;
writeln;
writeln;
TAMPIL;
writeln;
writeln;
writeln ('Stack Masih Bisa Dihapus : ',
top, ' data');
write ('Apakah Anda Mau Menghapus Data ?
(Y/T) ');
readln (jawab);
end;
if kondisi = 'kosong' then
writeln ('STACK KOSONG')
end;
end;
write ('Apakah Mau Kembali Ke Menu Utama ?
(Y/T) ');
readln (jawab);
end;
END.
