Structure de données de file d'attente circulaire

Table des matières

Fonctionnement de la file d'attente circulaire
Opérations de file d'attente circulaire
Implémentations de files d'attente circulaires en Python, Java, C et C ++
Analyse de la complexité de la file d'attente circulaire
Applications de la file d'attente circulaire

Dans ce didacticiel, vous apprendrez ce qu'est une file d'attente circulaire. Vous trouverez également l'implémentation de la file d'attente circulaire en C, C ++, Java et Python.

La file d'attente circulaire évite le gaspillage d'espace dans une implémentation de file d'attente régulière utilisant des tableaux.

Limitation de la file d'attente régulière

Comme vous pouvez le voir dans l'image ci-dessus, après un peu de mise en file d'attente et de retrait de la file d'attente, la taille de la file d'attente a été réduite.

Les index 0 et 1 ne peuvent être utilisés qu'après la réinitialisation de la file d'attente lorsque tous les éléments ont été retirés de la file d'attente.

Fonctionnement de la file d'attente circulaire

Circular Queue fonctionne par le processus d'incrémentation circulaire c'est-à-dire que lorsque nous essayons d'incrémenter le pointeur et que nous atteignons la fin de la file, nous partons du début de la file.

Ici, l'incrément circulaire est effectué par division modulo avec la taille de la file d'attente. C'est,

 si REAR + 1 == 5 (débordement!), REAR = (REAR + 1)% 5 = 0 (début de la file d'attente)

Représentation de file d'attente circulaire

Opérations de file d'attente circulaire

La file d'attente circulaire fonctionne comme suit:

deux pointeurs AVANT et ARRIÈRE
FRONT trace le premier élément de la file d'attente
REAR suit les derniers éléments de la file d'attente
initialement, définissez la valeur de FRONT et REAR sur -1

1. Opération de mise en file d'attente

vérifier si la file d'attente est pleine
pour le premier élément, définissez la valeur de FRONT sur 0
augmenter de façon circulaire l'index REAR de 1 (c'est-à-dire que si l'arrière atteint la fin, il serait ensuite au début de la file d'attente)
ajouter le nouvel élément à la position pointée par REAR

2. Opération de retrait de la file d'attente

vérifier si la file d'attente est vide
renvoie la valeur pointée par FRONT
augmenter de façon circulaire l'indice FRONT de 1
pour le dernier élément, remettez les valeurs de FRONT et REAR à -1

Cependant, la vérification de la file d'attente pleine a un nouveau cas supplémentaire:

Cas 1: FRONT = 0 && REAR == SIZE - 1
Cas 2: FRONT = REAR + 1

Le deuxième cas se produit lorsque REAR commence à 0 en raison d'un incrément circulaire et lorsque sa valeur est juste 1 de moins que FRONT, la file d'attente est pleine.

Opérations Enque et Deque

Implémentations de files d'attente circulaires en Python, Java, C et C ++

L'implémentation de file d'attente la plus courante utilise des tableaux, mais elle peut également être implémentée à l'aide de listes.

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