laporan pratikum 5
TRANSCRIPT
LAPORAN PRAKTIKUM
ALGORITMA DAN STRUKTUR DATA
QUEUE
Disusun Oleh :
Nama : Fauzul Adhim
NIM : 110533430541
Prodi : S1 PTI off B 2011
UNIVERSITAS NEGERI MALANG
FAKULTAS TEKNIK
S1 PENDIDIKAN TEKNIK INFORMATIKA
2012
BAB IV
QUEUE
A. Tujuan
1. Mahasiswa mampu menjelaskan pengertian queue dan dequeue
2. Mahasiswa mampu menjelaskan dan menunjukkan cara pembuatan queue, operasi
push dan pop pada array
3. Mahasiswa mampu menjelaskan dan menunjukkan program dengan ADT (Abstract
Data Type) queue dan dequeue dengan array
B. Dasar Teori
Queue / Antrian adalah suatu kumpulan data yang mana penambahan elemen
hanya bisa dilakukan pada satu ujung (disebut dengan sisi belakang atau rear) dan
penghapusan atau pengambilan elemen dilakukan lewat ujung lain (disebut dengan sisi
depan atau front).
Antrian menggunakan prinsip Pertama Masuk Pertama Keluar – First In First Out
(FIFO). Dengan kata lain urutan masuk sama dengan urutan keluar. Antrian banyak
dijumpai dalam kehidupan sehari-hari. Mobil-mobil yang mengantri digerbang tol untuk
membeli karcis tol; orang-orang yang mengantri di loket untuk membeli karcis film juga
membentuk antrian.
Pada antrian kita tidak menentukan batasan seberapa banyak antrian itu akan
berakhir tapi jika kita menggunakan array untuk mengimplementasikan queue/ tumpukan
kita harus membatasi jumlah antrian yang dapat masuk. Ini dikarenakan array memiliki
batasan (upperbound) yang menjadi penghambat jika kita menggunakan antrian. Oleh
sebab itu kita akan mengimplementasikan antrian ini dengan menggunakan link list.
Dengan menggunakan link list tepatnya Single Link List maka elemen dapat
dimasukkan secara tidak terbatas. Kita menggunakan Header Single Link List yang
seperti Stack ada posisi Header dapat kita pergunakan untuk menyimpan informasi
mengenai banyaknya elemen dalam Queue.
a. Deklarasi Queue Dalam Link List
Pendeklarasian Queue di dalam link list sama seperti kita mendeklarasikan link list.
Menggunakan pointer sebagai variabel yang menunjuk ke elemen antrian selanjutnya.
b. Operasi Dasar Pada Queue
Ada 6 operasi dasar yang dapat dilakukan pada struktur data antrian, yaitu:
1. CREATE(Q)
Untuk menciptakan dan menginisialisasi Queue dengan cara membuat
Head = -1 dan Tail = -1
2. SEMPTY(Q)
ISEMPTY(Q) adalah operator yang menentukan apakah antrian Q hampa atau
tidak. ISEMPTY(Q) di terapkan di dalam pascal menjadi sebuah function yang
bertipe boolean sehingga hasil dari function ini akan bernilai True jika antrian
dalam keadaan kosong / hampa (NOEL(Q) = 0) dan akan bernilai False jika
antrian dalam keadaan terisi / tidak kosong (NOEL(Q) > 0). Untuk memeriksa
apakah Antrian sudah penuh atau belum Dengan cara memeriksa nilai Tail, jika
Tail = -1 maka empty
3. Enqueue()
Digunakan Untuk menambahkan elemen ke dalam Antrian, penambahan elemen
selalu ditambahkan di elemen paling belakang, Penambahan elemen selalu
menggerakan variabel Tail dengan cara increment counter Tail terlebih dahulu
4. Dequeue()
Digunakan untuk menghapus elemen terdepan/pertama (head) dari Antrian Dengan
cara menggeser semua elemen antrian kedepan dan mengurangi Tail dgn 1,
Penggeseran dilakukan dengan menggunakan looping.
5. Clear()
Digunakan Untuk menghapus elemen-elemen Antrian dengan cara membuat Tail
dan Head = -1, Penghapusan elemen-elemen Antrian sebenarnya tidak menghapus
arraynya, namun hanya mengeset indeks pengaksesannya ke nilai -1 sehingga
elemen-elemen Antrian tidak lagi terbaca
6. Tampil()
Digunakan Untuk menampilkan nilai-nilai elemen Antrian dengan Menggunakan
looping dari head s/d tail
c. Jenis-jenis Antrian
Selain antrian yang telah kita bahas di atas, masih ada dua tipe antrian lagi
yang penggunaannya juga banyak di dalam kehidupan sehari hari atau dalam dunia
komputer itu sendiri, diantaranya adalah :
1. DEQUE
DEQUE adalah antrian dimana elemennya bisa masuk dan keluar lewat kedua
ujungnya (berbeda dengan queue yang hany bisa masuk lewat ujung belakang dan
keluar lewat ujung depan). Biasanya DEQUE disajikan dengan menggunakan Double
link list yang memiliki dua buah pointer yang menunjuk ke posisi sebelumnya dan
sesudahnya.
Berikut ini adalah struktur umum dari Deque
DEQUE juga mempunyai dua jenis variasi yaitu :
1. Deque input terbatas : suatu deque yang membatasi pemasukkan elemen hanya
pada satu ujung dari list, sementara penghapusan elemen boleh dilakukan pada
kedua ujung list.
2. Deque output terbatas : merupakan kebalikan dari deque input terbatas yaitu suatu
deque yang membatasi penghapusan elemen hanya pada satu ujung dari list,
sementara pemasukkan elemen boleh dilakukan pada kedua ujung list.
2. ANTRIAN BERPRIORITAS
Antrian berprioritas adalah suatu queue yang setiap elemennya telah diberikan sebuah
prioritas, dan urutan proses penghapusan elemen adalah berdasarkan aturan berikut :
a. Elemen yang prioritasnya lebih tinggi, diproses lebih dahulu dibandingkan
dengan elemen yang prioritas lebih rendah.
b. Dua elemen dengan prioritas yang sama, diproses sesuai dengan urutan mereka
sewaktu dimasukkan ke dalam priority queue.
Salah satu contoh antrian berprioritas ini adalah sistem berbagi waktu (time sharing
system), dimana program yang mempunyai prioritas tinggi akan dikerjakan lebih
dahulu dan program-program yang berprioritas sama akan membentuk antrian yang
biasa.
C. Latihan 1. Latihan 1
Script Program
#include <iostream.h>#include <conio.h> \
int f,r,df;int Antrian[50];void enQueue (void);void deQueue (void) ;void Tampilkan (void);
void main (){
int k;for (k=0;k<50;k++)Antrian[k]=0;while (1){
clrscr();cout<<endl;cout<<" +++++Pilihan++++++"<<endl;cout<<" 1. enQueue"<<endl;cout<<" 2. deQueue"<<endl;cout<<" 3. Tampilkan queue"<<endl;cout<<" 4. Keluar"<<endl;cout<<" ++++++++++++++++++"<<endl;cout<<endl;cout<<"Masukan pilihan (1,2,3,4) dalam melakukan Queue : ";cin>>k;if (k==1) enQueue ();if (k==2) deQueue ();if (k==3) Tampilkan ();if (k==4) break;
}}
void enQueue (){
cout<<" Masukan elemen : ";cin>>Antrian[r];r++;
}
void deQueue(){
Antrian[f]=0;f++;
}void Tampilkan (){
int i;cout<<endl<<"Queue : "<<endl;
for(i=f;i<r;++i)cout<<Antrian[i]<<",";cout<<endl<<"press any key...";getche ();
}
Hasil 1. Jika memilih satu maka akan disuruh untuk memasukkan nilai dari antrian
yang di inginkan.
Antrian tersebut dapat diisi trus menerus sampai dengan batas yang telah ditentukan oleh pemrogam,
2. Nomer 3 adalah untuk menampilkan hasil inputan antrian yang telah dimasukkan mulai dari awal masukkan (kiri) sampai dengan masukkan yang terakhir (kanan).
3. nomer 3 adalah digunakan untuk menghapus elemen terdepan atau pertama dari antrian, disini adalah nomer 1 akan hilang
4. setalah memilih nomer 2, kita lihat hasilnya pada nomer 3 lagi untuk menampilkan
5. tekan 4 untuk keluar dari program
2. latihan 2 Script Program
#include <stdio.h>#include <conio.h>#define max 8
typedef struct{
int data[max];int head;int tail;
} queue;
queue antrian;void create(){
antrian.head=antrian.tail=-1;}
int isempty(){
if (antrian.tail==-1) return 1;
else return 0;}
int isfull(){
if (antrian.tail==max-1) return 1;
else return 0;4;}
void Enqueue(int data){
if (isempty()==1) {
antrian.head=antrian.tail=0;antrian.data[antrian.tail]=data;printf(" %d Masuk! \n", antrian.data[antrian.tail]) ;
} else if (isfull()==0) {
antrian.tail++;antrian.data[antrian.tail]=data;printf(" %d Masuk! \n", antrian.data[antrian.tail]);
}}
int dequeue(){
int i;int e = antrian.data[antrian.head];for (i=antrian.head;i<=antrian.tail-1;i++)
{antrian.data[i]=antrian.data[i+1];
} antrian.tail--;
return e;}
void Tampil(){
if (isempty()==0) {
for (int i=antrian.head;i<=antrian.tail;i++) {
printf(" %d ",antrian.data[i]);}
} else printf(" Data Kosong \n");}
void main(){
int pil;int data;create();do
{clrscr();
printf(" ================================== \n"); printf(" PROGRAM ANTRIAN \n"); printf(" ================================== \n");
printf(" 1. Enqueue ( masukkan data )\n");printf(" 2. Dequeue ( keluarkan data awal )\n");printf(" 3. Tampil ( menampilkan data )\n");printf(" 4. Exit\n");
printf(" ================================== \n\n");printf(" Pilihan = ");scanf("%d", &pil);switch(pil)
{case 1:
printf(" Data = "); scanf("%d",&data);
printf(" \n");Enqueue(data);break;
case 2: printf(" Elemen yang keluar = %d",dequeue());
printf(" \n");break;
case 3: printf("\n");
Tampil();printf("\n");break;
}getch();
} while(pil!=4);}
Hasil1. Jika memilih satu maka akan disuruh untuk memasukkan nilai dari antrian
yang di inginkan.
Antrian tersebut dapat diisi trus menerus sampai dengan batas yang telah ditentukan oleh pemrogam,
2. Nomer 3 adalah untuk menampilkan hasil inputan antrian yang telah dimasukkan mulai dari awal masukkan (kiri) sampai dengan masukkan yang terakhir (kanan).
3. nomer 3 adalah digunakan untuk menghapus elemen terdepan atau pertama dari antrian, disini adalah nomer 1 akan hilang
4. setalah memilih nomer 2, kita lihat hasilnya pada nomer 3 lagi untuk menampilkan
5. tekan 4 untuk keluar dari program
D. Tugas Pratikum
Script Program
# include <stdio.h># include <conio.h># include <stdlib.h># include <string.h># define QSIZE 5typedef struct{
int count;int head,tail;char names[QSIZE][30];
}QUEUE;
char* enqueue(char *);char* dequeue();void display();void init();
QUEUE *pq;
int main(){
int choice;char str[30];QUEUE q;pq=&q;init();do
{clrscr();
printf("================================\n"); printf("|| Tugas Pratikum QUEUE ||\n"); printf("================================\n");
printf(":1 for Add into the Queue.. \n");printf(":2 for Delete from the Queue.. \n");printf(":3 Display Elements of the Queue..\n");
printf(":4 For Exit..\n"); printf("================================\n"); printf("\tEnter your Choice: ");
scanf("%d",&choice); printf("================================\n");
switch(choice) {
case 1:printf("\n\t Enter a Name: ");fflush(stdin);gets(str);puts(enqueue(str));break;
case 2:puts(dequeue());break;
case 3:display();break;
case 4: exit(0);
default: printf("\n\n Plz press 1,2,3 or 4 key..");
}printf("\n\n\n Press Any Key to continue...");fflush(stdin);while(!kbhit());
} while(1);
return 0;}
void init(){
pq->head = pq->tail = pq->count= 0;}
char* enqueue(char *p){
if(pq->count==QSIZE)return "\n\n Error: Queue Overflow..!!";
pq->tail= (pq->tail)%QSIZE;strcpy(pq->names[(pq->tail)++],p);pq->count++;return "\n\n Element Successfully Inserted";
}
char* dequeue(){
if(pq->count==0)return "\n\n\ Error: Queue Underflow..!!";pq->head= (pq->head)%QSIZE;pq->count--;printf("\n\n Deleted Queue Element is :");return pq->names[(pq->head)++];
}
void display(){
int i=pq->head;int x=0;if(pq->count==0)printf("\n\n Queue is Empty..");else
{while(x<pq->count)
{ if(i==QSIZE)
i%=QSIZE;printf("\n :%s",pq->names[i]);i++;x++;
}}
}
Hasil
1. Tampilan awal program
2. Option 1 untuk memasukkan data
3. Jika ada 5 masukkan, maka antrian akan penuh dan tidak bisa ditambah antrian lagi
4. Jika ingin menambah antrian, maka harus mengeluarkan antrian paling luar dengan
memilih nomer 2
5. Untuk lebih jelas lihat daftar antrian dengan plihan nomer 3
6. Dengan begitu bisa menambah lagi daftar antrian
7. Dan bisa di lihat lagi hasilnya apakah sudah masuk atau tidak
8. Jika ingin mengakhiri program tekan nomer 4
E. Tugas Rumah
1. Tugas rumah 1
Modifikasi program di Tugas Praktikum dengan menambahkan menu untuk mereset
antrian
Script Program
# include <stdio.h># include <conio.h># include <stdlib.h># include <string.h># include <iostream.h>
# define QSIZE 5typedef struct{
int count;int head,tail;char names[QSIZE][30];
} QUEUE;char* enqueue(char *);char* dequeue();void display();void init();QUEUE *pq;
int main(){
char str[30],choice;QUEUE q;pq=&q;init();
do {
clrscr(); printf("================================\n"); printf("|| Tugas Rumah QUEUE ||\n"); printf("================================\n");
printf("\n 1. Menambah antrian");printf("\n 2. Menghapus 1 data antrian");printf("\n 3. Menampilkan antrian");
printf("\n 4. Mengahpus Seluruh Antrian (reset)");printf("\n 5. Keluar program\n");
printf("\n==============================\n");
printf("\n Masukkan Pilihan : ");scanf("%s",&choice);printf("\n==============================\n");
switch(choice) {
case '1':printf("\n Masukkan antrian: ");fflush(stdin);gets(str);puts(enqueue(str));break;
case '2': printf("\n 1 antrian telah di hapus");
puts(dequeue());break;
case '3':display();break;
case '4': init(); break;
case '5': printf(" Terima Kasih !!! "); exit(0);
getch();default: printf("\n Masukan salah");}printf("\n Press Any Key to continue...");fflush(stdin);while(!kbhit());
} while(1);
return 0;}
void init(){
pq->head = pq->tail = pq->count= 0; cout<<"\n . . Reset data Berhasil . . \n . . .Antrian Kosong. . .";}
char* enqueue(char *p){
if(pq->count==QSIZE)return "\n Antrian penuh";pq->tail= (pq->tail)%QSIZE;strcpy(pq->names[(pq->tail)++],p);pq->count++;return "\n Data Sukses dimasukkan";
}
char* dequeue(){
if(pq->count==0)return "\n Antrian Penuh !";pq->head= (pq->head)%QSIZE;pq->count--;printf("\n Menghapus 1 data, yaitu : ");return pq->names[(pq->head)++];
}
void display(){
int i=pq->head; int x=0;
if(pq->count==0)
{ printf("\n Antrian Kosong"); printf("\n Tidak Ada Data Yang ditampilkan"); } else { while(x<pq->count) { if(i==QSIZE)
i%=QSIZE; cout<<"\n > ";
cout<<pq->names[i]; i++; x++; } }}
Hasil
1. Tampilan awal program
2. Option 1 untuk memasukkan data
3. Option 3 untuk melihat hasil yang dimasukkan antrian , dan Maksimal isi antrian
adalah 5,
4. Jika ada 5 masukkan, maka antrian akan penuh dan tidak bisa ditambah antrian lagi
5. Jika ingin menambah antrian, maka harus mengeluarkan antrian paling luar dengan
memilih nomer 2
6. Untuk lebih jelas lihat daftar antrian dengan plihan nomer 3, data fauzul tidak ada
7. Dengan begitu bisa menambah lagi daftar antrian
8. Dan bisa di lihat lagi hasilnya apakah sudah masuk atau tidak
9. Jika ingin menghapus semua daftar antrian menggunakan option 4, maka daftar
antrian akan kembali kosong lagi
10. Lihat daftar antrian
11. Jika ingin mengakhiri program tekan nomer 4
2. Tugas rumah 2.
Buatlah sebuah program dengan menerapkan contoh kasus sebuah queue dari
praktikum kali ini.
Program : Daftar Antrian Pada Rumah Sakit
Script Program
#include <iostream.h>#include <conio.h>#include <stdio.h>
typedef struct{
int data[100]; char data1[100][20]; char data2[100][30]; char data3[100][15]; int depan; int belakang;}Queue;
Queue antrian;Queue no;Queue nama;Queue poli;
int pilihan, data, i, j;char data1[20], data2[30], data3[15];
int isEmpty(){
if (antrian.belakang==-1) return 1;
else return 0;}
int isFull(){
if(antrian.belakang==100) return 1; else return 0;}
void Enqueue(int data, char data1[20], char data2[30], char data3[15]){
if(isEmpty()==1) { antrian.depan=antrian.belakang=0; nama.depan=nama.belakang=0; poli.depan=poli.belakang=0; no.depan=no.belakang=0; antrian.data[antrian.belakang]=data; for(i=0;i<20;i++) { nama.data1[nama.belakang][i]=data1[i]; } for(i=0;i<30;i++) {
poli.data2[poli.belakang][i]=data2[i]; } for(i=0;i<15;i++) { no.data3[no.belakang][i]=data3[i]; } printf("\n\n ::::::::::::::::::::::::::::::::::::::::::::::::::::::::: \n"); printf(" Data anda telah masuk. silahkan menunggu panggilan"); } else if(isFull()==0) { antrian.belakang++; nama.belakang++; poli.belakang++; no.belakang++; antrian.data[antrian.belakang]=data; for(i=0;i<20;i++) { nama.data1[nama.belakang][i]=data1[i]; } for(i=0;i<30;i++) { poli.data2[poli.belakang][i]=data2[i]; } for(i=0;i<15;i++) { no.data3[no.belakang][i]=data3[i]; } printf("\n\n ::::::::::::::::::::::::::::::::::::::::::::::::::::::::: \n"); printf(" Data anda telah masuk. silahkan menunggu panggilan"); }}
int Dequeue(){
if(isEmpty()==0) { int i,e ; char a[20], b[30]; e=antrian.data[antrian.depan]; for(i=0;i<20;i++) { a[i]=nama.data1[nama.depan][i]; } for(i=0;i<30;i++) { b[i]=poli.data2[poli.depan][i]; } for(i=antrian.depan;i<antrian.belakang;i++) { antrian.data[i]=antrian.data[i+1]; for(j=0;j<20;j++) { nama.data1[i][j]=nama.data1[i+1][j]; } for(j=0;j<30;j++) { poli.data2[i][j]=poli.data2[i+1][j]; } for(j=0;j<15;j++) { no.data3[i][j]=no.data3[i+1][j]; } } antrian.belakang--; nama.belakang--; poli.belakang--; no.belakang--;
printf("antrian no %i dengan nama %s silahkan memasuki poli %s !", e, a, b); return e; return a[20]; return b[30]; } else { printf("antrian kosong"); }}
void buat(){
antrian.depan=antrian.belakang=-1; nama.depan=nama.belakang=-1; poli.depan=poli.belakang=-1; no.depan=no.belakang=-1;}
void main(){
int n; buat(); n=1; do { clrscr(); printf(" ::::::::::::::::::::::::::::::::::::::::::::::::::::::::: \n"); printf(" :: :: \n"); printf(" :: Rumah Sakit SIDOWARAS :: \n"); printf(" :: kec. Bangsal, Kabupaten Mojokerto :: \n"); printf(" :: :: \n"); printf(" ::::::::::::::::::::::::::::::::::::::::::::::::::::::::: \n"); printf(" Menu : \n\n"); printf(" 1. Masukkan Data Antrian \n"); printf(" 2. Panggil Antrian \n"); printf(" 3. Lihat Daftar Antrian \n"); printf(" 4. Menghapus Seluruh Antrian Pasien ( Reset Ulang ) \n"); printf(" 5. Exit \n"); printf(" ::::::::::::::::::::::::::::::::::::::::::::::::::::::::: \n"); printf(" Silahkan Masukkan Pilihan (1-5) : "); scanf("%i", &pilihan); printf(" ::::::::::::::::::::::::::::::::::::::::::::::::::::::::: \n\n\n"); switch(pilihan) { case 1 : clrscr(); printf(" ::::::::::::::::::::::::::::::::::::::::::::::::::::::::: \n"); printf(" :: DATA PASIEN :: \n");
printf(" ::::::::::::::::::::::::::::::::::::::::::::::::::::::::: \n\n"); data=n; printf(" No antrian anda adalah %i \n", n); printf(" Masukkan no. rekam medis anda : "); fflush(stdin); gets(data3); printf(" Masukkan nama lengkap anda: "); fflush(stdin); gets(data1); printf(" Masukkan poli berobat anda: "); fflush(stdin); gets(data2); Enqueue(data, data1, data2, data3); n++; break;
case 2 : clrscr();
printf("::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: \n"); printf(" "); Dequeue();
printf("\n\n::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: "); break;
case 3 : clrscr(); if(isEmpty()==1) { printf("\n ------------------------------------------------------------- \n"); printf(" | No antrian | No.reka medis | Nama Lengkap | Poli Berobat | \n");printf(" ----------------------------------------------------------------- \n");printf(" ---- Antrian Kosong ---- \n"); break; } printf("\n --------------------------------------------------------------------------- \n"); printf(" | No antrian | No.reka medis | Nama Lengkap | Poli Berobat | \n"); printf(" --------------------------------------------------------------------------- \n"); for(i=antrian.depan;i<=antrian.belakang;i++) { gotoxy(3,i+5); cout<<"| "<<antrian.data[i]; gotoxy(16,i+5); cout<<"| "<<no.data3[i]; gotoxy(32,i+5); cout<<"| "<<nama.data1[i]; gotoxy(60,i+5); cout<<"| "<<poli.data2[i]; gotoxy(77,i+5); cout<<"|"; } break;
case 4 : buat(); printf(" . . .Reset Antrian Berhasil. . . !!!"); break;
case 5: printf(" Terimakasih Atas Partisipasinya !!!"); break;
default : printf(" Maaf,, Pilihan Anda Salah "); break; } getch(); }while(pilihan!=5);
}
Hasil
1. Tampilan awal program
2. Option 1 untuk memasukkan data
a. Masukkan 1
b. Masukkan 2
c. Masukkan 3
d. Masukkan 4
.dsb
3. Option 3 untuk melihat daftar antrian pasien yang sudah masuk
4. Daftar pasien bisa di tambah sampai dengan 100 pasien, dan jika penuh daftar antrian
pasien bisa dikurangi atau menghapus seluruh daftar antrian pasien
a. Daftar antrian dikurangi dengan memanggil pasien yang memasukkan data paling
awal dengan option nomer 2.
b. Menghapus seluruhantrian pasien yang ada dengan option nomer 4.
5. Lihat daftar antrian lagi apakah ada atau tidak
6. Jika ingin mengakhiri program ini tekan nomer 4
F. Kesimpulan
Queue / Antrian adalah suatu kumpulan data yang mana penambahan elemen
hanya bisa dilakukan pada satu ujung (disebut dengan sisi belakang atau rear) dan
penghapusan atau pengambilan elemen dilakukan lewat ujung lain (disebut dengan sisi
depan atau front). Sedangkan DEQUE adalah antrian dimana elemennya bisa masuk dan
keluar lewat kedua ujungnya
Ada beberapa Operasi Dasar Pada Queue yang dapat dilakukan pada struktur
data antrian, yaitu: CREATE(Q), SEMPTY(Q), Enqueue(), Dequeue(), Clear(),
Tampil()
G. Daftar Pustaka
Modul pratikum Algoritma dan Struktur data. 2012. Fakultas teknik - Universitas negeri malang