Struktur Data Antrian Pekeliling

Isi kandungan

Bagaimana Antrian Pekeliling Berfungsi
Operasi Antrian Pekeliling
Pelaksanaan Antrian Pekeliling di Python, Java, C, dan C ++
Analisis Kerumitan Antrian Pekeliling
Aplikasi Antrian Pekeliling

Dalam tutorial ini, anda akan mengetahui apa itu barisan bulat. Anda juga akan menemui pelaksanaan antrian bulat di C, C ++, Java dan Python.

Antrian pekeliling mengelakkan pembaziran ruang dalam pelaksanaan antrian biasa menggunakan tatasusunan.

Batasan Antrian biasa

Seperti yang dapat anda lihat pada gambar di atas, setelah sedikit proses mengorek dan menyekat, ukuran barisan telah dikurangkan.

Indeks 0 dan 1 hanya dapat digunakan setelah antrian diset semula apabila semua elemen telah dikurangkan.

Bagaimana Antrian Pekeliling Berfungsi

Circular Queue berfungsi dengan proses kenaikan bulatan iaitu ketika kita berusaha menaikkan pointer dan kita mencapai akhir antrian, kita mulai dari awal barisan.

Di sini, kenaikan bulatan dilakukan oleh pembahagian modulo dengan ukuran barisan. Itu dia,

 jika REAR + 1 == 5 (limpahan!), REAR = (REAR + 1)% 5 = 0 (permulaan barisan)

Perwakilan barisan bulat

Operasi Antrian Pekeliling

Antrian bulat 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

1. Operasi Enqueue

periksa sama ada barisan penuh
untuk elemen pertama, tetapkan nilai FRONT ke 0
secara berkala meningkatkan indeks REAR sebanyak 1 (iaitu jika belakang mencapai akhir, seterusnya akan berada di awal barisan)
tambah elemen baru pada kedudukan yang ditunjukkan oleh REAR

2. Operasi Dequeue

periksa sama ada barisan kosong
kembalikan nilai yang ditunjukkan oleh FRONT
secara berkala meningkatkan indeks FRONT sebanyak 1
untuk elemen terakhir, tetapkan semula nilai FRONT dan REAR ke -1

Walau bagaimanapun, pemeriksaan untuk barisan penuh mempunyai kes tambahan baru:

Kes 1: DEPAN = 0 && REAR == SIZE - 1
Kes 2: FRONT = REAR + 1

Kes kedua berlaku apabila REAR bermula dari 0 kerana kenaikan bulatan dan ketika nilainya hanya 1 kurang dari FRONT, barisan penuh.

Operasi Enque dan Deque

Pelaksanaan Antrian Pekeliling di Python, Java, C, dan C ++

Pelaksanaan antrian yang paling biasa adalah menggunakan tatasusunan, tetapi juga dapat dilaksanakan dengan menggunakan daftar.

Python Java C C +

 # Circular Queue implementation in Python class MyCircularQueue(): def __init__(self, k): self.k = k self.queue = (None) * k self.head = self.tail = -1 # Insert an element into the circular queue def enqueue(self, data): if ((self.tail + 1) % self.k == self.head): print("The circular queue is full") elif (self.head == -1): self.head = 0 self.tail = 0 self.queue(self.tail) = data else: self.tail = (self.tail + 1) % self.k self.queue(self.tail) = data # Delete an element from the circular queue def dequeue(self): if (self.head == -1): print("The circular queue is empty") elif (self.head == self.tail): temp = self.queue(self.head) self.head = -1 self.tail = -1 return temp else: temp = self.queue(self.head) self.head = (self.head + 1) % self.k return temp def printCQueue(self): if(self.head == -1): print("No element in the circular queue") elif (self.tail>= self.head): for i in range(self.head, self.tail + 1): print(self.queue(i), end=" ") print() else: for i in range(self.head, self.k): print(self.queue(i), end=" ") for i in range(0, self.tail + 1): print(self.queue(i), end=" ") print() # Your MyCircularQueue object will be instantiated and called as such: obj = MyCircularQueue(5) obj.enqueue(1) obj.enqueue(2) obj.enqueue(3) obj.enqueue(4) obj.enqueue(5) print("Initial queue") obj.printCQueue() obj.dequeue() print("After removing an element from the queue") obj.printCQueue()

 // Circular Queue implementation in Java public class CQueue ( int SIZE = 5; // Size of Circular Queue int front, rear; int items() = new int(SIZE); CQueue() ( front = -1; rear = -1; ) // Check if the queue is full boolean isFull() ( if (front == 0 && rear == SIZE - 1) ( return true; ) if (front == rear + 1) ( return true; ) return false; ) // Check if the queue is empty boolean isEmpty() ( if (front == -1) return true; else return false; ) // Adding an element void enQueue(int element) ( if (isFull()) ( System.out.println("Queue is full"); ) else ( if (front == -1) front = 0; rear = (rear + 1) % SIZE; items(rear) = element; System.out.println("Inserted " + element); ) ) // Removing an 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 = (front + 1) % SIZE; ) return (element); ) ) void display() ( /* Function to display status of Circular Queue */ int i; if (isEmpty()) ( System.out.println("Empty Queue"); ) else ( System.out.println("Front -> " + front); System.out.println("Items -> "); for (i = front; i != rear; i = (i + 1) % SIZE) System.out.print(items(i) + " "); System.out.println(items(i)); System.out.println("Rear -> " + rear); ) ) public static void main(String() args) ( CQueue q = new CQueue(); // Fails because front = -1 q.deQueue(); q.enQueue(1); q.enQueue(2); q.enQueue(3); q.enQueue(4); q.enQueue(5); // Fails to enqueue because front == 0 && rear == SIZE - 1 q.enQueue(6); q.display(); int elem = q.deQueue(); if (elem != -1) ( System.out.println("Deleted Element is " + elem); ) q.display(); q.enQueue(7); q.display(); // Fails to enqueue because front == rear + 1 q.enQueue(8); ) )

 // Circular Queue implementation in C #include #define SIZE 5 int items(SIZE); int front = -1, rear = -1; // Check if the queue is full int isFull() ( if ((front == rear + 1) || (front == 0 && rear == SIZE - 1)) return 1; return 0; ) // Check if the queue is empty int isEmpty() ( if (front == -1) return 1; return 0; ) // Adding an element void enQueue(int element) ( if (isFull()) printf(" Queue is full!! "); else ( if (front == -1) front = 0; rear = (rear + 1) % SIZE; items(rear) = element; printf(" Inserted -> %d", element); ) ) // Removing an element int deQueue() ( int element; if (isEmpty()) ( printf(" 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 dequeing it. ? else ( front = (front + 1) % SIZE; ) printf(" Deleted element -> %d ", element); return (element); ) ) // Display the queue void display() ( int i; if (isEmpty()) printf(" Empty Queue"); else ( printf(" Front -> %d ", front); printf(" Items -> "); for (i = front; i != rear; i = (i + 1) % SIZE) ( printf("%d ", items(i)); ) printf("%d ", items(i)); printf(" Rear -> %d ", rear); ) ) int main() ( // Fails because front = -1 deQueue(); enQueue(1); enQueue(2); enQueue(3); enQueue(4); enQueue(5); // Fails to enqueue because front == 0 && rear == SIZE - 1 enQueue(6); display(); deQueue(); display(); enQueue(7); display(); // Fails to enqueue because front == rear + 1 enQueue(8); return 0; )

 // Circular Queue implementation in C++ #include #define SIZE 5 /* Size of Circular Queue */ using namespace std; class Queue ( private: int items(SIZE), front, rear; public: Queue() ( front = -1; rear = -1; ) // Check if the queue is full bool isFull() ( if (front == 0 && rear == SIZE - 1) ( return true; ) if (front == rear + 1) ( return true; ) return false; ) // Check if the queue is empty bool isEmpty() ( if (front == -1) return true; else return false; ) // Adding an element void enQueue(int element) ( if (isFull()) ( cout << "Queue is full"; ) else ( if (front == -1) front = 0; rear = (rear + 1) % SIZE; items(rear) = element; cout << endl << "Inserted " << element << endl; ) ) // Removing an element int deQueue() ( int element; if (isEmpty()) ( cout << "Queue is empty" << endl; 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 = (front + 1) % SIZE; ) return (element); ) ) void display() ( // Function to display status of Circular Queue int i; if (isEmpty()) ( cout << endl << "Empty Queue" << endl; ) else ( cout < " << front; cout << endl < "; for (i = front; i != rear; i = (i + 1) % SIZE) cout << items(i); cout << items(i); cout << endl < " << rear; ) ) ); int main() ( Queue q; // Fails because front = -1 q.deQueue(); q.enQueue(1); q.enQueue(2); q.enQueue(3); q.enQueue(4); q.enQueue(5); // Fails to enqueue because front == 0 && rear == SIZE - 1 q.enQueue(6); q.display(); int elem = q.deQueue(); if (elem != -1) cout << endl << "Deleted Element is " << elem; q.display(); q.enQueue(7); q.display(); // Fails to enqueue because front == rear + 1 q.enQueue(8); return 0; )