Dairesel Kuyruk Veri Yapısı

İçindekiler

Dairesel Sıra Nasıl Çalışır?
Dairesel Kuyruk İşlemleri
Python, Java, C ve C ++ 'da Dairesel Sıra Uygulamaları
Dairesel Sıra Karmaşıklığı Analizi
Dairesel Sıra Uygulamaları

Bu eğitimde döngüsel bir sıranın ne olduğunu öğreneceksiniz. Ayrıca, C, C ++, Java ve Python'da dairesel kuyruk uygulamalarını bulacaksınız.

Dairesel kuyruk, dizileri kullanarak düzenli bir kuyruk uygulamasında alan israfını önler.

Normal Kuyruğun Sınırlandırılması

Yukarıdaki görüntüde görebileceğiniz gibi, biraz kuyruğa alma ve kuyruğundan çıkarma işleminden sonra kuyruğun boyutu küçültülmüştür.

0 ve 1 indeksleri, sadece tüm elemanların kuyruğu çözüldüğünde sıra sıfırlandıktan sonra kullanılabilir.

Dairesel Sıra Nasıl Çalışır?

Dairesel Sıra, dairesel artış süreciyle çalışır, yani işaretçiyi artırmaya çalıştığımızda ve kuyruğun sonuna ulaştığımızda, sıranın başından başlarız.

Burada, dairesel artış, sıra boyutu ile modulo bölme ile gerçekleştirilir. Yani,

 ARKA + 1 == 5 (taşma!), ARKA = (ARKA + 1)% 5 = 0 (sıranın başlangıcı)

Dairesel kuyruk gösterimi

Dairesel Kuyruk İşlemleri

Dairesel sıra şu şekilde çalışır:

iki işaretçi ÖN ve ARKA
ÖN kuyruğun ilk öğesini takip edin
REAR kuyruğun son öğelerini takip eder
başlangıçta FRONT ve REAR değerini -1 olarak ayarlayın

1. İşlemi Sırala

sıranın dolu olup olmadığını kontrol edin
ilk eleman için FRONT değerini 0 olarak ayarlayın
REAR endeksini dairesel olarak 1 artırın (yani arka taraf sona ulaşırsa, sıranın başlangıcında olur)
REAR ile gösterilen konuma yeni elemanı ekleyin

2. Sıradan Çıkarma İşlemi

sıranın boş olup olmadığını kontrol edin
FRONT ile gösterilen değeri döndür
FRONT endeksini dairesel olarak 1 artır
son eleman için FRONT ve REAR değerlerini -1 olarak sıfırlayın

Bununla birlikte, tam kuyruk için kontrolün yeni bir ek durumu vardır:

Durum 1: ÖN = 0 && REAR == SIZE - 1
Durum 2: FRONT = REAR + 1

İkinci durum, REAR döngüsel artış nedeniyle 0'dan başladığında ve değeri FRONT'dan sadece 1 küçük olduğunda, kuyruk doludur.

Enque ve Deque İşlemleri

Python, Java, C ve C ++ 'da Dairesel Sıra Uygulamaları

En yaygın kuyruk uygulaması dizileri kullanmaktır, ancak listeler kullanılarak da uygulanabilir.

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; )