Implementasi Queue
Pada blog ini akan menyajikan implementasi queue dalam C++.
Array-based Queue Implementation
Berikut adalah implementasi queue berbasis 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;
}
Berikut jika program dijalankan.
Linked List-based Queue Implementation
#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;
}
Queue dapat dijalankan menggunakan penerapan dalam linked list.
Example Program: Palindrom
Sebagai contoh akan dibuat sebuah program dalam cpp yang mengandalkan queue untuk melakukan pengecekan palindrom.
#include <bits/stdc++.h>
using namespace std;
int main() {
stack<char> s;
queue<char> q;
char ch;
char sItem, qItem;
int mismatches = 0;
cout << "Enter string: " << endl;
while(cin.peek() != '\n' && cin >> ch) {
if(isalpha(ch)) {
s.push(toupper(ch));
q.push(toupper(ch));
}
}
while( (!q.empty()) && (!s.empty()) ) {
sItem = s.top();
s.pop();
qItem = q.front();
q.pop();
if(sItem != qItem) ++mismatches;
}
if (mismatches == 0) cout << "That is a palindrome" << endl;
else cout << "That is not a palindrome" << endl;
return 0;
}
Berikut akan dilakukan input untuk pengecekan palindrom dengan konsep queue.
Ketika diinputkan palindrom, maka program akan mengeluarkan output "That is a palindrom" dan jika bukan palindrom maka akan mengeluarkan "That is not a palindrom".
Study Case
Study case pada ppt meminta untuk membuat program simulasi menghitung rata-rata waktu tunggu objek sebelum dilayani oleh sejumlah server. Dalam simulasi ini, harus mengolah durasi total simulasi, rata-rata waktu transaksi, jumlah server, dan interval kedatangan objek sebagai input, lalu mengevaluasi bagaimana perubahan jumlah server atau frekuensi kedatangan objek memengaruhi efisiensi sistem. Program bekerja dengan melacak waktu kedatangan setiap objek dalam antrean dan menghitung selisihnya saat mereka mulai diproses oleh server yang kosong, yang pada akhirnya menghasilkan data statistik berupa rata-rata waktu tunggu sebagai indikator utama kinerja sistem tersebut.
Berikut adalah implementasi yang telah dibuat dalam c++.
#include <bits/stdc++.h>
using namespace std;
struct Customer {
int arrivalTime;
};
struct Server {
int timeRemaining;
bool isBusy;
Server() : timeRemaining(0), isBusy(false) {}
};
int main() {
int simLength, avgTransactionTime, numServers, avgArrivalInterval;
cin >> simLength;
cin >> avgTransactionTime;
cin >> numServers;
cin >> avgArrivalInterval;
srand(time(0));
queue<Customer> q;
vector<Server> servers(numServers);
int totalWaitTime = 0;
int customersServed = 0;
for (int currentTime = 0; currentTime < simLength; ++currentTime) {
if (rand() % avgArrivalInterval == 0) {
Customer newCustomer;
newCustomer.arrivalTime = currentTime;
q.push(newCustomer);
}
for (int i = 0; i < numServers; ++i) {
if (servers[i].isBusy) {
servers[i].timeRemaining--;
if (servers[i].timeRemaining <= 0) {
servers[i].isBusy = false;
}
}
if (!servers[i].isBusy && !q.empty()) {
Customer currentCust = q.front();
q.pop();
totalWaitTime += (currentTime - currentCust.arrivalTime);
customersServed++;
servers[i].isBusy = true;
servers[i].timeRemaining = avgTransactionTime;
}
}
}
if (customersServed > 0) {
double avgWaitTime = (double)totalWaitTime / customersServed;
cout << avgWaitTime << endl;
} else {
cout << 0 << endl;
}
return 0;
}
Berikutnya dicoba untuk menginputkan durasi selama 1 jam (3600 s), waktu penyelesaian 60s, server sebanyak 3, dan interval kedatangan setiap 120s.
Hasilnya bernilai 0 karena kapasitas pelayanan sistem ini jauh lebih besar daripada kecepatan kedatangan objek baru. Dengan interval kedatangan setiap 120 detik dan waktu penyelesaian yang hanya 60 detik oleh 3 server sekaligus, dipastikan selalu ada server yang menganggur. Sehingga setiap objek yang tiba dapat langsung dilayani seketika itu juga tanpa pernah masuk ke dalam antrean, jadi waktu tunggunya murni menjadi nol.
Source Code
https://github.com/xbggnr/Queues-implementation.git
-- Terima Kasih --
Komentar
Posting Komentar