In questo tutorial imparerai cos'è una coda. Inoltre, troverai l'implementazione della coda in C, C ++, Java e Python.
Una coda è una struttura dati utile nella programmazione. È simile alla coda dei biglietti fuori da una sala cinematografica, dove la prima persona che entra in coda è la prima persona che riceve il biglietto.
La coda segue la regola FIFO (First In First Out) : l'elemento che entra per primo è l'elemento che esce per primo.
Rappresentazione FIFO della coda
Nell'immagine sopra, poiché 1 è stato tenuto in coda prima del 2, è anche il primo ad essere rimosso dalla coda. Segue la regola FIFO .
In termini di programmazione, l'inserimento di elementi nella coda è chiamato accodamento e la rimozione di elementi dalla coda è chiamato dequeue .
Possiamo implementare la coda in qualsiasi linguaggio di programmazione come C, C ++, Java, Python o C #, ma la specifica è praticamente la stessa.
Operazioni di base della coda
Una coda è un oggetto (una struttura dati astratta - ADT) che consente le seguenti operazioni:
- Accoda : aggiunge un elemento alla fine della coda
- Dequeue : rimuove un elemento dalla parte anteriore della coda
- IsEmpty : controlla se la coda è vuota
- IsFull : controlla se la coda è piena
- Peek : ottieni il valore della parte anteriore della coda senza rimuoverlo
Funzionamento della coda
Le operazioni in coda funzionano come segue:
- due indicatori ANTERIORE e POSTERIORE
- FRONT traccia il primo elemento della coda
- REAR traccia l'ultimo elemento della coda
- inizialmente, impostare il valore di FRONT e REAR su -1
Operazione di accodamento
- controlla se la coda è piena
- per il primo elemento, impostare il valore di FRONT su 0
- aumentare l'indice REAR di 1
- aggiungere il nuovo elemento nella posizione indicata da REAR
Operazione di rimozione dalla coda
- controlla se la coda è vuota
- restituisce il valore indicato da FRONT
- aumentare l'indice ANTERIORE di 1
- per l'ultimo elemento, reimpostare i valori di FRONT e REAR a -1
Operazioni di accodamento e rimozione dalla coda
Implementazioni di code in Python, Java, C e C ++
Di solito usiamo gli array per implementare le code in Java e C / ++. Nel caso di Python, usiamo liste.
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; )
Limitazioni di Queue
Come puoi vedere nell'immagine qui sotto, dopo un po 'di accodamento e rimozione dalla coda, la dimensione della coda è stata ridotta.
Limitazione di una coda
E possiamo solo aggiungere gli indici 0 e 1 solo quando la coda viene reimpostata (quando tutti gli elementi sono stati rimossi dalla coda).
Dopo che REAR ha raggiunto l'ultimo indice, se possiamo memorizzare elementi extra negli spazi vuoti (0 e 1), possiamo usare gli spazi vuoti. Ciò è implementato da una coda modificata chiamata coda circolare.
Analisi della complessità
La complessità delle operazioni di accodamento e rimozione dalla coda in una coda utilizzando un array è O(1).
Applicazioni di Queue
- Pianificazione della CPU, pianificazione del disco
- Quando i dati vengono trasferiti in modo asincrono tra due processi, la coda viene utilizzata per la sincronizzazione. Ad esempio: buffer IO, pipe, file IO, ecc
- Gestione degli interrupt nei sistemi in tempo reale.
- I sistemi telefonici del Call Center utilizzano le code per tenere in ordine le persone che le chiamano.
Letture consigliate
- Tipi di coda
- Coda circolare
- Deque Data Structure
- Coda prioritaria
