TUMPUKAN & ANTRIAN (STACK & QUEUE) |
STACK (TUMPUKAN)Stack (tumpukan) sebenarnya secara mudah dapat diartikan sebagai list (urutan) dimana penambahan dan pengambilan elemen hanya dilakukan pada satu sisi yang disebut top (puncak) dari stack. Dengan melihat definisi tersebut maka jelas bahwa pada stack berlaku aturan LIFO (Last In First Out), yaitu elemen yang terakhir masuk akan pertama kali diambil atau dilayani. Salah satu analogi yang dapat dikemukakan di sini adalah tumpukan piring atau barang lain. Pada saat kita hendak menumpuk piring-piring tersebut tentulah yang kita lakukan adalah meletakkan piring pertama pada tempatnya, selsnjutnya meletakkan piring kedua di atas piring pertama dan demikian seterusnya. Pada saat kita hendak mengambil satu piring dari tumpukan tersebut, tentu yang diambil adalah piring teratas (yang terakhir kali ditaruh), bukan yang terbawah (yang pertama kali diletakkan). Dua operasi dasar pada stack adalah PUSH (operasi pemasukan elemen ke
dalam stack) dan POP (operasi pengambilan satu elemen dari dalam stack).
Di bawah ini diberikan contoh pemakaian operasi PUSH dan POP dan isi stack untuk
setiap selesai eksekusi satu operasi.
IMPLEMENTASI STACK DALAM BAHASA PASCALImplementasi dalam bahasa Pascal dapat dilakukan dengan memanfaatkan struktur data record dan array. Array dipergunakan untuk menyimpan elemen-elemen yang dimasukkan. Selain itu diperlukan pula suatu variabel untuk mencatat banyaknya elemen yang adadi dalam array yang sekaligus menunjukkan TOS. Pada implementasi di bawah ini:
type tumpukan = record banyak :0..maxelm; elemen : array[1..maxelm] of typeelemen; end;
Selain prosedur untuk POP dan PUSH, kita dapat pula menambahkan sejumlah fungsi untuk membantu penanganan kesalahan diantaranya adalah fungsi PENUHS (untuk mengecek apakah stack penuh) fungsi KOSONGS (untuk mengecek apakah stack kosong) dan fungsi SIZES (untuk mengetahui banyaknya elemen di dalam stack). Masing-masing sub program di atas dapat disajikan pseudocode-nya sebagai berikut: Procedure Inisialisasi(var S : tumpukan); begin S. banyak¬ 0 end; Function PENUHS(S : tumpukan): boolean; begin Jika S.banyak = maxelm maka PENUHS ¬ true else PENUHS ¬false end; Function KOSONGS(S : tumpukan):boolean; begin If S.banyak = 0 then KOSONGS ¬ true else KOSONGS¬false end; Procedure PUSH(data : tipeelemen; var S : tumpukan); begin If not KOSONGS(S) then begin
else Tampilkan pesan kesalahan "Stack Penuh" end; Procedure POP(var S : tumpukan; var data : typeelemen); begin If not KOSONGS(S) then begin
else Tampilkan pesan kesalahan "Stack kosong" End; QUEUE (ANTRIAN)Queue atau antrian sebenarnya juga merupakan suatu list. Salah satu sifat yang membedakan queue dengan stack adalah bahwa pada queue penambahan elemen dilakukan pada salah satu ujung (ujung depan) dan pengambilan dilakukan pada ujung yang lain (ujung belakang) . Dengan demikian queue menggunakan prinsip FIFO (First In First Out), yaitu elemen yang pertama masuk akan pertama kali pula dikeluarkan.
IMPLEMENTASI QUEUE DALAM BAHASA PASCALImplementasi dalam bahasa Pascal dapat dilakukan dengan memanfaatkan struktur data record dan array. Array dipergunakan untuk menyimpan elemen-elemen yang dimasukkan. Selain itu diperlukan pula suatu variabel untuk mencatat banyaknya elemen yang ada di dalam array. Pada implementasi di bawah ini:
type antrian= record banyak :0..maxelm; elemen : array[1..maxelm] of typeelemen; end;
Selain prosedur untuk ADDQ dan DELQ, kita dapat pula menambahkan sejumlah fungsi untuk membantu penanganan kesalahan diantaranya adalah fungsi PENUHQ (untuk mengecek apakah antrian penuh) fungsi KOSONGQ (untuk mengecek apakah antrian kosong) dan fungsi SIZEQ (untuk mengetahui banyaknya elemen di dalam queue). Masing-masing sub program di atas dapat disajikan pseudocode-nya sebagai berikut: Procedure Inisialisasi(var q : antrian); begin Q. banyak ¬ 0 end; Function PENUHQ(q : antrian): boolean; begin Jika Q.banyak = maxelm maka PENUHQ ¬ true else PENUHQ¬false end; Function KOSONGQ(q : antrian):boolean; begin If Q.banyak = 0 then KOSONGQ ¬ true else KOSONGQ ¬ false end; Procedure ADDQ(data : tipeelemen; var q : antrian); begin If not PENUHQ(Q) then begin
else Tampilkan pesan kesalahan "Antrian Penuh" end; Procedure DELQ(var q : antrian; var data : typeelemen); begin If not KOSONGS(Q) then begin
else Tampilkan pesan kesalahan "Antrian kosong" End; Dengan melihat implementasi di atas kita dapat merasakan adanya ketidakefisienan, yaitu bahwa untuk mengambil satu elemen dari queue kita harus menggeser sisa elemen yang sebenarnya tidak menjadi perhatian kita. Untuk data yang sedikit mungkin ini tidak terasa, tetapi untuk data yang banyak maka ketidakefisienan ini akan tampak jelas. Untuk mengatasi permasalahan di atas kita dapat menggunakan implementasi
queue berputar, yaitu dengan membiarkan sel tetap kosong bila elemen pada
sel tersebut baru saja diambil. Bagaimanakah implementasi queue berputar?
Perhatikan implementasi di bawah ini. type antrian_putar= record Field depan dan belakang masing-masing adalah untuk mencatat lokasi elemen terdepan (yang akan diambil berikutnya) dan lokasi elemen paling belakang (elemen terakhir kali masuk) Procedure ADDQ(data : tipeelemen; var q : antrian_putar); begin If not PENUHQ(Q) then begin
else Tampilkan pesan kesalahan "Antrian Penuh" end; Procedure DELQ(var q : antrian_putar; var data : typeelemen); begin If not KOSONGS(Q) then begin
else Tampilkan pesan kesalahan "Antrian kosong" End; TUGAS
|