Dalam tutorial ini, anda akan mengetahui apa itu barisan. Anda juga akan menemui pelaksanaan antrian di C, C ++, Java dan Python.
Antrian adalah struktur data yang berguna dalam pengaturcaraan. Ia sama dengan barisan tiket di luar dewan pawagam, di mana orang pertama yang memasuki barisan adalah orang pertama yang mendapat tiket.
Antrian mengikuti peraturan First In First Out (FIFO) - item yang masuk pertama adalah item yang keluar terlebih dahulu.
FIFO Perwakilan Antrian
Dalam gambar di atas, kerana 1 disimpan dalam barisan sebelum 2, ia juga yang pertama dikeluarkan dari barisan juga. Ia mengikut peraturan FIFO .
Dalam istilah pengaturcaraan, meletakkan item dalam barisan disebut enqueue , dan mengeluarkan item dari barisan disebut dequeue .
Kita dapat menerapkan antrian dalam bahasa pengaturcaraan seperti C, C ++, Java, Python atau C #, tetapi spesifikasinya hampir sama.
Operasi Asas Beratur
Antrian adalah objek (struktur data abstrak - ADT) yang membolehkan operasi berikut:
- Enqueue : Tambahkan elemen ke hujung barisan
- Dequeue : Keluarkan elemen dari hadapan barisan
- IsEmpty : Periksa sama ada barisan kosong
- IsFull : Periksa sama ada barisan penuh
- Mengintip : Dapatkan nilai bahagian depan barisan tanpa mengeluarkannya
Kerja Antrian
Operasi antrian berfungsi seperti berikut:
- dua titik FRONT dan REAR
- DEPAN mengesan elemen pertama dalam barisan
- REAR mengesan elemen terakhir dalam barisan
- pada mulanya, tetapkan nilai FRONT dan REAR hingga -1
Operasi Enqueue
- periksa sama ada barisan penuh
- untuk elemen pertama, tetapkan nilai FRONT ke 0
- tingkatkan indeks REAR sebanyak 1
- tambah elemen baru pada kedudukan yang ditunjukkan oleh REAR
Operasi Dequeue
- periksa sama ada barisan kosong
- kembalikan nilai yang ditunjukkan oleh FRONT
- tingkatkan indeks FRONT sebanyak 1
- untuk elemen terakhir, tetapkan semula nilai FRONT dan REAR ke -1
Operasi Enqueue dan Dequeue
Pelaksanaan Antrian di Python, Java, C, dan C ++
Kami biasanya menggunakan tatasusunan untuk menerapkan antrian di Java dan C / ++. Dalam kes Python, kami menggunakan senarai.
Python Java C 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 ini, setelah sedikit proses mengorek dan menyekat, ukuran barisan telah dikurangkan.
Batasan barisan
Dan kita hanya dapat menambahkan indeks 0 dan 1 hanya apabila barisan diset semula (apabila semua elemen telah dikurangkan).
Setelah REAR mencapai indeks terakhir, jika kita dapat menyimpan elemen tambahan di ruang kosong (0 dan 1), kita dapat memanfaatkan ruang kosong. Ini dilaksanakan oleh barisan yang diubahsuai yang disebut lingkaran bulat.
Analisis Kerumitan
Kerumitan operasi enqueue dan dequeue dalam barisan menggunakan array adalah O(1).
Aplikasi Antrian
- Penjadualan CPU, Penjadualan Disk
- Apabila data dipindahkan secara tidak segerak antara dua proses. Antrian digunakan untuk penyegerakan. Contohnya: Penyangga IO, paip, fail IO, dll
- Pengendalian gangguan dalam sistem masa nyata.
- Sistem telefon Call Center menggunakan Antrean untuk menahan orang yang memanggilnya mengikut urutan.
Bacaan yang Disyorkan
- Jenis Beratur
- Antrian Pekeliling
- Struktur Data Deque
- Baris Keutamaan
