LINK
PUSH AND POP
Data Structure and Algorithms – Queue
Antrean adalah struktur data abstrak, agak mirip
dengan Tumpukan, tetapi tidak seperti tumpukan, antrean terbuka di kedua
ujungnya. Salah satu ujungnya selalu digunakan untuk memasukkan data (enqueue)
dan ujung lainnya digunakan untuk menghapus data (dequeue). Antrean mengikuti
metodologi First-In-First-Out, yaitu item data yang disimpan terlebih dahulu
akan diakses terlebih dahulu.
Contoh antrean pada
dunia nyata dapat berupa jalan satu arah dengan satu jalur, di mana kendaraan
masuk lebih dulu, keluar lebih dulu. Contoh pada dunia nyata lainnya dapat
dilihat sebagai antrean di loket tiket dan halte bus.
Queue Representation
Seperti yang sekarang
kita pahami dalam antrean, kita mengakses kedua ujungnya karena alasan yang
berbeda. Diagram berikut di bawah ini menjelaskan representasi antrean sebagai
struktur data.
Seperti di stack, antrean juga dapat
diimplementasikan menggunakan Array, Linked-list, Pointers dan Structures. Demi
kesederhanaan, kami akan mengimplementasikan antrean menggunakan array satu
dimensi.
Operasi
Dasar
Operasi antrean mungkin melibatkan
menginisialisasi atau menentukan antrean, memanfaatkannya, dan kemudian
menghapus sepenuhnya dari memori. Di sini kita akan mencoba memahami operasi
dasar yang terkait dengan antrean.
enqueue () - menambahkan (menyimpan)
item ke antrean.
dequeue () - hapus (akses) item dari
antrean.
Beberapa fungsi yang diperlukan untuk
membuat operasi antrean yang disebutkan di atas.
peek () - Mendapat elemen di depan
antrean tanpa menghapusnya.
isfull () - Memeriksa apakah antrean
penuh.
isempty () - Memeriksa apakah antrean
kosong.
Dalam antrean, selalu dilakukan dequeue
(atau mengakses) data, yang ditunjukkan oleh pointerdepan dan saat memasukkan
(menyimpan) data dalam antrean, kami mengambil bantuan pointer belakang.
Pertama-tama, mari pelajari tentang
fungsi pendukung antrean.
peek() : Fungsi ini membantu untuk
melihat data di depan antrean. Algoritme fungsi peek () adalah sebagai berikut.
Algoritme
begin procedure peek
return
queue[front]
end procedure
Example
int peek() {
return queue[front];
}
isfull()
Karena digunakan array dimensi tunggal
untuk mengimplementasikan antrean, kami hanya memeriksa pointer belakang untuk
mencapai MAXSIZE, untuk menentukan bahwa antrean sudah penuh. Jika kita
mempertahankan antrean dalam daftar tertaut melingkar, algoritme akan berbeda.
Algoritme dari fungsi isfull ().
Algorithm
begin procedure isfull
if rear equals to MAXSIZE
return true
else
return false
endif
end procedure
Example
bool isfull() {
if(rear == MAXSIZE - 1)
return true;
else
return false;
}
isempty()
Algorithm
begin procedure isempty
if front is less than MIN OR front is greater than rear
return true
else
return false
endif
end procedure
Jika nilai depan kurang dari MIN atau 0, memberitahu bahwa antrean belum diinisialisasi (kosong).
Example
bool isempty() {
if(front < 0 || front > rear)
return true;
else
return false;
}
Operasi
Enqueue
Antrean mempertahankan dua pointer data,
depan dan belakang. Oleh karena itu, operasinya relatif sulit untuk diterapkan
dibandingkan dengan stack.
Langkah-langkah berikut harus dilakukan
untuk mengantrekan (menyisipkan) data ke dalam antrean.
Langkah
1 - Periksa apakah antrean sudah penuh.
Langkah
2 - Jika antrean penuh, menghasilkan kesalahan overflow dan keluar.
Langkah
3 - Jika antrean tidak penuh, naikkan pointer belakang untuk menunjuk ruang
kosong berikutnya.
Langkah
4 - Tambahkan elemen data ke lokasi antrean, di mana mengarah ke bagian belakang.
Langkah
5 - Kembalikan Sukses.
Terkadang, juga diperiksa apakah antrean diinisialisasi atau tidak, untuk menangani situasi yang tidak
terduga.
Algoritme
untuk operasi antrean
procedure enqueue(data)
if queue is full
return overflow
endif
rear ← rear + 1
queue[rear] ← data
return true
end procedure
Example
int enqueue(int data)
if(isfull())
return 0;
rear = rear + 1;
queue[rear] = data;
return 1;
end procedure
Operasi
Dequeue
Mengakses data dari antrean ada dua proses: - mengakses data di mana pointer menunjuk bagian depan dan
menghapus data setelah akses. Langkah-langkah berikut diambil untuk melakukan
operasi dequeue -
Langkah
1 - Periksa apakah antrean kosong.
Langkah
2 - Jika antrean kosong, keluar.
Langkah
3 - Jika antrean tidak kosong, akses data bagian depan.
Langkah
4 - Pointer depan naikkan satu step untuk menunjuk ke elemen data berikutnya yang
tersedia.
Langkah
5 - Return sukses.
Algorithm operasi dequeue
procedure dequeue
if queue is empty
return underflow
end if
data = queue[front]
front ← front + 1
return true
end procedure
Example
int dequeue() {
if(isempty())
return 0;
int data = queue[front];
front = front + 1;
return data;
}
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 6
int intArray[MAX];
int front = 0;
int rear = -1;
int itemCount = 0;
int peek() {
return intArray[front];
}
bool isEmpty() {
return itemCount == 0;
}
bool isFull() {
return itemCount == MAX;
}
int size() {
return itemCount;
}
void insert(int data) {
if(!isFull()) {
if(rear == MAX-1) {
rear = -1;
}
intArray[++rear] = data;
itemCount++;
}
}
int removeData() {
int data = intArray[front++];
if(front == MAX) {
front = 0;
}
itemCount--;
return data;
}
int main() {
/* insert 5 items */
insert(3);
insert(5);
insert(9);
insert(1);
insert(12);
// front : 0
// rear : 4
// ------------------
// index : 0 1 2 3 4
// ------------------
// queue : 3 5 9 1 12
insert(15);
// front : 0
// rear : 5
// ---------------------
// index : 0 1 2 3 4 5
// ---------------------
// queue : 3 5 9 1 12 15
if(isFull()) {
printf("Queue is full!\n");
}
// remove one item
int num = removeData();
printf("Element removed: %d\n",num);
// front : 1
// rear : 5
// -------------------
// index : 1 2 3 4 5
// -------------------
// queue : 5 9 1 12 15
// insert more items
insert(16);
// front : 1
// rear : -1
// ----------------------
// index : 0 1 2 3 4 5
// ----------------------
// queue : 16 5 9 1 12 15
// As queue is full, elements will not be inserted.
insert(17);
insert(18);
// ----------------------
// index : 0 1 2 3 4 5
// ----------------------
// queue : 16 5 9 1 12 15
printf("Element at front: %d\n",peek());
printf("----------------------\n");
printf("index : 5 4 3 2 1 0\n");
printf("----------------------\n");
printf("Queue: ");
while(!isEmpty()) {
int n = removeData();
printf("%d ",n);
}
}
Output
Queue is full!
Element removed: 3
Element at front: 5
----------------------
index : 5 4 3 2 1 0
----------------------
Queue: 5 9 1 12 15 16
