LINEAR QUEUE
PERTEMUAN 06
MATA KULIAH : STRUKTUR DATA
LINEAR QUEUE
Queue menggunakan array 1D:
1. Linear Queue (Antrian Lurus)
2. Circular Queue (Antrian Melingkar)
3. Double Ended Queue/Deque (Antrian dengan ujung ganda)
1. Linear Queue
I. Ilustrasi
Misal n= 10
F (Front) : menunjuk pengantri paling depan/siap untuk keluar/ siap untuk dilayani
R (Rear) : menunjuk pengantri paling belakang/paling akhir masuk
R = 6, artinya :
Pernah masuk 7 pengantri dengan urutan masuk Q[0], Q[1], Q[2], Q[3], Q[4], Q[5], Q[6]
F = 3, artinya :
Sudah keluar sebanyak 3 pengantri dengan urutan keluar Q[0], Q[1], Q[2]
II. Prinsip : FIFO(First In First Out) atau FIFS (First In First Serve)
III. Proses :
- AWAL (Inisialisasi)
- INSERT (Sisip, Masuk, Simpan, Tulis)
- DELETE (Hapus, Keluar, Ambil, Dilayani)
- RESET (Kembali ke keadaan awal)
a) Fungsi dasar untuk proses AWAL :
b) Fungsi dasar proses INSERT :
c) Fungsi dasar proses DELETE :
d) Fungsi dasar proses RESET :
IV. Kondisi antrian (n : jml elemen array)
1. Kondisi awal
a. F = 0, R = -1 kondisi awal
b. F = R + 1 antrian kosong
c. R < n - 1 antrian bisa diisi
2. Misal masuk 1 pengantri, belum ada yang keluar
a. F = 0 belum ada yang keluar
b. F < R + 1 antrian ada isinya
c. R < n – 1 antrian bisa diisi
3. Misal masuk lagi 5 pengantri, belum ada yang keluar
a. R = 5 sudah pernah masuk 6
b. F = 0 belum ada yang keluar
c. F < R + 1 antrian ada isinya
d. R < n – 1 antrian bisa diisi
4. Misal keluar 5 pengantri
a. F = 5 sudah keluar 5 pengantri
b. F = R tinggal 1 pengantri
c. F < R + 1 antrian ada isinya
d. R < n – 1 antrian bisa diisi
5. Misal keluar lagi satu pengantri
a. F = 6 sudah keluar 6 pengantri
b. R = 5
c. F = R + 1 antrian kosong
d. R < n + 1 antrian bisa diisi
6. Misal masuk lagi 3 pengantri
a. F < R + 1 antrian ada isinya
b. R < n – 1 antrian masih bisa diisi
7. Misal masuk lagi 1 pengantri
a. F < R + 1 antrian ada isinya
b. R = n – 1 antrian penuh
8. Misal keluar 3 pengantri
a. F < R + 1 antrian ada isinya
b. F = R antrian sisa 1 pengantri
c. R = n – 1 antrian penuh
9. Misalkan keluar 1 pengantri
a. F = n semua antrian sudah keluar
b. F = R + 1 antrian kosong
c. R = n – 1 antrian penuh (disebut penuh)
d. F = R + 1 dan R = n – 1 kondisi khusus :
- Kosong karena tidak ada isinya
- Penuh karena tidak bisa diisi
- Perlu direset(kembali ke posisi awal)
10. Kondisi khusus lainnya :
a. Antrian penuh tapi belum ada yang keluar
i. F = 0 belum ada yang keluar
ii. R = n – 1 antrian penuh
Kondisi antrian:
V. Fungsi INSERT dan DELETE lengkap
Soal
1. Buatlah suatu program Animasi Antrian dengan 4 buah pilihan : INSERT, DELETE, CETAK ANTRIAN, QUIT.
Jika dipilih INSERT : program akan meminta user untuk menginput sebuah karakter yang akan dimasukan kedalam antrian
Jika dipilih DELETE : maka karakter pertama masuk akan dikeluarkan dari antrian
Jika dipilih CETAK ANTRIAN : komputer menampilkan karakter yang ada pada antrian
Jika dipilih QUIT : program keluar
Jawab :
#include<iostream>
#include<conio.h>
#include<stdlib.h>
#define n 10
using namespace std;
void INSERT();
void DELETE();
void CETAKLAYAR();
void Inisialisasi();
void RESET();
int PIL,F,R;
char PILIHAN [1],HURUF;
char Q[n];
void main ( )
{
Inisialisasi();
do
{
cout<<" ANIMASI QUEUE"<<endl;
cout<<"=============="<<endl;
cout<<"1. INSERT"<<endl;
cout<<"2. DELETE"<<endl;
cout<<"3. CETAK QUEUE"<<endl;
cout<<"4. QUIT"<<endl;
cout<<"PILIHAN : "; cin>>PILIHAN;
PIL=atoi(PILIHAN);
switch (PIL)
{
case 1:
INSERT ();
break;
case 2:
DELETE();
break;
case 3:
CETAKLAYAR ();
break;
default:
cout<<"TERIMA KASIH"<<endl;
break;
}
cout<<"press any key to continue"<<endl;
getch();
system("cls");
}
while (PIL<4);
}
void INSERT()
{
if(R<n-1)
{
cout<<endl<<"MASUKAN 1 HURUF : ";
cin>>HURUF;
Q[++R]=HURUF;
}
else
cout<<"Antrian Penuh"<<endl;
}
void CETAKLAYAR()
{
if(F<R+1)
{
for (int i=F;i<=R;i++)
cout<<"Q["<<i<<"] = "<<Q[i]<<endl;
}
else
cout<<"Antrian Kosong"<<endl;
}
void DELETE()
{
if(F<=R+1)
{
HURUF=Q[F];
Q[F++]='\0';
cout<<"Data yang diambil : "<<HURUF<<endl;
if(F==n)
RESET();
}
else
cout<<"Antrian Kosong"<<endl;
}
void Inisialisasi()
{
F=0;
R=-1;
}
void RESET()
{
F=0;
R=-1;
}
DAFTAR PUSTAKA
Buku
1. Esakov, Jeffrey, Tom Weiss, Data Structures An Advanced Approach Using C, Prentice-Hall, Inc. 1989
2. Hariyanto, Bambang, Struktur Data, Informatika Bandung, Pebruari 2000
3. Kadir, Abdul, Pemrograman Dasar Turbo C, Andi Offset, Yogyakarta, 1991
4. Kruse, Robert L. Data Structures & Program Design, Prentice-Hall, Inc. 1987
5. Standish, Thomas A. Data Structures, Algorithms & Software Principles In C, Addison Wesley, 1995
Komentar
Posting Komentar