Queue (Antrian) adalah struktur data linear yang merupakan kumpulan elemen. Queue adalah jenis khusus dari list, di mana elemen dimasukkan pada satu ujung yang disebut rear (belakang) dan dihapus dari ujung lainnya yang disebut front (depan).
Prinsip utama dari queue adalah FIFO (First-In-First-Out) atau masuk pertama, keluar pertama.
Queue merupakan struktur data abstrak (Abstract Data Type / ADT) dan sangat berguna dalam pemrograman. Konsepnya mirip dengan antrian tiket di depan bioskop, di mana orang yang pertama kali masuk antrian adalah orang pertama yang mendapatkan tiket.
Contoh dalam kehidupan nyata lainnya adalah jalan satu arah satu jalur, di mana kendaraan yang masuk terlebih dahulu akan keluar terlebih dahulu.
Operasi utama:
-
enqueue() → tambah data
-
dequeue() → hapus data
Proses
ALGORITHM Enqueue(Q, item)
INPUT : Q (queue), item (elemen yang akan dimasukkan)
OUTPUT : Queue Q yang telah ditambahkan elemen baru
BEGIN
IF rear = MAX - 1 THEN
OUTPUT "Queue Overflow"
RETURN
ENDIF
IF front = -1 THEN
front ← 0
rear ← 0
ELSE
rear ← rear + 1
ENDIF
Q[rear] ← item
END
Penjelasan Variabel
-
Q : array sebagai penyimpan queue
-
MAX : kapasitas maksimum queue
-
front : penunjuk elemen depan
-
rear : penunjuk elemen belakang
-
item : data yang akan dimasukkan
DEQUEUE
ALGORITHM Dequeue(Q)
INPUT : Q (queue)
OUTPUT : Elemen yang dihapus dari queue
BEGIN
IF front = -1 THEN
OUTPUT "Queue Underflow"
RETURN
ENDIF
item ← Q[front]
IF front = rear THEN
front ← -1
rear ← -1
ELSE
front ← front + 1
ENDIF
RETURN item
END
Contoh :
Antrian bank
Printer queue
Task scheduling OS
Implementasi Array
#include <iostream>
using namespace std;
#define MAX 5
class Queue {
private:
int arr[MAX];
int front, rear;
public:
Queue() {
front = -1;
rear = -1;
}
bool isEmpty() {
return (front == -1);
}
bool isFull() {
return (rear == MAX - 1);
}
void enqueue(int x) {
if (isFull()) {
cout << "Queue Overflow\n";
return;
}
if (isEmpty()) {
front = 0;
}
arr[++rear] = x;
cout << "Elemen " << x << " masuk ke queue\n";
}
void dequeue() {
if (isEmpty()) {
cout << "Queue Underflow\n";
return;
}
cout << "Elemen " << arr[front] << " keluar dari queue\n";
if (front == rear) {
front = rear = -1;
} else {
front++;
}
}
void display() {
if (isEmpty()) {
cout << "Queue kosong\n";
return;
}
cout << "Isi Queue: ";
for (int i = front; i <= rear; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
};
int main() {
Queue q;
q.enqueue(10);
q.enqueue(20);
q.enqueue(30);
q.display();
q.dequeue();
q.display();
return 0;
}
Implementasi Link List
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
class Queue {
private:
Node *front, *rear;
public:
Queue() {
front = rear = NULL;
}
bool isEmpty() {
return (front == NULL);
}
void enqueue(int x) {
Node* newNode = new Node();
newNode->data = x;
newNode->next = NULL;
if (rear == NULL) {
front = rear = newNode;
} else {
rear->next = newNode;
rear = newNode;
}
cout << "Elemen " << x << " masuk ke queue\n";
}
void dequeue() {
if (isEmpty()) {
cout << "Queue kosong\n";
return;
}
Node* temp = front;
cout << "Elemen " << temp->data << " keluar dari queue\n";
front = front->next;
if (front == NULL) {
rear = NULL;
}
delete temp;
}
void display() {
if (isEmpty()) {
cout << "Queue kosong\n";
return;
}
Node* temp = front;
cout << "Isi Queue: ";
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
};
int main() {
Queue q;
q.enqueue(5);
q.enqueue(15);
q.enqueue(25);
q.display();
q.dequeue();
q.display();
return 0;
}
