Tugas stack

1.Jelaskan konsep dari Stack yang anda ketahui?

        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

STACK merupakan salah satu struktur data yang memiliki sistem kerja Last In First Out (LIFO), yang terakhir masuk pertama keluar. Stack dapat dibayangkan seperti tumpukan barang, dimana hanya data terakhir yang dapat diperoleh (diakses) dengan satu langkah. Data-data yang terletak di bawahnya hanya bisa diambil (pop) setelah data data yang berada di atasnya diambil (dikeluarkan).

2.Berikan masing-masing contoh konsep dari push dan pop?

Konsep push

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)

Perhatikan gambar dibawah ini :       

                                                                                                    

Konsep 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

3.Buatlah program dari Stack

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.

                                           

4.Apa yang anda ketahui tentang ADT     

            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:

klik gambar untuk memperbesar!

       

                     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

PENGERTIAN ADT (Abstrack Data Type)

    - 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

                                            

                                                           

ADT (Abstract Data Type)

         Tipe data abstrak (ADT) dapat didefinisikan sebagai model matematika dari objek data yang menyempurnakan tipe data dengan cara mengaitkannya dengan fungsi-fungsi yang beroprasi pada data yang bersangkutan. Merupakan hal yang sangat penting untuk mengenali bahwa operasi-operasi yang akan dimanipulasi data pada objek yang bersangkutan termuat dalam spesifikasi ADT. Sebagai contoh, ADT HIMPUNAN didefinisikan sebagai koleksi data yang diakses oleh operasi-operasi himpunan seperti penggabungan (UNION), irisan (INTERSECTION), dan selisih antar-himpunan (SET DIFFERENCE).


      Implementasi dari ADT harus menyediakan cara tertentu untuk merepresentasikan unsur tipe data (seperti matrix) dan cara untuk mengimplementasikan operasi -operasi matrix. Secara tipikal, kita akan mendeskripsikan operasi-operasi pada ADT dengan algoritma (logika berfikir) tertentu. Algoritma ini biasanya berupa urutan instruksi yang menspesifikasi secara tepat bagaimana operasi-operasi akan dilakukan/dieksekusi oleh computer

.
        Kita sekarang akan membahas lebih konkret tentang apa itu ADT. Pada dasarnya, ADT adalah tipe data tertentu yang didefinisikan oleh pemrogram untuk kemudahan pemrograman serta untuk mengakomodasi tipe-tipe data yang tidak secara spesifik diakomodasi oleh bahasa pemrograman yang digunakan. Maka, secara informal dapat dinyatakan bahwa ADT adalah :

1. Tipe data abstrak ADT pertama kali ditemukan oleh para ilmuan komputer utuk memisahkan struktur penyimpanan dari perilaku tipe data yang abstrak seperti misalnya, Tumpukan(Stack) serta antrian(Queue). Seperti kita duga, pemrogram tidak perlu tahu bagaimana Tumpukan(Stack) perubahan inplementasi ADT tidak mengubah program yang menggunakannya secara keseluruhan, dengan catatan bahwa interface ADT tersebut dengan ‘dunia luar’ tetap dipertahankan.

2. Pemakaian dan pembuatan ADT dapat dilakukan secara terpisah. yang perlu dibicarakan antara pembuat dan pengguna ADT adalah interface ADT yang bersangkutan.

3. ADT merupakan sarana pengembangan sistem yang bersifat modular, memungkinkan suatu sistem dikembangkan oleh beberapa orang anggota tim kerja dimana masing-masing anggota tim bisa melakukan bagiannya sendiri-sendiri dengan tetap mempertahankan keterpaduannya dengan anggota tim yang lain.

         Dalam hal ini perlu dibedakan antara pengertian struktur data dan ADT. Struktur data hanya memperlihatkan bagaimana data-data di organisir, sedangkan ADT bercakupan lebih luas, yaitu memuat/mengemas struktur data tertentu sekaligus dengan operasi-operasi yang dapat dilakukan pada struktur data tersebut. Dengan demikian, definisi umum tentang ADT di atas dapat diperluas sebagai berikut :

5.Jelaskan konsep Array dalam Stack

1. STACK DENGAN MENGGUNAKAN ARRAY
Pengertian Stack
• Stack atau tumpukan adalah suatu stuktur data yang penting dalam pemrograman
• Bersifat LIFO (Last In First Out)
• Benda yang terakhir masuk ke dalam stack akan menjadi benda pertama yang dikeluarkan dari stack
• Contohnya, karena kita menumpuk Compo di posisi terakhir, maka Compo akan menjadi elemen teratas dalam tumpukan. Sebaliknya, karena kita menumpuk Televisi pada saat pertama kali, maka elemen Televisi menjadi elemen terbawah dari tumpukan. Dan jika kita mengambil elemen dari tumpukan, maka secara otomatis akan terambil elemen teratas, yaitu Compo juga.
Operasi-operasi/fungsi Stack
• Push : digunakan untuk menambah item pada stack pada tumpukan paling atas
• Pop : digunakan untuk mengambil item pada stack pada tumpukan paling atas
• Clear : digunakan untuk mengosongkan stack
• IsEmpty : fungsi yang digunakan untuk mengecek apakah stack sudah kosong
• IsFull : fungsi yang digunakan untuk mengecek apakah stack sudah penuh
Stack with Array of Struct
• Definisikan Stack dengan menggunakan struct
• Definisikan MAX_STACK untuk maksimum isi stack
• Buatlah variabel array data sebagai implementasi stack secara nyata
• Deklarasikan operasi-operasi/function di atas dan buat implemetasinya
Deklarasi MAX_STACK
#define MAX_STACK 10 //hati-hati mulai dari 0 jadi 0-9
Deklarasi STACK dengan struct dan array data
typedef struct STACK{
int top;
char data[10][10]; //misalkan : data adalah array of string
//berjumlah 10 data, masing-masing string
//menampung maksimal 10 karakter
};
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!
• 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!
• Ilustrasi stack pada saat inisialisasi:
Fungsi IsFull
• Untuk memeriksa apakah stack sudah penuh?
• 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
• Ilustrasi:
Fungsi IsEmpty
• Untuk memeriksa apakah stack masih kosong?
• Dengan cara memeriksa top of stack, jika masih -1 maka berarti stack masih kosong!
• Program:
Fungsi Push
• Untuk memasukkan elemen ke stack, selalu menjadi elemen teratas stack
• Tambah satu (increment) nilai top of stack terlebih dahulu setiap kali ada penambahan elemen stack, asalkan stack masih belum penuh, kemudian isikan nilai baru ke stack berdasarkan indeks top of stack setelah ditambah satu (diincrement)
• Ilustrasinya:
Fungsi Pop
• Untuk mengambil elemen teratas dari stack.
• Ambil dahulu nilai elemen teratas stack dengan mengakses top of stack, tampilkan nilai yang akan diambil terlebih dahulu, baru didecrement nilai top of stack sehingga jumlah elemen stack berkurang
• Ilustrasinya:
Programnya:
Fungsi Print
• Untuk menampilkan semua elemen-elemen stack