STRUKTUR DATA QUEUE (ANTREAN)

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