Stack and Queue

Stack and Queue
TUMPUKAN & ANTRIAN (STACK &QUEUE)

STACK (TUMPUKAN)
Stack (tumpukan) sebenarnyasecaramudahdapatdiartikansebagailist (urutan) dimanapenambahandanpengambilanelemenhanyadilakukanpadasatusisi yang disebuttop (puncak)dari stack.
Denganmelihatdefinisitersebutmakajelasbahwapada stack berlakuaturan LIFO (Last In First Out), yaituelemen yang terakhirmasukakanpertama kali diambilataudilayani. Salah satuanalogi yang dapatdikemukakan di siniadalahtumpukanpiringataubarang lain. Padasaatkitahendakmenumpukpiring-piringtersebuttentulah yang kitalakukanadalahmeletakkanpiringpertamapadatempatnya, selsnjutnyameletakkanpiringkedua di ataspiringpertamadandemikianseterusnya. Padasaatkitahendakmengambilsatupiringdaritumpukantersebut, tentu yang diambiladalahpiringteratas (yang terakhir kali ditaruh), bukan yang terbawah (yang pertama kali diletakkan).
Duaoperasidasarpada stack adalahPUSH (operasipemasukanelemenkedalam stack) danPOP (operasipengambilansatuelemendaridalam stack). Di bawahinidiberikancontohpemakaianoperasi PUSH dan POP danisi stack untuksetiapselesaieksekusisatuoperasi.
(Untukmempermudahpenulisan, di bawahiniisi stack tidakdituliskansecarabertumpuk, tetapidengankesepakatan:
  • elemen paling kananadalahelemen yang adapada TOS (Top Of the Stack)
  • stack yang dipakaibernama S
  • PUSH(S,B) berartimemasukkanelemen B kedalam stack S
  • POP(B,S) berartimengambilelemendari stack S danmenaruhnyakedalamvariabel B
Operasi yang dilakukan
Isi Stack
Keterangan
KondisiAwal
kosong
-
PUSH('A',S)
A
-
PUSH('B',S)
AB
-
PUSH('C',S)
ABC
-
POP(Data,S)
AB
VariabelDataberisi 'C'
PUSH('D',S)
ABD
-
POP(Data,S)
AB
Databerisi 'D'
POP(Data,S)
A
Databerisi 'B'
keatashalaman   
IMPLEMENTASI STACK DALAM BAHASA PASCAL
Implementasidalambahasa Pascal dapatdilakukandenganmemanfaatkanstruktur data record dan array. Array dipergunakanuntukmenyimpanelemen-elemen yang dimasukkan. Selainitudiperlukan pula suatuvariabeluntukmencatatbanyaknyaelemen yang adadidalam array yang sekaligusmenunjukkan TOS. Padaimplementasi di bawahini:
  • konstantamaxelmmenyatakanbanyaknyaelemenmaksimum yang dapatditampungoleh stack
  • typeelemenadalahtipe data yang akandisimpan di dalam stack (bisa integer, word, real, boolean, char , string ataulainya)
  • banyakadalah field yang menyatakanbanyaknyaelemendalam stack saatitu, yang sekaligusmenyatakan TOS
Deklarasitipeuntuktumpukan (stack):
type tumpukan = record
   banyak :0..maxelm;
   elemen : array[1..maxelm] of typeelemen;
end;
Selainproseduruntuk POP dan PUSH, kitadapat pula menambahkansejumlahfungsiuntukmembantupenanganankesalahandiantaranyaadalahfungsiPENUHS (untukmengecekapakah stack penuh) fungsiKOSONGS (untukmengecekapakah stack kosong) danfungsiSIZES (untukmengetahuibanyaknyaelemen di dalam stack). Masing-masing sub program di atasdapatdisajikanpseudocode-nyasebagaiberikut:
Procedure Inisialisasi(var S : tumpukan);
begin
  S. banyak¬ 0
end;
Function PENUHS(S : tumpukan): boolean;
begin
 JikaS.banyak = maxelmmaka 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
  1. S.banyak ¬ S.banyak +1
  2. S.elemen[S.banyak]¬data
 end
 else
   Tampilkanpesankesalahan "Stack Penuh"
end;
Procedure POP(var S : tumpukan; var data : typeelemen);
begin
 If not KOSONGS(S) then
 begin
  1. data¬S.elemen[S.banyak]
  2. S.banyak ¬ S.banyak - 1
 end
 else
   Tampilkanpesankesalahan "Stack kosong"
End;
keatashalaman    ke menu utama
QUEUE (ANTRIAN)
Queue atauantriansebenarnyajugamerupakansuatu list. Salah satusifat yang membedakan queue dengan stack adalahbahwapada queue penambahanelemendilakukanpadasalahsatuujung (ujungdepan) danpengambilandilakukanpadaujung yang lain (ujungbelakang) . Dengandemikian queue menggunakanprinsipFIFO (First In First Out), yaituelemen yang pertamamasukakanpertama kali pula dikeluarkan.
Sepertipada stack, operasi-operasidasarpada queue adalahoperasipenambahanelemen ( sebut "ADDQ") danoperasipengambilanelemen (sebut DELQ). Di bawahinidiberikancontohpemakaianoperasi PUSH dan POP danisi stack untuksetiapselesaieksekusisatuoperasi.
(Untukmempermudahpenulisan, di bawahiniisi queue tidakdituliskansecarabertumpuk, tetapidengankesepakatan:
  • elemen paling kananadalahelemen yang adapadaujungbelakang (yang terakhir kali masuk)
  • queue yang dipakaibernama Q
  • ADDQ(Q,B) berartimemasukkanelemen B kedalam queue Q
  • DELQ(B,Q) berartimengambilelemendari queue Q danmenaruhnyakedalamvariabel B
Operasi yang dilakukan
Isi Queue
Keterangan
KondisiAwal
kosong
-
ADDQ('A',Q)
A
-
ADDQ('B',Q)
AB
-
ADDQ('C',Q)
ABC
-
DELQ(Data,Q)
BC
VariabelDataberisi 'A'
ADDQ('D',Q)
BCD
-
DELQ(Data,Q)
CD
Databerisi 'B'
POP(Data,S)
D
Databerisi 'C'
keatashalaman   
IMPLEMENTASI QUEUE DALAM BAHASA PASCAL
Implementasidalambahasa Pascal dapatdilakukandenganmemanfaatkanstruktur data record dan array. Array dipergunakanuntukmenyimpanelemen-elemen yang dimasukkan. Selainitudiperlukan pula suatuvariabeluntukmencatatbanyaknyaelemen yang ada di dalam array. Padaimplementasi di bawahini:
  • konstantamaxelmmenyatakanbanyaknyaelemenmaksimum yang dapatditampungoleh queue
  • typeelemenadalahtipe data yang akandisimpan di dalam queue(bisa integer, word, real, boolean, char , string ataulainya)
  • banyakadalah field yang menyatakanbanyaknyaelemendalam queue saatitu
  • queue diimplementasikansebagai array linier denganmemandangbahwaelementerdepanselaluberadapadaselpertama (implementasifisik), sehinggabilaterjadipengambilansatuelemenmakasemuaelemen di belakangelementerambil (bilaada) harusdigeserkedepansatulangkah
Deklarasitipeuntukantrian (queue):
type antrian= record
   banyak :0..maxelm;
   elemen : array[1..maxelm] of typeelemen;
end;
Selainproseduruntuk ADDQ dan DELQ, kitadapat pula menambahkansejumlahfungsiuntukmembantupenanganankesalahandiantaranyaadalahfungsiPENUHQ (untukmengecekapakahantrianpenuh) fungsiKOSONGQ (untukmengecekapakahantriankosong) danfungsiSIZEQ (untukmengetahuibanyaknyaelemen di dalam queue). Masing-masing sub program di atasdapatdisajikanpseudocode-nyasebagaiberikut:
Procedure Inisialisasi(var q : antrian);
begin
  Q. banyak ¬ 0
end;
Function PENUHQ(q : antrian): boolean;
begin
 JikaQ.banyak = maxelmmaka 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
  1. Q.banyak¬ Q.banyak+1
  2. Q.elemen[Q.banyak] ¬ data
 end
 else
   Tampilkanpesankesalahan "AntrianPenuh"
end;
Procedure DELQ(var q : antrian; var data : typeelemen);
begin
 If not KOSONGS(Q) then
 begin
  1. data ¬Q.elemen[1]
  2. for i:= 2 to Q.banyak
    Q.elemen[i-1] ¬ Q.elemen[i]
  3. Q.banyak ¬ Q.banyak- 1
 end
 else
   Tampilkanpesankesalahan "Antriankosong"
End;
keatashalaman   
Denganmelihatimplementasi di ataskitadapatmerasakanadanyaketidakefisienan, yaitubahwauntukmengambilsatuelemendari queue kitaharusmenggesersisaelemen yang sebenarnyatidakmenjadiperhatiankita. Untuk data yang sedikitmungkininitidakterasa, tetapiuntuk data yang banyakmakaketidakefisienaniniakantampakjelas.
Untukmengatasipermasalahan di ataskitadapatmenggunakanimplementasiqueue berputar, yaitudenganmembiarkanseltetapkosongbilaelemenpadaseltersebutbarusajadiambil. Bagaimanakahimplementasi queue berputar? Perhatikanimplementasi di bawahini.
type antrian_putar= record
   depan,belakang,banyak :0..maxelm;
   elemen : array[1..maxelm] of typeelemen;
end;
Field depandanbelakangmasing-masingadalahuntukmencatatlokasielementerdepan (yang akandiambilberikutnya) danlokasielemen paling belakang (elementerakhir kali masuk)
Procedure ADDQ(data : tipeelemen; var q : antrian_putar);
begin
 If not PENUHQ(Q) then
 begin
  1. Q.belakang ¬ (Q.belakang mod maxelm)+1
  2. Q.elemen[Q.belakang] ¬ data
 end
 else
   Tampilkanpesankesalahan "AntrianPenuh"
end;
Procedure DELQ(var q : antrian_putar; var data : typeelemen);
begin
 If not KOSONGS(Q) then
 begin
  1. data ¬ Q.elemen[Q.depan]
  2. Q.banyak ¬ Q.banyak- 1
  3. Q.depan ¬ (Q.depan mod maxelm)+1
 end
 else
   Tampilkanpesankesalahan "Antriankosong"

End;


Sumber : KhabibMustofa, Dr. techn.

0 komentar:

Posting Komentar

Langganan: Postingan (Atom)