TUGAS STACK

TUGAS

1. Jelaskan konsep dari Stack yang anda ketahui?
2. Berikan masing-masing contoh konsep dari push dan pop?
3. Buatlah program dari Stack !
4. Apa yang anda ketahui tentang ADT
5. Jelaskan konsep Array dalam Stack

KONSEP DARI SATACK

Stack atau Tumpukan adalah suatu struktur data yang terbentuk dari barisan hingga yang terurut dari satuan data. Pada Stack, penambahan dan penghapusan elemennya hanya dapat dilakukan pada satu posisi, yaitu posisi akhir stack. Posisi ini disebut Puncak atau Top dari stack.

Elemen Stack S yang berada pada posisi Top / Puncak dinyatakan dengan : TOP(S).

Jika stack S = [S1 ,S2 , . . . ,ST ] maka : TOP(S) = S T

Sedang banyaknya elemen stack S dinyatakan dengan :

NOEL(S) = T.

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. 

Stack bersifat LIFO (Last In First Out) artinya Benda yang terakhir masuk ke dalam stack akan menjadi yang pertama keluar dari stack 

Operasi-operasi yang biasanya tredapat pada Stack yaitu:

1. Push : digunakan untuk menambah 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. IsEmpty : fungsi yang digunakan untuk mengecek apakah stack sudah kosong

5. IsFull : fungsi yang digunakan untuk mengecek apakah stack sudah penuh

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;

Inisialisasi Stack

Pada mulanya isi top dengan -1, karena array dalam C dimulai dari 0, yang berarti stack adalah kosong.

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

v   IsFull berfungsi untuk memeriksa apakah stack sudah 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.

v     IsEmpty berfungsi untuk memeriksa apakah stack masih kosong atau tidak. Dengan cara memeriksa top of stack, jika masih -1 maka berarti stack masih kosong.

v  Push berfungsi untuk memasukkan elemen ke stack, selalu menjadi elemen teratas stack (yang ditunjuk oleh TOS).

Tambah satu (increment)  nilai top of stack lebih dahulu setiap kali ada penambahan elemen stack.

Asalkan stack masih belum penuh, isikan data baru ke stack berdasarkan indeks top of stack setelah diincrement sebelumnya.

v  Pop berfungsi untuk mengambil elemen teratas (data yang ditunjuk oleh TOS) dari stack. Ambil dahulu nilai elemen teratas stack dengan mengakses top of stack, tampilkan nilai yang akan dipop, baru dilakukan decrement nilai top of stack sehingga jumlah elemen stack berkurang.

v   Print berfungsi 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.

v   create berfungsi untuk membuat sebuah stack baru yang masih kosong.

Contoh Konsep Dari Push Dan Pop

Ø    Konsep Push

Push berfungsi untuk memasukkan elemen ke stack, selalu menjadi elemen teratas stack. Tambah satu (increment)  nilai top of stack lebih dahulu setiap kali ada penambahan elemen stack. Asalkan stack masih belum penuh, isikan data baru ke stack berdasarkan indeks top of stack setelah diincrement sebelumnya. Contoh : misalkan dalam sebuah lemari ingin disusun beberapa baju. Sedangkan dalam lemari tersebut sudah terisi dengan beberapa baju,maka terlebih dahulu dilakukan pengecekan kapasitasnya apa masing ada tempat kosong atau tidak, apabila masih tersisa ruang maka boleh diisi lagi dengan baju- baju di atasnya.

Ø  Konsep Pop

Pop berfungsi untuk mengambil elemen teratas (data yang ditunjuk oleh TOS) dari stack. Ambil dahulu nilai elemen teratas stack dengan mengakses top of stack, tampilkan nilai yang akan dipop, baru dilakukan decrement nilai top of stack sehingga jumlah elemen stack berkurang. Contohnya : misalkan ada sebuah tumpukan kotak dan kita ingin mengambil kotak yang berada di tengah – tengah, hal yang pertama yang harus kita lakukan adalah memindahkan kotak – kotak yang ada diatasnya, hingga kotak yang dibutuhkan dapat terambil.

Contoh program dari Stack

program stack;

uses wincrt;

const max = 10;

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;

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;

write ('Apakah Mau Kembali Ke Menu Utama ? (Y/T)  ');

readln (jawab);

end;

END.

ADT (ABSTRACT DATA TYPE)

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.

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 :

int top;

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

Kemudian baru setelah ini kita akan mengimplementasikan operasi PUSH dan POP.

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

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

v   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