Antrian(queue)

Antrian(queue)

Kata Pengantar

Assalamualaikum Wr. Wb

Puji syukur kami panjatkan kehadirat Allah SWT karena telah melimpahkan rahmat dan hidayahNya sehingga kami dapat menyelesaikan tugas laporan tentang materi struktur data Antrian(queue). Sholawat serta salam senantiasa tercurah kepada junjungan kita nabi agung Muhammad SAW ayang kita tunggu syafa’atnya. Aamiin.

Dalam era globalisasi dengan berkembangnya kemajuan Ilmu Pengetahuan dan Teknologi, kini berbagai kalangan dituntut untuk berurusan dengan benda robotik buatan manusia. Seperti komputer, kalkulator dan alat elektronik lainny, kini sistem dalam berbagai bidang kehidupan hampir mayoritas menggunakan sistem komputer baik segi penyimpanan data maupun pemrosesnya. Dengan demikian cabang pemrograman sangat dibutuhkan diberbagai kalangan baik di bidang perdangan maupun perbankan, Oleh karena itu mempelajari detail detail ilmu pemrograman sangatlah perlu, seperti halnya cabang struktur data, dalam bidang ini terdapat bermacam-macam ilmu, seperti struktur data Antrian(queue) dan Tumpukan(queue), laporan ini akan membahas tentang penjelasan struktur data Antrian(queue).

Kami menyadari bahwa tugas laporan ini masih jauh dari sempurna, baik dari segi isi maupun cara penyusunannya. Oleh karena itu kami selaku penulis sangat mengharapkan kritik dan saran yang bersifat membangun dari pembaca demi kesempurnaan tugas laporan ini di masa mendatang. Kami berharap tugas laporan yang kami tulis dapat memberikan manfaat dan referensi bagi para pembaca pada khususnya.

Semarang, April 2012

Tim penulis 

DAFTAR ISI

HALAMAN JUDUL……………………………………………………………… 1

KATA PEGANTAR....................................................................................... 2

DAFTAR ISI….……………………………………………………………..……. 3

BAB I

1. Rumusan masalah…………………………………………………………… 4
2. Tujuan………………………………………………………………………. 4
3. Manfaat……………………………………………………………………... 4

BAB II

1. Pengertian struktur data Antrian(queue) ……………………………….….. 5
2. Contoh Antrian(queue) dalam kehidupan sehari-hari…………………….… 7
3. Operasi-operasi pada Antrian(queue)....…………..................................... 9
4. Implementasi Antrian(queue).................................................................. 12
5. Contoh program Antrian(queue).............................................................. 14

BAB III

1. Simpulan………………………………………………………………….... 18
2. Saran……………………………………………………………..………… 18

DAFTAR PUSTAKA……………………………………………………............ 19

BAB I

A.     RUMUSAN MASALAH

1. Apakah struktur data Antrian(queue) ?
2. Bagaimana cara pengoperasian struktur data Antrian(queue) ?
3. Apa saja contoh struktur data Antrian(queue) dalam kehidupan sehari-hari?
4. Apa saja implementasi dari struktur data Antrian(queue) ?
5. Bagaimana bentuk contoh program Antrian(queue)?

B.    TUJUAN

1. Memahami pengertian struktur data Antrian(queue)
2. Memahami cara pengoperasian struktur data Antrian(queue)
3. Mengetahui contoh struktur data Antrian(queue) dalam kehidupan sehari-hari
4. Mengimplementasikan struktur data Antrian(queue) dengan array dan linked list
5. Mengetahui bentuk contoh program Antrian(queue)

C.    MANFAAT

1. Dapat memahami pengertian struktur data Antrian(queue)
2. Dapat memahami cara pengoperasian struktur data Antrian(queue)
3. Dapat mengetahui contoh struktur data Antrian(queue) dalam kehidupan sehari-hari
4. Dapat mengimplementasikan struktur data Antrian(queue) dengan array dan linked list
5. Dapat mengetahui bentuk contoh program Antrian(queue)

BAB II

1. Pengertian struktur data Antrian(queue)

Queue jika diartikan secara harfiah, queue berarti antrian, Queue merupakan suatu struktur data linear. Konsepnya hampir sama dengan Stack, perbedaannya adalah operasi penambahan dan penghapusan pada ujung yang bebeda. Pada Stack atau tumpukan menggunakan prinsip “Masuk terakhir keluar pertama”atau LIFO (Last In First Out), Maka pada Queue atau antrian prinsip yang digunakan adalah “Masuk Pertama Keluar Pertama” atau FIFO (First In First Out).Data-data di dalam antrian dapat bertipe integer, real, record dalam bentuk sederhana atau terstruktur.

Antrian disebut juga “Waiting Line” yaitu penambahan data baru dilakukan pada bagian belakang dan penghapusan data dilakukan pada bagian depan,

Queue merupakan salah satu contoh aplikasi dari pembuatan double linked list yang cukup sering kita temui dalam kehidupan sehari-hari,

Queue (Antrian) adalah list linier yang :

1. Dikenali data pertama (Head) dan data terakhirnya (Tail)

2. Aturan penyisipan dan penghapusan datanya disefinisikan sebagai berikut :

- Penyisipan selalu dilakukan setelah data terakhir

- Penghapusan selalu dilakukan pada data pertama

3. Satu data dengan data lain dapat diakses melalui informasi

(1) Queue dengan 2 data; (2) Queue setelah proses enqueue C, D dan E;

(3) Setelah proses dequeue A dan B

Antrian Berprioritas

Dalam antrian yang telah dibahas di atas, semua data yang masuk dalam antrian dianggap mempunyai prioritas yang sama, sehingga data yang masuk lebih dahulu akan diproses lebih dahulu. Dalam praktek, data-data yang akan masuk dalam suatu antrian ada yang dikatakan mempunyai prioritas yang lebih tinggi dibanding yang lain. Antrian yang demikian ini disebut dengan antrian berprioritas (priority queue).

Dalam antrian berprioritas, setiap datan yang akan msuk dalam antrian sudah ditentukan lebih dahulu prioritasnya. Dalam hal ini berlaku dua ketentuan, yaitu:

1. Data-data yang mempunyai prioritas lebih tinggi akan diproses lebih dahulu.

2. Dua data yang mempunyai prioritas sama akan dikerjakan sesuai dengan urutan

pada saat kedua data ini masuk dalam antrian.

Dengan memperhatikan kedua ketentuan di atas, akan berlaku ketentuan bahwa data yang mempunyai prioritas lebih tinggi akan dikerjakan lebih dahulu dibanding data yang mempunyai prioritas lebih rendah, meskipun data yang berprioritas tinggi masuknya sesudah data yang berprioritas rendah. Salah satu contoh antrian berprioritas ini adalah pada 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 biasa.

Ada beberapa cara untuk mengimplementasikan antrian berprioritas. Salah satu

caranya adalah dengan menggunakan linked list. Jika kita menggunakan linked list,

khususnya single linked list atau double linked list, maka ada ketentuan lain yang perlu

diperhatikan, yaitu:

1. Setiap node dari linked list terdiri tiga bagian, yaitu bagian informasi, angka prioritas dan bagian-bagian penyambung ke simpul lain.
2. Simpul X mendahului (terletak di sebelah kiri) simpul Y, jika prioritas X lebih tinggi dibanding prioritas Y atau jika prioritas X dan Y sama, maka simpul X datang lebih dahulu dibanding dengan Y.

Biasanya dibuat suatu perjanjian bahwa angka prioritas yang lebih kecil menunjukkan derajad prioritas yang lebih tinggi. Sebagai contoh, jika angka prioritas pada simpul X adalah 1 dan pada simpul Y adalah 2, maka dikatakan bahwa simpul X berprioritas lebih tinggi dibanding dengan simpul Y.

B. Contoh Antrian(queue) dalam kehidupan sehari-hari

1. Antrian mobil di pintu tol.

Ketika sebuah mobil datang, dari belakang akan menuju kedepan dari antrian. Setelah mobil mendapatkan karcis tol, antrian yang berada di depan akan maju. Pada saat menempatkan data pada ujung (tail) dari queue disebut dengan enqueue, pada saat memindahkan data dari kepala (head) sebuah queue disebut dengan dequeue.

2. Antrian loket.

Data yang pertama kali masuk ke antrian akan keluar pertama kalinya

Dequeue adalah mengeluarkan satu data dari suatu Antrian

Antrian dapat dibuat dengan menggunakan: Liniear Array dan Circular Array

Kondisi antrian yang menjadi perhatian adalah:

1. Penuh

Bila data pada antrian mencapai kapasitas maksimum antrian. Pada kondisi ini, tidak mungkin dilakukan penambahan ke antrian. Penambahan data menyebabkan kondisi kesalahan Overflow.

2. Kosong

ila tidak ada data pada antrian. Pada kondisi ini, tidak mngkin dilakukan penghapusan data dari antrian. Pengambilan data menyebabkan kondisi kesalahan Overflow.

3. Operasi-operasi pada Antrian(queue)

1. Create()

Untuk menciptakan dan menginisialisasi Queue

Dengan cara membuat Head dan Tail  = -1

2. IsEmpty()

Untuk memeriksa apakah Antrian sudah penuh atau belum

• Dengan cara memeriksa nilai Tail, jika tail = -1 maka empty
• Kita tidak memeriksa Head, karena Head adalah tanda untuk kepala antrian (data pertama dalam antrian) yang tidak akan berubah-ubah
• Pergerakan pada Antrian terjadi dengan penambahan data Antrian kebelakang, yaitu menggunakan nilai tail

3. IsFull()

Untuk mengecek apakah Antrian sudah penuh atau belum

• Dengan cara mengecek nilai tail, jika tail >= MAX-1 (karena MAX-1 adalah batas data array pada C) berarti sudah penuh

4. Enqueue

Untuk menambahkan data ke dalam Antrian, penambahan data selalu

ditambahkan di data paling belakang

• Penambahan data selalu menggerakan variabel tail dengan cara increment counter tail

5. Dequeue()

• Digunakan untuk menghapus data terdepan/pertama dari Antrian
• Dengan cara mengurangi counter Tail dan menggeser semua data antrian kedepan.
• Penggeseran dilakukan dengan menggunakan looping

6. Clear()

Untuk menghapus data-data Antrian dengan cara membuat tail dan head = -1

Penghapusan data-data Antrian sebenarnya tidak menghapus arraynya, namun hanya mengeset indeks pengaksesan-nya ke nilai -1 sehingga data-data Antrian tidak lagi terbaca

 

7. Tampil()

Untuk menampilkan nilai-nilai data Antrian menggunakan looping dari head s/d tail

4. Implementasi Antrian(queue)

1. Implementasi Antrian dengan Array

Seperti halnya pada tumpukan, maka dalam antrian kita juga mengenal ada dua operasi dasar, yaitu menambah data baru yang akan kita tempatkan di bagian belakang antrian dan menghapus data yang terletak di bagian depan antrian. Disamping itu seringkali kita juga perlu melihat apakah antrian mempunyai isi atau dalam keadaan kosong. Operasi penambahan data baru selalu bisa kita lakukan karena tidak ada pembatasan banyaknya data dari suatu antrian. Tetapi untuk menghapus data, maka kita harus melihat apakah antrian dalam keadaan kosong atau tidak. Tentu saja kita tidak mungkin menghapus data dari suatu antrian yang sudah kosong.

Untuk menyajikan antrian menggunakan array, maka kita membutuhkan deklarasi

antrian, misalnya sebagai berikut:

#define MAXQUEUE 100;

typedef int ItemType;

typedef struct{

int Count;

int Front;

int Rear;

ItemType Item[MAXQUEUE];

}Queue;

Front, menunjukkan item yang paling depan, yaitu data yang akan dihapus jika dilakukan operasi penghapusan. Setelah kita melakukan penghapusan, kita melakukan increment pada indeks Front, sehingga indeks menunjuk pada posisi berikutnya. Jika indeks ini jatuh pada angka tertinggi, yaitu angka paling maksimum dari array (N), maka kita melakukan setting ulang ke 0. Array Item[0:N-1] berisi N item yang merupakan isi dari antrian. Berada pada posisi 0:N-1dimana pada posisi ini dapat diindikasikan dua pengenal, yaitu Front dan Rear. Count menunjukkan jumlah item dalam antrian. Rear menunjukkan posisi dimana setelahnya dapat dimasukkan item berikutnya. Representasi antrian lengkap dengan operasi-operasi yang merupakan

karakteristik antrian adalah sebagai berikut:

#include

#include

#define MAXQUEUE 100;

typedef int ItemType;

typedef struct{

int Count;

int Front;

int Rear;

ItemType Item[MAXQUEUE];

}Queue;

void InitializeQueue(Queue *Q)

{

Q->Count = 0;

Q->Front = 0;

Q->Rear = 0;

32

}

int Empty(Queue *Q)

{

return(Q->Count == 0);

}

int Full(Queue *Q)

{

return(Q->Count == MAXQUEUE);

}

void Insert(ItemType ins, Queue *Q)

{

if (Q->Count == MAXQUEUE)

printf("Tidak dapat memasukkan data! Queue Penuh!");

else {

Q->Item[Q->Rear] = ins;

Q->Rear = (Q->Rear + 1) % MAXQUEUE;

++(Q->Count);

}

}

void Remove(Queue *Q, ItemType *rm)

{

if (Q->Count == 0)

printf("Tidak dapat mengambil data! Queue Kosong!");

else {

*rm = Q->Item[Q->Front];

Q->Front = (Q->Front + 1) % MAXQUEUE;

--(Q->Count);

}

}

Jika kita meletakkan beberapa item yang baru dari antrian dalam sebuah array, maka kita menambahkannya pada Rear dan memindah item dari Front. Dengan penambahan dan pengurangan item ini, permasalahan akan terjadi jika ukuran dari array habis. Kita bisa keluar dari permasalahan ini jika kita merepresentasikan antrian secara circular. Cara mensimulasikan antrian secara circular dalam array linear menggunakan arithmetic modular. Arithmetic modular menggunakan ekspresi rumus (X % N) untuk menjaga besarnya nilai X pada range 0:N-1. Jika indeks telah sampai pada N dengan penambahan atau pengurangan tersebut, maka indeks akan diset pada angka 0. Hal yang sama juga dilakukan pada Front jika dilakukan pengambilan item dari

antrian. Setelah mengambil item dari antrian, kita melakukan increment terhadap Front untuk penunjukan pada posisi sesudahnya. Apabila indeks telah berada pada N, maka indeks diset juga pada angka 0. Perintah di bawah ini merupakan perintah yang menunjukkan proses Arithmetic

Modular yang diterapkan pada antrian.

Front = (Front + 1) % N;

Rear = (Rear +1) % N;

2. Implementasi Antrian dengan Linked list

Antrian yang direpresentasikan dengan linked list mempunyai beberapa variasi. Pada kesempatan kali ini hanya direpresentasikan satu macam saja. Linked list yang digunakan di sini menggunakan struktur yang berisi pointer yang menunjuk pada simpul Front dan Rear dari linked list. Masing-masing simpul berisi data dari antrian dan juga link yang menunjuk pada simpul selanjutnya dari linked list, yang dinamakan Link.

#include

#include

typedef int ItemType;

typedef struct QueueNodeTag { ItemType Item;

struct QueueNodeTag *Link;

}QueueNode;

typedef struct {

QueueNode *Front;

QueueNode *Rear;

}Queue;

void InitializeQueue(Queue *Q){

Q->Front = NULL;

Q->Rear = NULL;}

int Empty(Queue *Q){

return(Q->Front == NULL);}

int Full(Queue *Q){

return 0;}

void Insert(ItemType R, Queue *Q){

QueueNode *Temp;

Temp = (QueueNode *) malloc(sizeof(QueueNode));

if (Temp == NULL) {

printf("Queue tidak dapat tercipta");

}else{

Temp->Item = R;

Temp->Link = NULL;

if (Q->Rear == NULL){

Q->Front = Temp;

Q->Rear = Temp;

}else{

Q->Rear->Link=Temp;

Q->Rear = Temp; } } }

35

void Remove(Queue *Q, ItemType *F)

{

QueueNode *Temp;

if (Q->Front == NULL){

printf("Queue masing kosong!");

}else{

*F = Q->Front->Item;

Temp = Q->Front;

Q->Front = Temp -> Link;

free(Temp);

if(Q->Front == NULL) Q->Rear = NULL;

}}

5. Contoh program Antrian(queue)
   1. Listing Program

#include

#include

#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;

}

void Enqueue(int data){

if(IsEmpty()==1){

antrian.head=antrian.tail=0;

antrian.data[antrian.tail]=data;

printf("%d masuk!",antrian.data[antrian.tail]);

void Tampil(){

if(IsEmpty()==0)

{

int i;

for(i=antrian.head;i<=antrian.tail;i++){

printf("%d ",antrian.data[i]);

}

}else printf("data kosong!\n");

}

} else

if(IsFull()==0){

antrian.tail++;

antrian.data[antrian.tail]=data;

printf("%d masuk!",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 Clear(){

antrian.head=antrian.tail=-1;

printf("data clear");

}

void Tampil(){

if(IsEmpty()==0){

int i;

for(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{

system("cls");

printf("1. Enqueue\n");

printf("2. Dequeue\n");

printf("3. Tampil\n");

printf("4. Clear\n");

printf("5. Exit\n");

printf("Pilihan = ");scanf("%d",&pil);

switch(pil){

case 1: printf("Data = ");scanf("%d",&data);

Enqueue(data);

break;

case 2: printf("Elemen yang keluar : %d",Dequeue());

break;

case 3: Tampil();

break;

case 4: Clear();

break;

}

getch();

} while(pil!=5);

}

2. Tampilan program dari listing di atas

• Menu utama

• Enque(menambahkan sebuah data)

Tambahkan 5 buah data yang berisi 10,20,30,40 dan 50.

• Menampilkan data

Setelah di isikan 5 buah data 10 20 30 40 50 maka akan tampil data 10,20,30,40 dan 50

• Deque(menghapus sebuah data pada urutan pertama)

Yang terhapus data 10 karena data 10 pada urutan pertama

• Setelah proses Deque maka akan tampil sebagai berikut,

• Clear (menghapus demua data)

• Setelah proses clear jika kita memproses pilihan tampil maka akan seperti di bawah ini,

• Menu exit(keluar)

BAB III

1. Kesimpulan

1. Antrian (queue) adalah sebuah bentuk struktur yang berdasarkan pada proses FIFO (First In First Out)
2. Contoh Antrian (queue) bisa kita temukan di kehidupan sehari-hari seperti antrian masuk jalan tol dan loket antrian.
3. Pengoperasian Antrian (qeue) berbagai macam seperti, Create, Enque, Deque, IsEmpty, IsFull, Tampil, Clear, dsb.
4. Antrian dapat diimplementasikan dengan menggunakan array atau linked list

B.     SARAN

Dengan pemahaman di atas, kita dapat memahami pengertian, penggunaan, pengoprasian serta implementasi dari struktur data Antrian (qeue). Kita pun bisa membuat program dengan struktur data tersebut, Jika ada salah kata, tata dan canda kami selaku kelompok yang ditugasi membawa materi struktuktur data Antrian (qeue) mohon kritik dan sarannya, Terima Kasih telah meluangkan waktu untuk sekedar membaca laporan kami yang jauh dari sempurna ini, Wa Bilattaufik wal hidayah, Wa ridho wal innayah,

Wassalamaualaikum Wr. Wb.

Daftar Pustaka

http://oopweb.com/Java/Documents/ThinkCSJav/Volume/chap16.htm, diakses tanggal 9 Desember 2008, jam 12.53 WIB.

http://webmail.informatika.org/~rinaldi/Stmik/Makalah/MakalahStmik38.pdf, diakses tanggal 9 Desember 2008, jam 13.05 WIB.

http://www.google.com

http://www.google.co.id

http://www.google.com/gambar/antrian-jalan-tol

http://www.google.com/gambar/antrian-loket

Prijono, Agus dan Teddy Marcus Zakaria. 2006. Konsep dan Implementasi Struktur Data. Bandung : Informatika.