1 of 23
QUEUE Definisi Queue (antrian) adalah list linier yang : ü elemen yang pertama kali masuk antrian disebut elemen depan (front/head of queue), sedangkan elemen yang terakhir kali masuk disebut elemen belakang (rear/tail of queue). ü merupakan salah satu contoh aplikasi dari double linked list, yaitu kumpulan data dengan penambahan data (elemen) hanya melalui satu sisi, yaitu belakang (tail) dan penghapusan data (elemen) hanya melalui sisi depan (head). Karena sifat keluar-masuknya elemen queue melalui kedua ujung queue, maka elemen-elemen pada kedua ujung barisan tersebut perlu diidentifikasi. ü satu elemen dengan elemen lain dapat diakses melalui informasi Next ü merupakan struktur data dinamis, ketika program dijalankan, jumlah elemennya dapat berubah secara dinamis sesuai keperluan. List linier/Linked List (senarai berantai) yaitu sekumpulan elemen bertype sama, yang mempunyai keterurutan tertentu, yang setiap elemennya terdiri dari 2 bagian. Linked List terdiri dari: ü Single Linked List pointer hanya dapat bergerak satu arah saja, maju/mundur, atau kanan/kiri sehingga pencarian data hanya dapat bergerak dalam satu arah saja. ü Double Linked List pointer dapat bergerak ke semua arah sehingga pencarian data dapat bergerak dalam berbagai arah. Struktur data ini banyak dipakai dalam informatika misalnya untuk merepresentasi: ü antrian job dalam sistem operasi ü antrian dalam dunia nyata.
Sifat Queue Mempunyai sifat FIFO (First In First Out), yaitu suatu metode pembuatan linked list dimana data yang masuk pertama akan keluar pertama juga dan data yang terakhir masuk akan keluar terakhir.
Operasi dan Fungsi Dasar pada Queue 1. Inisialisasi queue menjadi kosong (pembuatan queue kosong) membuat queue kosong diperlukan untuk memulai memakai queue. 2. Test Queue Kosong » mencari tahu status queue kosong atau tidak mengetahui bahwa queue kosong atau tidak sangat penting, sebab semua operasi akan dilakukan berdasarkan kosong atau tidaknya suatu queue. 3. Test Queue Penuh » mencari tahu status queue penuh atau tidak 4. Mencari panjang queue (jumlah elemen queue) 5. Penambahan sebuah elemen pada queue. penambahan selalu dilakukan pada ekor, dan karena alamat ekor diketahui maka prosesnya sederhana, yaitu hanya insert last. Susiana Sari
2 of 23 6. Clear menghapus elemen seluruh antrian 7. Penghapusan elemen pada queue. penghapusan elemen pada queue selalu dilakukan pada elemen pertama, hanya saja perlu diperhitungkan bahwa mungkin queue menjadi kosong akibat terjadinya penghapusan. Jika queue menjadi kosong, maka harga tail harus diganti. Jika akibat penghapusan queue tidak kosong, maka elemen terakhir tidak berubah.
Representasi Untuk mempermudah penulisan, di bawah ini isi queue tidak dituliskan secara bertumpuk, tetapi dengan kesepakatan: • elemen paling kanan adalah elemen yang ada pada ujung belakang (yang terakhir kali masuk) • queue yang dipakai bernama Q • ADDQ(B,Q) berarti memasukkan elemen B ke dalam queue Q • DELQ(B,Q) berarti mengambil elemen dari queue Q dan menaruhnya ke dalam variabel B Operasi yang dilakukan Isi Queue
Keterangan
Kondisi Awal
kosong
-
ADDQ('A',Q)
A
-
ADDQ('B',Q)
AB
-
ADDQ('C',Q)
ABC
-
DELQ(Data,Q)
BC
Variabel Data berisi 'A'
ADDQ('D',Q)
BCD
-
DELQ(Data,Q)
CD
Data berisi 'B'
POP(Data,S)
D
Data berisi 'C'
Implementasi Queue dalam bahasa Pascal Untuk membuat aplikasi antrian dapat menggunakan 2 metoda : 1. Array a. Linear Array b. Circular Array 2. Linked List
Susiana Sari
3 of 23 IMPLEMENTASI QUEUE DENGAN ARRAY A. IMPLEMENTASI QUEUE DENGAN LINEAR ARRAY Linear Array adalah suatu array yang dibuat seakan-akan merupakan suatu garis lurus dengan satu pintu masuk dan satu pintu keluar. Dengan adanya 2 pintu, Sehingga membutuhkan variabel Head dan Tail. Gambar berikut menunjukkan model penyajian antrian dengan linier array : depan (Head)
Keluar
1
2
Belakang (Tail) max=5
3
4
5
masuk
Berikut diberikan penggalan konstanta, type dan variabel yang akan dipakai untuk menjelaskan operasi-operasi dalam queue linear array. Const MaxQueue = 5; Type TypeQueue = byte; Var Queue : array[1..MaxQueue] of TypeQueue; Head, Tail : Byte; Operasi-operasi pada queue dengan linear array : 1. Create Procedure Create berguna untuk menciptakan Queue yang baru dan kosong yaitu dengan cara memberikan nilai awal (head) dan nilai akhir (tail) dengan 0(nol). Nol menunjukkan bahwa queue(antrian) masih kosong. Berikut penggalan procedure create. Procedure create; Begin Head := 0; Tail := 0; End; 2. IsEmpty Function IsEmpty berguna untuk mengecek apakah Queue masih kosong atau sudah berisi data. Hal ini dilakukan dengan mengecek apakah tail bernilai nol atau tidak, jika nol maka kosong. Berikut penggalan function IsEmpty : Function IsEmpty : Boolean; Begin If Tail = 0 then IsEmpty := true Else IsEmpty := false; End; Susiana Sari
4 of 23 3. IsFull Function IsFull berguna untuk mengecek apakah Queue sudah penuh atau masih bisa menampung data dengan cara mengecek apakah nilai tail sudah sama dengan jumlah maksimal queue, jika nilai keduanya sama maka penuh. Berikut penggalan function full: Function IsFull : Boolean; Begin If Tail = MaxQueue then IsFull := true Else IsFull := false; End; 4. EnQueue Procedure EnQueue berguna untuk memasukkan 1 elemen ke dalam Queue. Berikut penggalan procedure enqueue. Procedure enqueue(elemen : byte); Begin If IsEmpty then Begin Head := 1; Tail := 1; Queue [Head] := elemen; End; End; 5. DeQueue Procedure DeQueue berguna untuk mengambil 1 elemen dari queue, operasi ini sering disebut SERVE. Hal ini dilakukan dengan cara memindahkan semua elemen satu langkah ke posisi di depannya, sehingga otomatis elemen yang paling depan akan tertimpa dengan elemen yang terletak di belakangnya. Berikut penggalan procedure DeQueue. Procedure DeQueue; Var i : byte; Begin If not IsEmpty then Begin For i := Head to Tail-1 do Queue [i] := queue [i-1]; Dec(tail); End; End;
Susiana Sari
5 of 23 6. Clear Procedure Clear berguna untuk menghapus semua elemen dalam queue dengan jalan mengeluarkan semua elemen tersebut satu per satu sampai kosong dengan memanfaatkan procedure dequeue. Berikut penggalan procedure clear. Procedure clear; Begin While not IsEmpty then DeQueue; End; B. IMPLEMENTASI QUEUE DENGAN CIRCULAR ARRAY Circular Array adalah suatu array yang dibuat seakan-akan merupakan sebuah lingkaran dengan titik awal(head) dan titik akhir (tail) saling bersebelahan jika array tersebut masih kosong. Gambar berikut menunjukkan model penyajian antrian dengan circular array :
head := 1; tail := Max_Queue;
posisi head dan tail pada gambar di atas adalah bebas asalkan saling bersebelahan. Operasioperasi yang terdapat pada circular array tidak berbeda jauh dengan operasi pada linear array. Implementasi dengan array melingkar merupakan model yang tepat untuk mengatasi inefisiensi penggunaan ruang array pada model linear. Array dapat dipandang sebagai sebuah lingkaran. Apabila posisi terakhir dari array sudah digunakan dan posisi pertama dari array sudah tidak digunakan lagi, maka elemen queue berikutnya dapat diletakkan mulai posisi pertama lagi. Untuk mengimplementasikan array melingkar dari sebuah array linear, posisiposisi yang mengelilingi lingkaran diberi nomor dari 1 s.d maks., sama dengan indeks dari array linear. Pergeseran atau kenaikan indeks dilakukan dengan operasi aritmetika modulo (pembagian bilangan bulat). Ketika nilai indeks melebihi maks, maka dimulai lagi dari 1. operasi modulo mirip operasi pada sebuah jam, dengan angka 1 s.d 12. bila kita mengggeser empat jam dari jam 10, maka kita akan mencapai jam 2. Operasi-operasi queue dengan circular array : 1. Create Procedure Create berguna untuk menciptakan Queue yang baru dan kosong yaitu dengan cara memberikan nilai awal (head) dengan satu(1) dan nilai akhir (tail) dengan jumlah maksimal data yang akan ditampung/array. Berikut penggalan procedure create. Procedure create; Begin Head := 1; Tail := Max_Queue; End; Susiana Sari
6 of 23 2. IsEmpty Function IsEmpty berguna untuk mengecek apakah Queue masih kosong atau sudah berisi data. Hal ini dilakukan dengan mengecek apakah tail masih terletak bersebelahan dengan head, dan tail LEBIH BESAR head atau tidak, jika benar maka kosong. Berikut penggalan function IsEmpty : Function IsEmpty : Boolean; Begin If (Tail mod max_queue) + 1 = head then IsEmpty := true Else IsEmpty := false; End; 3. IsFull Function IsFull berguna untuk mengecek apakah Queue sudah penuh atau masih bisa menampung data dengan cara mengecek apakah tempat yang masih kosong tinggal satu atau tidak (untuk membedakan dengan IsEmpty dimana semua tempat kosong), jika ya maka kosong. Berikut penggalan function IsFull: Function Isfull : Boolean; Var X : 1..Max_Queue; Begin X := (Tail mod Max_Queue) + 1; If (x mod Max_Queue) + 1 = head then IsFull := true Else isFull := false; End; 4. EnQueue Procedure EnQueue berguna untuk memasukkan 1 elemen ke dalam Queue. (tail dan head mula-mula adalah nol (0) ) Berikut penggalan procedure EnQueue. Procedure EnQueue(elemen : TypeElemen); Begin If not IsFull then Begin Tail := (tail mod Max_Queue) + 1; Queue [Tail] := elemen; End; End; 5. DeQueue Procedure DeQueue berguna untuk mengambil 1 elemen dari queue. Hal ini dilakukan dengan cara memindahkan posisi head satu langkah ke belakang. Berikut penggalan procedure dequeue. Procedure dequeue; Begin If not IsEmpty then Head := (head mod max_queue) + 1 End; Susiana Sari
7 of 23 C. IMPLEMENTASI QUEUE DENGAN DOUBLE LINKED LIST Selain menggunakan array, queue juga dapat dibuat dengan linked list. Metode linked list yang digunakan adalah double linked list. Berikut penggalan tipe konstanta dan variabel yang akan digunakan dalam penjelasan operasi-operasi queue dengan linked list. Type point = ^simpul; simpul = record isi : tipedata; next : point; end; queue = record head : point; tail : point; end; Var Q :Queue ; N : 0..Max_Queue; {jumlah antrian}
Operasi-operasi pembuatan queue dengan double linked list : 1. Create Procedure Create berguna untuk menciptakan Queue yang baru dan kosong yaitu dengan cara mengarahkan pointer head dan tail kepada nil. Berikut penggalan procedure create. Procedure create; Begin q.Head := nil; q.Tail := q.head; n := 0; End; 2. IsEmpty Function IsEmpty berguna untuk mengecek apakah Queue masih kosong atau sudah berisi data. Hal ini dilakukan dengan mengecek apakah head masih menunjuk pada nil atau tidak, jika ya maka kosong. Berikut penggalan function IsEmpty : Function IsEmpty : Boolean; Begin If q.head = nil then isEmpty := true Else IsEmpty := false; End;
Susiana Sari
8 of 23 3. IsFull Function IsFull berguna untuk mengecek apakah Queue sudah penuh atau masih bisa menampung data dengan cara mengecek apakah N (jumlahQueue) sudah sama dengan max_Queue atau belum, jika ya maka penuh. Berikut penggalan function IsFull: Function Isfull : Boolean; Begin if n = Max_Queue then IsFull := true Else IsFull := false; End; 4. EnQueue Procedure Enqueue berguna untuk memasukkan 1 elemen ke dalam Queue. (tail dan head mula-mula menunjuk ke null) Berikut penggalan procedure enqueue.
Procedure enqueue (elemen : TypeData); Var now : point; Begin If not Isfull then Begin New (now); Now^.isi := elemen; Now^.next := nil; If IsEmpty then Begin q.head := now; q.tail := now; n := 1; end else begin q.tail^.next := now; q.tail := now; inc(n); end; End; End;
Susiana Sari
9 of 23 5. Dequeue Procedure Dequeue berguna untuk mengambil 1 elemen dari queue. Hal ini dilakukan dengan cara menghapus satu simpul yang terletak paling depan(head). Berikut penggalan procedure dequeue. Procedure dequeue; Var now : point; Begin If not IsEmpty then Begin Now := q.head; q.head := q.head^.next; dispose (now); dec(n); End; End;
Perbedaan Queue dan Stack Perbedaan stack dan queue terdapat pada: ü aturan penambahan dan penghapusan elemen. Pada stack, operasi penambahan dan penghapusan elemen dilakukan di satu tempat atau satu ujung. Elemen yang terakhir kali dimasukkan akan berada paling dekat dengan ujung atau dianggap paling atas sehingga pada operasi penghapusan, elemen teratas tersebut akan dihapus paling awal. Pada queue, operasi tersebut dilakukan di tempat yang berbeda. Penambahan elemen selalu dilakukan melalui salah satu ujung, menempati posisi di belakang elemen-elemen yang sudah masuk sebelumnya atau menjadi elemen belakang, sedangkan penghapusan elemen dilakukan di ujung yang berbeda, yaitu pada posisi elemen yang masuk paling awal atau elemen depan dibanding elemen-elemen lain. ü Stack dengan single linked list, sedangkan queue dengan double linked list. stack dapat diimplementasikan dengan single linked list. Keunggulannya dibandingkan array adalah penggunaan alokasi memori yang dinamis sehingga menghindari pemborosan memori. Misalnya pada stack dengan array disediakan tempat untuk stack berisi 150 elemen, sementara ketika dipakai oleh user stack hanya diisi 50 elemen, maka telah terjadi pemborosan memori untuk sisa 100 elemen, yang tak terpakai. Dengan penggunaan linked list maka tempat yang disediakan akan sesuai dengan banyaknya elemen yang mengisi stack. Dalam stack dengan linked list tidak ada istilah full, sebab biasanya program tidak menentukan jumlah elemen stack yang mungkin ada (kecuali jika sudah dibatasi oleh pembuatnya). Namun demikian sebenarnya stack ini pun memiliki batas kapasitas, yakni dibatasi oleh jumlah memori yang tersedia.
Salah satu kelemahan single linked list adalah pointer (penunjuk) hanya dapat bergerak satu arah saja, maju/mundur, atau kanan/kiri sehingga pencarian data pada single linked list hanya dapat bergerak dalam satu arah saja. Untuk mengatasi kelemahan tersebut, dapat menggunakan metode double linked list. Linked list ini dikenal dengan nama Linked list berpointer Ganda atau Double Linked List..
Susiana Sari
10 of 23
Contoh Aplikasi Queue PROGRAM QUEUE01; uses crt; const MAX=50; type larik = Array[0..MAX] of char; RecQueue = RECORD info : larik; awal : integer; akhir : integer; END; var antri : RecQueue; pilih,elm : char; procedure init; begin antri.awal := 0; antri.akhir := 0; end; function Isfull:boolean; begin if antri.akhir = MAX then Isfull := true else Isfull := false; end; function IsEmpty:boolean; begin if antri.akhir = 0 then Isempty := true else Isempty := false; end; procedure baca; var i:integer; begin writeln('Isi queue sekarang : '); for i := antri.awal to antri.akhir do write(antri.info[i], ' '); writeln(''); end;
procedure inQueue(elemen:char); begin Susiana Sari
11 of 23 if Isempty = true then begin antri.awal := 1; antri.akhir:= 1; antri.info[antri.awal] := elemen; end else if Isfull <> true then begin antri.akhir := antri.akhir + 1; antri.info[antri.akhir]:=elemen; end else writeln('Queue overflow...'); end; function deQueue:char; var isi:char; i : integer; begin if Isempty <> true then begin isi := antri.info[antri.awal]; for i:=antri.awal to antri.akhir - 1 do antri.info[i] := antri.info[i+1]; antri.akhir := antri.akhir - 1; deQueue := isi; end else writeln('Queue underflow...'); end; BEGIN CLRSCR; writeln('--- Demo Queue dg Linear Array ---'); init; repeat writeln('OPERASI QUEUE dg Linear Array :'); writeln('[1] InQueue (Insert Queue)'); writeln('[2] DeQueue (Delete Queue)'); writeln('[3] Baca'); writeln('[4] Selesai...'); write(' Pilihan : '); readln(pilih); case pilih of '1' : begin write('Antrian Masuk : '); readln(elm); inQueue(elm); end; '2' : begin Susiana Sari
12 of 23 elm:=deQueue; writeln(elm,' Keluar dr antrian'); end; '3' : baca; '4' : writeln('Wakarimasuta (?_?)'); else writeln('Salah pilih...'); end; writeln(''); until (pilih = '4'); readln; END.
Program Antri1; Uses crt; Const Max = 10; Type Node = ^Queue; Queue = Record Kar : Char; Next : Node; End; Var Pil : char; Jml : byte; Head, now, tail : node; Procedure Push(ch : char); {membuat node} Begin New(Now); If Head = NIL then Head := Now; Else Tail^.Next := Now; Tail := Now; Tail^.Next := NIL; Now^.Kar := ch; End; Procedure Pop; {menghapus simpul} Begin Now := Head; Head := Head^.Next; Dispose(Now); End; Procedure EnQueue; {mengisi antrian} Var I : byte; Temp : char; Begin GotoXY(1,6); Clreol;Write(‘MASUKKAN @ KARAKTER : ‘); Susiana Sari
13 of 23 Repeat GotoXY(25,6); Clreol;Temp := Readkey;Write(Temp); Until Temp <>’ ‘; Push(Temp); For I := 1 to 75 – Jml * 6 do {animasi mengisi antrian} Begin GotoXY(I+1,20); Write(‘ o’); GotoXY(I,21);Write(‘=(‘, Now^.Kar,‘)=’); GotoXY(I+1,22);Write(‘/ \’);Delay(10); If I <> 75 – Jml * 6 then Begin GotoXY(I+1,20);Write(‘ ‘); GotoXY(I,21);Write(‘ ‘); GotoXY(I+1,22);Write(‘ ‘); End; End; End; Procedure DeQueue; {mengeluarkan antrian} Var I, Byk : byte; Begin Now := Head; For I := 69 to 76 do {animasi mengeluarkan antrian} Begin GotoXY(I+1,20);Write(‘ o‘); GotoXY(I,21);Write(‘=( ‘,Now^.Kar,’)= ‘); GotoXY(I+1,22);Write(‘/ \‘);Delay(10); GotoXY(I+1,20);Write(‘ ‘); GotoXY(I,21);Write(‘ ‘); GotoxXY(I+1,22);Write(‘ ‘); End; Byk := 0; While Byk <> Jml do Begin Inc(Byk); Now := Now^.Next; For I := 69 – Byk * 6 to 75 – Byk * 6 do {animasi memajukan} Begin GotoXY(I+1,20);Write(‘ o‘); GotoXY(I,21);Write(‘=( ‘,Now^.Kar,’)= ‘); GotoXY(I+1,22);Write(‘/ \‘);Delay(25); If I <> 75 – Byk * 6 then Begin GotoXY(I+1,20);Write(‘ ‘); GotoXY(I,21);Write(‘ ‘); GotoXY(I+1,22);Write(‘ ‘); End; End; End; End; Susiana Sari
14 of 23 Procedure Input; {membuat menu} Begin GotoXY(1,1);Writeln(‘1. ENQUEUE ‘); GotoXY(1,2);Writeln(‘2. DEQUEUE ‘); GotoXY(1,3);Writeln(‘3. EXIT ‘); Repeat Repeat GotoXY(1,4);Clreol;Write(‘YOUR CHOICE : ‘); Pil := Readkey;Write(Pil); Until Pil in [‘1’, ‘2’, ‘3’]; Case Pil of ‘1’ : Begin {menambah pengantri} If Jml < Max then Begin Inc(Jml); EnQueue; end else Begin GotoXY(1,8);Write(‘ANTRIAN PENUH !’);Delay(500); GotoXY(1,8);Clreol; End; End; ‘2’ : Begin {mengeluarkan pengantri} If Jml >= 1 then Begin Dec(Jml); DeQueue; Pop; end else Begin GotoXY(1,8);Write(‘ANTRIAN KOSONG!’);Delay(500); GotoXY(1,8);Clreol; End; End; End; Until Pil = ‘3’; {keluar dari program} End; Begin {program utama} Jml := 0; Clrscr; Input; End. Program Antri2; Uses crt; Type Point = ^Rec; Susiana Sari
15 of 23 Rec = Record Isi : Char; Next : Point; end; Queue = Record; Head : Point; Tail : Point; end; Var Q I, K
: Queue; : Byte; {i = tinggi_stack}
Procedure GambarPipa; {membentuk pipa antrian} Var Y : Byte; Begin GotoXY(39,8);Write(‘\ /’); For Y := 1 to 10 do Begin GotoXY(40,Y+8);Write(‘|’); GotoXY(46,Y+8);Write(‘|’); end; GotoXY(40,19);Write(‘|_| |_|’); GotoXY(61,21);Write(‘\’); GotoXY(61,23);Write(‘/’); end; Function IsEmpty : Boolean; {fungsi cek antri kosong} Begin If Q.Head = NIL then IsEmpty := True Else IsEmpty := False; end; Function IsFull : Boolean; {fungsi cek antrian penuh} Begin If 1 = 10 then IsFull := True Else IsFull := False; end; Procedure EnQueue; {prosedur menambah pengantri} Var Now : Point; Begin If IsFull then Begin GotoXY(1,6); Write(‘QUEUE SUDAH PENUH......‘); Delay(200); Susiana Sari
16 of 23 GotoXY(1,6); Clreol; end else Begin New(Now); GotoXY(1,7); Clreol;Write(‘MASUKKAN SATU HURUF = ‘); Now^Isi := Readkey;Write(Now^.Isi); Now^.Next := NIL; For K := 1 to 20 do {animasi mengisi antrian} Begin GotoXY(K+22,7);Write(‘ ‘); GotoXY(K+23,7);Write(Now^.Isi);Delay(10); end; For K := 1 to 11-I do Begin GotoXY(43,K+6);Write(‘ ‘); GotoXY(43,K+7);Write(Now^.Isi);Delay(10); end; Inc(I); GotoXY(1,7);Clreol; If IsEmpty then Begin Q.Head := Now; Q.Tail := Now; end else Begin Q.Tail^.Next := Now; Q.Tail := Now; end; end; end; Procedure DeQueue; {prosedur mengurangi antrian} Var U : Byte; Now : Point; Begin If IsEmpty then Begin GotoXY(1,6);Write(‘QUEUE KOSONG.......‘); Delay(200); GotoXY(1,6);Clreol; end else Begin For K := 19 to 22 do {animai mengeluarkan pengantri} Begin GotoXY(43,K-1);Write(‘ ‘); GotoXY(43,K);Write(Q.Head^.Isi);Delay(10); end; For K := 43 to 63 do Begin GotoXY(K,22);Write(‘ ‘); Susiana Sari
17 of 23 GotoXY(K+1,22); Write(Q.Head^.Isi);Delay(10); end; Now := Q.Head; Q.Head := Q.Head^.Next; Dispose(Now); Dec(I); Now := Q.Head; K := 18; While Now <> NIL do Begin GotoXY(43,K);Write(Now^.Isi); Now := Now^.Next; Dec(K); end; GotoXY(43,K);Write(‘ ‘); Sound(1000);Delay(200);NoSound; end; end; Procedure Create; {memberi nilai antrian awal} Begin Q.Head := NIL; Q.Tail := NIL; end; Procedure Clear; {mengosongkan antrian} Begin While not IsEmpty do DeQueue; end; Procedure Menu; {tampilan menu} Var Jwb : Char; Begin I := 0; GotoXY(1,2);Writeln(‘1. ENQUEUE ‘); GotoXY(1,3);Writeln(‘2. DEQUEUE ‘); GotoXY(1,4);Writeln(‘3. EXIT ‘); Create; Repeat GotoXY(1,5);Clreol;Write(‘PILIHAN [ 1 / 2 / 3 ] : ‘); Jwb := Readkey;Write(Jwb); Case Jwb of ‘1’ : EnQueue; {menambah antrian} ‘2’ : DeQueue ; {mengurangi antrian} end; Until Jwb = ‘3’; {keluar dari program} Clear; end; Begin {main program} Susiana Sari
18 of 23 Clrscr; GambarPipa; Menu; End.
Susiana Sari
19 of 23 Perbandingan Queue Dengan Linked List VS Queue Dengan Array Implementasi queue menggunakan array • Implementasi sederhana • Ukuran memori harus ditentukan ketika sebuah objek queue dideklarasikan • Pemborosan tempat (memori) ketika menggunakan jumlah data yang lebih sedikit dari alokasi memori • Tidak dapat menambahkan data melebihi maksimal ukuran array yang telah dideklarasikan Implementasi queue menggunakan linked list • Pengalokasian memori dinamis • Menggunaka 2 buah pionter, qFront dan qRear, untuk menandai posisi depan dan belakang dari queue
Perbandingan implementasi queue, array VS linked list (contoh 1) • Memory requirements – Array-based implementation • Diasumsikan ukuran queue 100 (string @80bytes) • Diasumsikan index membutuhkan 2 bytes • Total memory: (80 bytes x 101 slots) + (2 bytes x 2 indexes) = 8084 bytes – Linked-list-based implementation • Diasumsikan pointers membutuhkan 4 bytes • Total memory per node: 80 bytes + 4 bytes = 84 bytes Gambar :
Susiana Sari
20 of 23 Perbandingan implementasi queue, array VS linked list (contoh 2) • Memory requirements – Array-based implementation • Diasumsikan ukuran queue 100 (string @2bytes) • Diasumsikan index membutuhkan 2 bytes • Total memory: (2 bytes x 101 slots) + (2 bytes x 2 indexes) = 206 bytes – Linked-list-based implementation • Diasumsikan pointers membutuhkan 4 bytes • Total memory per node: 2 bytes + 4 bytes = 6 bytes Gambar :
PEMBAHASAN 1. INPUT PROGRAM a. PROGRAM ANTRI1 Program antri1 merupakan program animasi antrian. Dalam program tersebut terdapat 3 pilihan yaitu ENQUEUE, DEQUEUE dan EXIT. Jika ENQUEUE dipilih, maka user akan diminta menginput sebuah character yang akan langsung ditampilkan. Jika ENQUEUE dipilih lagi, character baru akan ditambahkan dibelakang character sebelumnya. Kalau terpilih DEQUEUE maka karaklter terdepan akan menghilang dan character-character di belakangnya akan maju. Jika dipilih exit maka program akan selesai. b. PROGRAM ANTRI2 Program antri2 adalah program yang akan menggambarkan suatu antrian. Dimana terdapat 3 pilihan yaitu ENQUEUE, DEQUEUE dan EXIT. Jika dipilih ENQUEUE, maka user diminta menginputkan character. Dalam proses menginputkan character tersebut Susiana Sari
21 of 23 terdapat animasi yaitu character tersebut memasuki tempat antrian. Jika dipilih DEQUEUE, maka animasi character terdepan keluiar dari antrian. Jika dipilih exit, maka program akan selesai. 2. OUTPUT PROGRAM a. ANTRI1 Output Program apabila kita memilih angka 1 yaitu ENQUEUE :
Output Program apabila kita memilih angka 2 yaitu DEQUEUE
Output Program apabila kita memilih angka 3 yaitu EXIT
Susiana Sari
22 of 23
b. ANTRI2 Output Program apabila kita memilih angka 1 yaitu ENQUEUE
Output Program apabila kita memilih angka 2 yaitu DEQUEUE
Susiana Sari
23 of 23
Output Program apabila kita memilih angka 3 yaitu EXIT
DAFTAR PUSTAKA
Sismoro, Heri S.Kom Dan Kusrini Iskandar, S.Kom, 2004, Struktur Data Dan Pemrograman Dengan Pascal, Yogyakarta : Andi Offset Sanjaya, Dwi, 2001, Bertualang Dengan Struktur Data Di Planet Pascal, Yogyakarta : J & J Learning. http://www.khabib.staff.ugm.ac.id/index.php?option=com_content&task=view&id=84&Itemi d=33
Susiana Sari
