konsep dari Stack
Stack
Dalam
memecahkan suatu masalah, terkadang kita membutuhkan algoritma yang hanya
memperbolehkan insertion dan deletion pada akhir data saja, contohnya adalah
algoritma backtracking (runut balik) dsb. Nah, untuk memecahkan masalah semacam
itu, kita dapat menerapkan konsep stack.
Apa
itu stack ?
Stack
adalah sebuah abstract data type (ADT) yang berisi koleksi data item yang hanya
dapat diakses pada akhir bagian stack tersebut, biasa disebut top. Hal ini
berarti bahwa didalam sebuah stack, kita dapat memasukkan (insert) dan
menghapus (delete) item hanya dari posisi top tersebut. Item terakhir yang kita
masukkan kedalam sebuah stack adalah item yang paling pertama harus kita
keluarkan. Itulah mengapa stack disebut sebagai Last-In-First-Out (LIFO) data
structure. Kalimat sederhana yang dapat menjelaskan konsep tersebut adalah
kalimat “Masuk belakangan keluar duluan”.
Didalam
kehidupan sehari-hari, terdapat beberapa contoh penerapan algoritma dari data
structure ini, seperti dalam membuat suatu tumpukan piring, tumpukan buku,
tumpukan koin, tusuk sate, atau bahkan cara memakai gelang.
Salah
satu contoh, dalam membuat suatu tumpukan piring kita pasti menempatkan piring
pertama berada pada posisi paling bawah, dan piring terakhir berada pada
posisi paling atas.
Nah, ketika kita hendak mencuci atau mengambil
piring tersebut, maka kita akan mengambil piring pada tumpukkan atas terlebih
dahulu dan seterusnya hingga mencapai piring paling bawah. Hal tersebut juga
serupa pada tumpukan buku, koin, tusuk sate dan cara memakai gelang. Saya rasa
ilustrasi tersebut cukup menjelaskan konsep LIFO dari stack.
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.
Operasi – operasi pada Stack (Tumpukan)
Operasi yang sering diterapkan pada struktur data Stack (Tumpukan) adalah Push dan Pop. Operasi – operasi yang dapat diterapkan adalah sebagai berikut :
Operasi yang sering diterapkan pada struktur data Stack (Tumpukan) adalah Push dan Pop. Operasi – operasi yang dapat diterapkan adalah sebagai berikut :
1.
Push : digunakan untuk menembah item pada Stack pada Tumpukan paling atas.
2. Pop : digunakan untuk mengambil item pada Stack pada Tumpukan paling atas.
3. Clear : digunakan untuk mengosongkan Stack.
4. Create Stack : membuat Tumpukan baru S, dengan jumlah elemen kosong.
5. MakeNull : mengosongkan Tumpukan S, jika ada elemen maka semua elemen dihapus.
6. IsEmpty : fungsi yang digunakan untuk mengecek apakah Stack sudah kosong.
7. Isfull : fungsi yang digunakan untuk mengecek apakah Stack sudah penuh
2. Pop : digunakan untuk mengambil item pada Stack pada Tumpukan paling atas.
3. Clear : digunakan untuk mengosongkan Stack.
4. Create Stack : membuat Tumpukan baru S, dengan jumlah elemen kosong.
5. MakeNull : mengosongkan Tumpukan S, jika ada elemen maka semua elemen dihapus.
6. IsEmpty : fungsi yang digunakan untuk mengecek apakah Stack sudah kosong.
7. Isfull : fungsi yang digunakan untuk mengecek apakah Stack sudah penuh
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.
contoh konsep dari push dan pop
Fungsi
push: digunakan untuk menambahkan data ke dalam stack. Penambahan data tidak
bisa dilakukan apabila stack sudah penuh. Urutan perintahnya adalah:
menambahkan nilai top dan menambahkan data pada posisi nilai top. Jika dalam
Linked List menggunakan method addLast.
Fungsi
pop: digunakan untuk mengeluarkan data teratas stack dengan syarat bahwa stack
tidak kosong. Urutan perintahnya adalah : menghapus data pada posisi nilai top
dan menurunkan nilai top.
program tumpukan_kata;
uses wincrt;
const elemen = 255;
type S255 = string [elemen];
tumpukan = record
isi : s255;
atas : 0..elemen;
end;
var
T : tumpukan;
U : char;
kata : s255;
m,n : integer;
uses wincrt;
const elemen = 255;
type S255 = string [elemen];
tumpukan = record
isi : s255;
atas : 0..elemen;
end;
var
T : tumpukan;
U : char;
kata : s255;
m,n : integer;
ulang: string;
procedure awalan (var T : tumpukan);
begin
T.Atas := 0;
end;
procedure push (var T : tumpukan; Z: char);
begin
T.Atas := T.Atas+1;
T.Isi[T.Atas] := Z;
end;
function pop (var T : tumpukan): char;
begin
pop := T.Isi[T.Atas];
T.atas := T.atas-1;
end;
procedure awalan (var T : tumpukan);
begin
T.Atas := 0;
end;
procedure push (var T : tumpukan; Z: char);
begin
T.Atas := T.Atas+1;
T.Isi[T.Atas] := Z;
end;
function pop (var T : tumpukan): char;
begin
pop := T.Isi[T.Atas];
T.atas := T.atas-1;
end;
begin
clrscr;
repeat
writeln('Masukkan Kata yang anda inginkan :');
read(kata);
writeln;
for m:= 1 to length (kata) do
push (T, kata[m]);
write('Elemen yang di-push : ', kata);
writeln;
readln;
for m:= 1 to length (kata) do
push (t, kata[m]);
writeln;
writeln('Hasil akhir push dibaca dengan pop : ');
for n:= 1 to length (kata) do
clrscr;
repeat
writeln('Masukkan Kata yang anda inginkan :');
read(kata);
writeln;
for m:= 1 to length (kata) do
push (T, kata[m]);
write('Elemen yang di-push : ', kata);
writeln;
readln;
for m:= 1 to length (kata) do
push (t, kata[m]);
writeln;
writeln('Hasil akhir push dibaca dengan pop : ');
for n:= 1 to length (kata) do
begin
u:= pop (T);
write(u);
end;
writeln;
writeln;
writeln('==========================================');
writeln;
writeln('Coba lagi? Ketik [Y / T], Kemudian [ENTER]');readln (ulang);
writeln;
clrscr;
Until (ulang = 'T') OR (ulang = 't');
writeln;
readln;
end.
u:= pop (T);
write(u);
end;
writeln;
writeln;
writeln('==========================================');
writeln;
writeln('Coba lagi? Ketik [Y / T], Kemudian [ENTER]');readln (ulang);
writeln;
clrscr;
Until (ulang = 'T') OR (ulang = 't');
writeln;
readln;
end.
program dari Stack !
program stack1;
uses wincrt;
const NMax =100;
type
typestack = array [0..NMax] of integer;
var
stack:typestack;
begin
stack[0]:=0;
end;
begin
stackpenuh:=(stack[0]=NMax);
end;
Pengertian ADT
ADT
adalah tipe data yang dibuat oleh programmer
sendiri yang memiliki suatu nama tertentu.
- ADT dapat berupa tipe data dasar namun diberi nama
baru atau berupa kumpulan tipe data berbeda yang
diberi nama baru.
- Untuk pembuatan ADT digunakan keyword typedef
sendiri yang memiliki suatu nama tertentu.
- ADT dapat berupa tipe data dasar namun diberi nama
baru atau berupa kumpulan tipe data berbeda yang
diberi nama baru.
- Untuk pembuatan ADT digunakan keyword typedef
Abstract
Data Type (ADT) adalah definisi TYPE
dan sekumpulan PRIMITIF (operasi dasar) terhadap TYPE
tersebut. Definisi TYPE dari sebuah ADT dapat mengandung sebuah definisi ADT
lain.
Misalnya:
¢ ADT
Waktu 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)
TYPE
diterjemahkan menjadi type terdefinisi dalam bahasa yang bersangkutan, misalnya
menjadi struct dalam bahasa C. Primitif,
dalam konteks prosedural, diterjemahkan menjadi
fungsi atau prosedural.
ADT biasanya diimplementasi menjadi dua buah modul,
yaitu
1.Definisi/Spesifikasi Type dan Primitif
Spesifikasi
type sesuai dengan bahasa yang bersangkutan
Spsesifikasi
dari primitif sesuai dengan kaidah dalam konteks prosedural, yaitu:
Fungsi
: nama, domain, range, dan prekondisi jika ada
Prosedur
: Initial State, Final State, dan Proses yang dilakukan
2. Body/realisasi dari primitif,
berupa kode program dalam bahasa yang bersangkutan.
Realisasi ADT
dalam beberapa bahasa:
Dalam modul ADT tidak terkandung definisi
variabel. Modul ADT biasanya dimanfaatkan oleh modul lain,
yang akan mendeklarasikan variabel bertype ADT
tersebut dalam modulnya. Jadi ADT bertindak
sebagai Supplier (penyedia type dan
primitif), sedangkan modul pengguna berperan sebagai
Client (pengguna) dari ADT tersebut.
Biasanya ada sebuah pengguna yang khusus yang disebut
sebagai main program (program utama) yang memanfaatkan langsung type tsb.
konsep Array dalam Stack
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.