Apa yang dimaksud dengan antrian pada struktur data?

Queue / Antrian adalah suatu kumpulan data yang mana penambahan elemen hanya bisa dilakukan pada satu ujung (disebut dengan sisi belakang atau tail/rear) dan penghapusan atau pengambilan elemen dilakukan lewat ujung lain (disebut dengan sisi depan atau head/front).

Table of Contents Show

1. Deklarasi Antrian dengan array
2. Inisialisasi
3. Operasi cek kosong
4. Operasi cek penuh
5. Operasi Enqueue
6. Operasi Dequeue
7. Operasi Clear
8. Operasi Tampil
Operasi-Operasi Queue:
Implementasi Queue dengan Linear Array
Operasi-Operasi Queue dengan Linear Array
Contoh Implementasi Queue dengan Circular Array
Operasi-Operasi Queue dengan Circular Array
Contoh Soal Queue Struktur Data
Video yang berhubungan

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.

Elemen yang pertama kali masuk ke antrian akan keluar pertama kalinya. DEQUEUE adalah mengeluarkan satu elemen dari suatu antrian. Terdapat satu buah pintu masuk di suatu ujung dan satu buah pintu keluar di ujung satunya sehingga membutuhkan variabel Head dan Tail.

1. Deklarasi Antrian dengan array

Proses pendeklarasi antrian adalah proses pembuatan struktur antrian dalam memori. Struktur antrian terdiri dari data dalam array, head untuk menunjukkan ujung antrian dan tail untuk menunjukkan akhir antrian.

#define MAX 6 struct Queue { int data[MAX]; int head; int tail; };

2. Inisialisasi

Inisialisasi antrian adalah proses pembuatan suatu antrian kosong. Proses inisialisasi untuk antrian yang menggunakan array adalah dengan mengisi nilai field head dan tail dengan 0 (nol) jika elemen pertama diawali dengan nomor 1. Kalau elemen pertama array dimulai dengan 0 maka head dan tail diisi dengan nilai -1.

void Create() { antrian.head=antrian.tail=-1; }

3. Operasi cek kosong

Operasi ini digunakan untuk memeriksa apakah antrian dalam keadaan kosong. Operasi ini penting dilakukan dalam proses Dequeu. Ketika suatu antrian dalam keadaan kosong, maka proses Dequeue tidak bisa dilakukan. Operasi ini dilakukan dengan memeriksa tail. Jika tail bernilai -1, maka berarti antrian dalam keadaan empty (kosong).

int IsEmpty() { if(antrian.tail==-1) return 1; else return 0; }

4. Operasi cek penuh

Operasi ini berguna untuk memeriksa keadaan antrian apakah sudah penuh atau belum. Operasi ini akan memberikan nilai true (1) jika field tail sama dengan size-1.

int IsFull() { if(antrian.tail==MAX-1) return 1; else return 0; }

5. Operasi Enqueue

Operasi ini berguna untuk menambah suatu elemen data baru pada antrian dan disimpan pada posisi head dan tail yang akan mengakibatkan posisi tail akan berubah. Langkah operasi ini adalah :

Periksa apakah kosong. Jika kosong maka ubah posisi head dan tail pada posisi 0, kemudian masukkan datanya.
Jika antrian tidak kosong maka naikkan posisi tail sebesar 1, kemudian masukkan datanya.

void Enqueue(int data) { if(IsEmpty()==1) { antrian.head=antrian.tail=0; antrian.data[antrian.tail]=data; cout<<antrian.data[antrian.tail]; } else { antrian.tail++; antrian.data[antrian.tail]=data; cout<<antrian.data[antrian.tail]; } }

6. Operasi Dequeue

Operasi ini berguna untuk mengambil elemen pertama (head) dari antrian. Penghapusan dilakukan dengan cara mengurangi counter Tail dan menggeser semua elemen antrian kedepan. Penggeseran dilakukan dengan menggunakan looping.

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

7. Operasi 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 pengaksesan-nya.

void Clear() { antrian.head=antrian.tail=-1; cout<<"Data Clear"; }

8. Operasi Tampil

Digunakan untuk menampilkan nilai-nilai elemen antrian. Proses menampilkan data dalam antrian dilakukan dengan menggunakan looping dari head s/d tail.

void Tampil() { if (IsEmpty()==0) for (int i=antrian.head;i<=antrian.tail; i++) cout<<antrian.data[i]<<" "; else cout<<"Data Kosong\n"; }

Program Lengkap:

#include <stdio.h> #include <conio.h> #include <iostream.h> #define MAX 6 struct Queue { int data[MAX]; int head; int tail; }; 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; cout<<antrian.data[antrian.tail]; } else //kodisi lainnya jika penuh() sama dengan 0 maka antrian.ekor ditambah 1 { antrian.tail++; antrian.data[antrian.tail]=data; cout<<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; cout<<"Data Clear"; } void Tampil() { if (IsEmpty()==0) for (int i=antrian.head;i<=antrian.tail; i++) cout<<antrian.data[i]<<" "; else cout<<"Data Kosong\n"; } void main() { int pil; int data; Create(); do { clrscr(); cout<<"\n============MENU PILIHAN============\n"; cout<<"1. Enqueue\n"; cout<<"2. Dequeue\n"; cout<<"3. Tampil\n"; cout<<"4. Clear\n"; cout<<"5. Keluar\n"; cout<<"--------------------------------------\n"; cout<<"Masukkan Pilihan Anda -> "; cin>>pil; switch(pil) { case 1: cout<<"Data : ";cin>>data; Enqueue(data); break; case 2: if (IsEmpty()==0) cout<<"Elemen yang keluar : "<<Dequeue(); else cout<<"Data kosong"<<endl; break; case 3: Tampil(); break; case 4: Clear(); break; case 5: break; } getch(); } while(pil!=5); }

Sumber

Mata kuliah Struktur Data. Disusun oleh Eko Riswanto
STMIK EL Rahma Yogyakarta.

Queue bisa disebut juga antrian pada struktur data. Pengertian queue adalah sekumpulan data yang mana penambahan elemen hanya bisa dilakukan pada suatu ujung yang disebut sisi belakang (rear), dan penghapusan (pengambilan elemen) dilakukan lewat ujung lain.

Contoh queue paling sederhana dapat dilihat pada antrian. Prinsip kerja dari queue adalah prinsip “First In First Out” (FIFO) atau “masuk pertama keluar pertama”. Sedangkan prinsip “masuk terakhir keluar pertama” atau “Last In First Out” (LIFO), digunakan pada tumpukan atau stack.

Pada queue terdapat satu pintu masuk di salah satu ujung dan satu pintu keluar di ujung lainnya. Maka ada penunjuk yang menunjukkan awal dan akhir. Operasi penting dalam queue:

Add yang berfungsi menambah sebuah elemen ke dalam antrian.
Delete yang berfungsi menghapus atau mengeluarkan elemen dari antrian.

Dalam ilmu komputer, antrian atau queue banyak digunakan terutama dalam sistem operasi yang memerlukan manajemen sumber daya dan penjadwalan. Contohnya time-sharing computer-system yang bisa dipakai oleh sejumlah orang secara serempak.

Sebuah antrian (queue) memiliki suatu operasi bernama add_priority. Dalam hal ini, antrian tidak lagi menerapkan konsep antrian yang murni, namun berubah menjadi antrian sesuai prioritas tertentu pada elemen, dan elemen yang baru ditambah tidak selalu berada di akhir.

Operasi-Operasi Queue:

a. Create
Untuk menciptakan dan menginisialisasi Queue dengan cara membuat Head dan Tail = -1

b. IsEmpty
Dipakai untuk memeriksa penuh tidaknya sebuah antrian dengan cara memeriksa nilai tail, jika tail = -1 maka empty. Kita tidak memeriksa head, karena head adalah tanda kepala antrian (elemen pertama dalam antrian) yang tidak akan berubah.

Pergerakan pada antrian terjadi dengan penambahan elemen antrian di bagian belakang, yaitu menggunakan nilai tail.

c. IsFull
Dipakai untuk mengecek penuh tidaknya antrian dengan cara mengecek nilai tail, jika tail >= MAX-1 (karena MAX-1 adalah batas elemen array pada C) maka sudah penuh.

d. EnQueue
Digunakan untuk penambahan 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

e. DeQueue
Dipakai untuk menghapus elemen terdepan (head) dari queue dengan cara menggeser semua elemen antrian ke bagian depan dan mengurangi tail dengan 1 penggeseran yang dilakukan dengan menggunakan pengulangan.

f. Clear
Digunakan untuk menghapus elemen-elemen antrian dengan cara membuat tail dan head bernilai -1. Penghapusan elemen-elemen antrian sebenarnya tidak menghapus arraynya, namun hanya mengeset indeks pengaksesannya menjadi -1 sehingga elemen-elemen antrian tidak lagi terbaca.

g. Tampil
Dipakai untuk menampilkan nilai-nilai elemen antrian menggunakan pengulangan dari head hingga tail.

Implementasi Queue dengan Linear Array

Linear array adalah suatu array yang seakan-akan dibuat menjadi suatu garis lurus dengan satu pintu masuk dan satu pintu keluar.

Berikut ini diberikan contoh deklarasi kelas queue linear sebagai implementasi dari queue menggunakan linear array. Dalam prakteknya, dapat diganti sesuai dengan kebutuhan. Data diakses dengan field data, dan indeks item pertama dan terakhir disimpan dalam field head dan tail.

Konstruktor akan menginisialisasikan nilai dari head dan tail dengan -1 untuk menunjukkan bahwa antrian masih kosong dan mengalokasikan data sebanyak MAX_QUEUE yang ditunjuk oleh data. Destruktor akan mengosongkan antrian kembali dan mendealokasikan memori yang digunakan oleh antrian.

Operasi-Operasi Queue dengan Linear Array

a. IsEmpty
Fungsi IsEmpty berguna untuk mengecek apakah queue sudah terisi atau masih kosong. hal ini dilakukan dengan mengecek apakah tail bernilai -1 atau tidak. Nilai -1 menandakan bahwa queue masih kosong.

b. IsFull
Fungsi IsFull berguna untuk mengecek apakah queue sudah penuh atau masih bias menampung data dengan cara mengecek apakah nilai tail sudah sama dengan jumlah maksimal queue. Jika nilai keduanya sama, berarti antrian sudah penuh.

c. EnQueue
Fungsi EnQueue berguna untuk memasukkan sebuah elemen dalam sebuah antrian.

d. DeQueue
Fungsi DeQueue berfungsi untuk mengambil sebuah elemen dari antrian. Operasi ini sering disebut juga serve. Hal ini dilakukan dengan cara memindahkan sejauh satu langkah ke posisi di depannya sehingga otomatis elemen yang paling depan akan tertimpa dengan elemen yang terletak di belakangnya.

e. Clear
Fungsi Clear berguna untuk menghapus semua lemen dalam queue dengan jalan mengeluarkan semua elemen tersebut satu per satu hingga queue kosong dengan memanfaatkan fungsi DeQueue.

Contoh Implementasi Queue dengan Circular Array

Circular array adalah sebuah array yang dibuat menyerupai sebuah lingkaran dengan titik awal (head) dan titik akhir (tail) saling bersebelahan jika array tersebut masih kosong. Posisi head dan tail pada gambar di atas adalah bebas asalkan saling bersebelahan.

Berikut dibagikan deklarasi kelas queue circular sebagai implementasi circular array. Dalam prakteknya, dapat diganti sesuai dengan kebutuhan. Data diakses dengan field data, dan indeks item pertama dan terakhir disimpan dalam field head dan Tail.

Konstruktor akan menginisialisasi nilai head dan tail dengan 0 dan MAX-QUEUE-1 untuk menunjukkan bahwa antrian masih kosong dan mengalokasikan data sebanyak MAX-QUEUE yang ditunjuk oleh data. Destruktur akan mengosongkan antrian kembali dan mengdealokasikan memori yang digunakan oleh antrian.

Operasi-Operasi Queue dengan Circular Array

a. IsEmpty
Fungsi IsEmpty berguna untuk mengecek apakah queue sudah terisi atau masih kosong. Hal ini dilakukan dengan mengecek apakah tail lebih besar dari head dan tail masih terletak bersebelahan dengan head. Jika benar demikian, maka queue masih kosong.

b. IsFull
Fungsi IsFull berguna untuk mengecek apakah queue sudah penuh atau masih bias menampung data dengan cara mengecek apakah tempat yang masih kosong tinggal satu atau tidak (untuk membedakan dengan empty dimana semua tempat kosong). Jika benar berarti queue penuh.

c. EnQueue
Fungsi EnQueue berfungsi untuk memasukkan sebuah elemen ke dalam queue tail dan head awal bernilai nol (0).

d. DeQueue
DeQueue berguna untuk mengambil sebuah elemen dari queue. Hal ini dilakukan dengan cara memindahkan posisi head satu posisi ke belakang.

Contoh Soal Queue Struktur Data

Berikut adalah beberapa jawaban dari soal yang berkaitan dengan queue dalam kehidupan. Jika kamu punya soal lain, silakan berkomentar agar kita dapat sama-sama mencari jawabannya.

Berikan contoh antrian dalam kehidupan!

Antrian pada saat ke dokter. Orang yang pertama mengantri akan mendapat posisi paling depan dalam antrian. Orang yang di posisi depan maka orang itu yang pertama mendapatkan pelayanan dan/atau pengobatan

Jelaskan fungsi operasi ADD_priority!

Priority queue adalah nilai-nilai null dan kita tidak dapat membuat priority queue objek yang tidak sebanding misalnya setiap kelas tersesuai yang kita miliki menggunakan java sebanding dan komparator interface untuk menyortir objek dan prioritas antrian untuk pengolahan priority elemen itu.

Sebutkan perbedaan stack dengan array dalam queue struktur data! Apa yang membedakan konsep kerja keduanya? Berikan contoh dari masing-masing konsep dalam di kehidupan sehari-hari!

Dalam struktur data, dikenal sebuah konsep bernama array dan stack. Keduanya tentu sangat berbeda.

Stack menggunakan LIFO atau Last In First Out (yang masuk terakhir akan keluar pertama, yang masuk pertama akan keluar terakhir) yang apabila kita menghapus/mengeluarkan data, maka data yang terakhirlah yang akan terhapus/keluar terlebih dahulu.

Contoh stack dalam kehidupan sehari-hari adalah proses penurunan batu bata dari mobil. Batu bata yang diambil pasti adalah batu bata yang paling atas, padahal batu bata tersebut diletakkan terakhir.

Array menggunakan metode FIFO atau First In First Out (yang masuk terakhir akan keluar terakhir, yang masuk pertama akan keluar pertama) yang apabila kita menghapus/mengeluarkan data, maka data yang pertamalah yang akan terhapus/keluar terdahulu.

Contoh array dalam kehidupan sehari-hari adalah saat seseorang mengantre menunggu nomornya dipanggil untuk melakukan pembayaran pajak 5 tahunan di Samsat.

Penutup

Sudah selesai pembahasan mengenai materi queue ini. Secara sederhana, queue artinya sebuah antrian. Semoga kamu sudah memahami apa yang dimaksud dengan queue dan juga contoh queue yang ada di kehidupan sehari-hari.

Ikuti kami di Google News untuk dapatkan artikel terbaru!

Bagikan ke media sosial: