Dalam tutorial ini, Anda akan mempelajari apa itu antrian. Juga, Anda akan menemukan implementasi antrian di C, C ++, Java dan Python.
Antrian adalah struktur data yang berguna dalam pemrograman. Mirip dengan antrian tiket di luar gedung bioskop, di mana orang pertama yang masuk antrian adalah orang pertama yang mendapat tiket.
Antrian mengikuti aturan First In First Out (FIFO) - item yang masuk lebih dulu adalah item yang keluar lebih dulu.
Representasi Antrian FIFO
Pada gambar di atas, karena 1 disimpan dalam antrian sebelum 2, itu juga yang pertama akan dihapus dari antrian. Ini mengikuti aturan FIFO .
Dalam istilah pemrograman, meletakkan item dalam antrian disebut enqueue , dan menghapus item dari antrian disebut dequeue .
Kita dapat mengimplementasikan antrian dalam bahasa pemrograman apa pun seperti C, C ++, Java, Python atau C #, tetapi spesifikasinya kurang lebih sama.
Operasi Dasar Antrian
Antrian adalah objek (struktur data abstrak - ADT) yang memungkinkan operasi berikut:
- Enqueue : Tambahkan elemen ke akhir antrian
- Dequeue : Hapus elemen dari depan antrian
- IsEmpty : Periksa apakah antrian kosong
- IsFull : Periksa apakah antrian sudah penuh
- Peek : Dapatkan nilai antrian depan tanpa menghapusnya
Bekerja dari Antrian
Operasi antrian bekerja sebagai berikut:
- dua petunjuk DEPAN dan BELAKANG
- DEPAN melacak elemen pertama antrian
- REAR melacak elemen terakhir dari antrian
- awalnya, setel nilai FRONT dan REAR menjadi -1
Operasi Enqueue
- periksa apakah antriannya penuh
- untuk elemen pertama, setel nilai FRONT ke 0
- tingkatkan indeks REAR sebanyak 1
- tambahkan elemen baru pada posisi yang ditunjukkan oleh REAR
Operasi Dequeue
- periksa apakah antrian kosong
- mengembalikan nilai yang ditunjukkan oleh FRONT
- naikkan indeks FRONT sebanyak 1
- untuk elemen terakhir, setel ulang nilai FRONT dan REAR ke -1
Operasi Enqueue dan Dequeue
Implementasi Antrian di Python, Java, C, dan C ++
Kami biasanya menggunakan array untuk mengimplementasikan antrian di Java dan C / ++. Dalam kasus Python, kami menggunakan daftar.
Python Java C ++ # Queue implementation in Python class Queue: def __init__(self): self.queue = () # Add an element def enqueue(self, item): self.queue.append(item) # Remove an element def dequeue(self): if len(self.queue) < 1: return None return self.queue.pop(0) # Display the queue def display(self): print(self.queue) def size(self): return len(self.queue) q = Queue() q.enqueue(1) q.enqueue(2) q.enqueue(3) q.enqueue(4) q.enqueue(5) q.display() q.dequeue() print("After removing an element") q.display()
// Queue implementation in Java public class Queue ( int SIZE = 5; int items() = new int(SIZE); int front, rear; Queue() ( front = -1; rear = -1; ) boolean isFull() ( if (front == 0 && rear == SIZE - 1) ( return true; ) return false; ) boolean isEmpty() ( if (front == -1) return true; else return false; ) void enQueue(int element) ( if (isFull()) ( System.out.println("Queue is full"); ) else ( if (front == -1) front = 0; rear++; items(rear) = element; System.out.println("Inserted " + element); ) ) int deQueue() ( int element; if (isEmpty()) ( System.out.println("Queue is empty"); return (-1); ) else ( element = items(front); if (front>= rear) ( front = -1; rear = -1; ) /* Q has only one element, so we reset the queue after deleting it. */ else ( front++; ) System.out.println("Deleted -> " + element); return (element); ) ) void display() ( /* Function to display elements of Queue */ int i; if (isEmpty()) ( System.out.println("Empty Queue"); ) else ( System.out.println("Front index-> " + front); System.out.println("Items -> "); for (i = front; i " + rear); ) ) public static void main(String() args) ( Queue q = new Queue(); // deQueue is not possible on empty queue q.deQueue(); // enQueue 5 elements q.enQueue(1); q.enQueue(2); q.enQueue(3); q.enQueue(4); q.enQueue(5); // 6th element can't be added to because the queue is full q.enQueue(6); q.display(); // deQueue removes element entered first i.e. 1 q.deQueue(); // Now we have just 4 elements q.display(); ) )
// Queue implementation in C #include #define SIZE 5 void enQueue(int); void deQueue(); void display(); int items(SIZE), front = -1, rear = -1; int main() ( //deQueue is not possible on empty queue deQueue(); //enQueue 5 elements enQueue(1); enQueue(2); enQueue(3); enQueue(4); enQueue(5); // 6th element can't be added to because the queue is full enQueue(6); display(); //deQueue removes element entered first i.e. 1 deQueue(); //Now we have just 4 elements display(); return 0; ) void enQueue(int value) ( if (rear == SIZE - 1) printf("Queue is Full!!"); else ( if (front == -1) front = 0; rear++; items(rear) = value; printf("Inserted -> %d", value); ) ) void deQueue() ( if (front == -1) printf("Queue is Empty!!"); else ( printf("Deleted : %d", items(front)); front++; if (front> rear) front = rear = -1; ) ) // Function to print the queue void display() ( if (rear == -1) printf("Queue is Empty!!!"); else ( int i; printf("Queue elements are:"); for (i = front; i <= rear; i++) printf("%d ", items(i)); ) printf(""); )
// Queue implementation in C++ #include #define SIZE 5 using namespace std; class Queue ( private: int items(SIZE), front, rear; public: Queue() ( front = -1; rear = -1; ) bool isFull() ( if (front == 0 && rear == SIZE - 1) ( return true; ) return false; ) bool isEmpty() ( if (front == -1) return true; else return false; ) void enQueue(int element) ( if (isFull()) ( cout << "Queue is full"; ) else ( if (front == -1) front = 0; rear++; items(rear) = element; cout << endl << "Inserted " << element << endl; ) ) int deQueue() ( int element; if (isEmpty()) ( cout << "Queue is empty" <= rear) ( front = -1; rear = -1; ) /* Q has only one element, so we reset the queue after deleting it. */ else ( front++; ) cout << endl < " << element << endl; return (element); ) ) void display() ( /* Function to display elements of Queue */ int i; if (isEmpty()) ( cout << endl << "Empty Queue" << endl; ) else ( cout << endl < " << front; cout << endl < "; for (i = front; i <= rear; i++) cout << items(i) << " "; cout << endl < " << rear << endl; ) ) ); int main() ( Queue q; //deQueue is not possible on empty queue q.deQueue(); //enQueue 5 elements q.enQueue(1); q.enQueue(2); q.enQueue(3); q.enQueue(4); q.enQueue(5); // 6th element can't be added to because the queue is full q.enQueue(6); q.display(); //deQueue removes element entered first i.e. 1 q.deQueue(); //Now we have just 4 elements q.display(); return 0; )
Batasan Antrian
Seperti yang Anda lihat pada gambar di bawah, setelah sedikit mengantre dan mengantre, ukuran antrean telah dikurangi.
Batasan antrian
Dan kita hanya dapat menambahkan indeks 0 dan 1 hanya ketika antrian diatur ulang (ketika semua elemen telah di-dequeued).
Setelah REAR mencapai indeks terakhir, jika kita dapat menyimpan elemen ekstra di ruang kosong (0 dan 1), kita dapat menggunakan ruang kosong tersebut. Ini diimplementasikan oleh antrian yang dimodifikasi yang disebut antrian melingkar.
Analisis Kompleksitas
Kompleksitas operasi enqueue dan dequeue dalam antrian menggunakan array adalah O(1).
Penerapan Antrian
- Penjadwalan CPU, Penjadwalan Disk
- Ketika data ditransfer secara tidak sinkron antara dua proses. Antrian digunakan untuk sinkronisasi. Misalnya: Buffer IO, pipa, file IO, dll
- Penanganan interupsi dalam sistem waktu nyata.
- Sistem telepon Pusat Panggilan menggunakan Antrian untuk menahan orang yang menelepon mereka secara berurutan.
Bacaan yang Direkomendasikan
- Jenis Antrian
- Antrian Edaran
- Struktur Data Deque
- Antrian Prioritas
