Δομή δεδομένων κυκλικής ουράς

Πίνακας περιεχομένων

Πώς λειτουργεί η κυκλική ουρά
Λειτουργίες κυκλικής ουράς
Εφαρμογές κυκλικής ουράς σε Python, Java, C και C ++
Ανάλυση πολυπλοκότητας κυκλικής ουράς
Εφαρμογές κυκλικής ουράς

Σε αυτό το σεμινάριο, θα μάθετε τι είναι μια κυκλική ουρά. Επίσης, θα βρείτε την εφαρμογή κυκλικής ουράς σε C, C ++, Java και Python.

Η κυκλική ουρά αποφεύγει τη σπατάλη χώρου σε μια κανονική εφαρμογή ουράς χρησιμοποιώντας πίνακες.

Περιορισμός της κανονικής ουράς

Όπως μπορείτε να δείτε στην παραπάνω εικόνα, μετά από λίγο enqueue και dequeue, το μέγεθος της ουράς έχει μειωθεί.

Τα ευρετήρια 0 και 1 μπορούν να χρησιμοποιηθούν μόνο μετά την επαναφορά της ουράς όταν όλα τα στοιχεία έχουν αφαιρεθεί.

Πώς λειτουργεί η κυκλική ουρά

Η κυκλική ουρά λειτουργεί με τη διαδικασία της κυκλικής αύξησης, δηλαδή όταν προσπαθούμε να αυξήσουμε τον δείκτη και φτάσουμε στο τέλος της ουράς, ξεκινάμε από την αρχή της ουράς.

Εδώ, η κυκλική αύξηση γίνεται με διαίρεση modulo με το μέγεθος της ουράς. Αυτό είναι,

 αν REAR + 1 == 5 (υπερχείλιση!), REAR = (ΠΙΣΩ + 1)% 5 = 0 (έναρξη της ουράς)

Κυκλική αναπαράσταση ουράς

Λειτουργίες κυκλικής ουράς

Η κυκλική ουρά λειτουργεί ως εξής:

δύο δείκτες Μπροστά και ΠΙΣΩ
FRONT παρακολουθείτε το πρώτο στοιχείο της ουράς
ΠΙΣΩ παρακολουθείτε τα τελευταία στοιχεία της ουράς
αρχικά, ορίστε την τιμή FRONT και REAR σε -1

1. Λειτουργία Enqueue

ελέγξτε αν η ουρά είναι γεμάτη
για το πρώτο στοιχείο, ορίστε την τιμή FRONT σε 0
αυξήστε κυκλικά τον δείκτη REAR κατά 1 (δηλαδή εάν το πίσω μέρος φτάσει στο τέλος, το επόμενο θα ήταν στην αρχή της ουράς)
προσθέστε το νέο στοιχείο στη θέση που δείχνει ο REAR

2. Λειτουργία Dequeue

ελέγξτε αν η ουρά είναι κενή
επιστρέψτε την τιμή που δείχνει ο FRONT
αυξήστε κυκλικά τον δείκτη FRONT κατά 1
για το τελευταίο στοιχείο, επαναφέρετε τις τιμές FRONT και REAR σε -1

Ωστόσο, ο έλεγχος για πλήρη ουρά έχει μια νέα επιπλέον υπόθεση:

Περίπτωση 1: FRONT = 0 && REAR == SIZE - 1
Περίπτωση 2: FRONT = REAR + 1

Η δεύτερη περίπτωση συμβαίνει όταν το REAR ξεκινά από το 0 λόγω κυκλικής αύξησης και όταν η τιμή του είναι μόλις 1 μικρότερη από το FRONT, η ουρά είναι πλήρης.

Λειτουργίες Enque και Deque

Εφαρμογές κυκλικής ουράς σε Python, Java, C και C ++

Η πιο συνηθισμένη εφαρμογή ουράς είναι η χρήση συστοιχιών, αλλά μπορεί επίσης να εφαρμοστεί χρησιμοποιώντας λίστες.

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