Konsep dari stack

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 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

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;

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;

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

            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.

 

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

                        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).