În acest tutorial, veți afla ce este o coadă. De asemenea, veți găsi implementarea cozii în C, C ++, Java și Python.
O coadă este o structură de date utilă în programare. Este similar cu coada de bilete în afara unei săli de cinema, unde prima persoană care intră în coadă este prima persoană care primește biletul.
Coada urmează regula First In First Out (FIFO) - elementul care intră primul este elementul care iese primul.
Reprezentarea FIFO a cozii
În imaginea de mai sus, deoarece 1 a fost păstrat în coadă înainte de 2, este primul care a fost eliminat și din coadă. Urmează regula FIFO .
În ceea ce privește programarea, punerea elemente în coada de așteptare este numit Puneți în coadă , și eliminarea elementelor din coada se numește dequeue .
Putem implementa coada în orice limbaj de programare, cum ar fi C, C ++, Java, Python sau C #, dar specificațiile sunt cam aceleași.
Operațiuni de bază ale cozii
O coadă este un obiect (o structură abstractă de date - ADT) care permite următoarele operații:
- Enqueue : Adăugați un element la sfârșitul cozii
- Dequeue : eliminați un element din partea din față a cozii
- IsEmpty : Verificați dacă coada este goală
- IsFull : Verificați dacă coada este plină
- Peek : obțineți valoarea din fața cozii fără a o elimina
Funcționarea cozii
Operațiunile la coadă funcționează după cum urmează:
- două indicatoare FRONT și SPATE
- FRONT urmăriți primul element al cozii
- Urmăriți în spate ultimul element al cozii
- inițial, setați valoarea FRONT și SPATE la -1
Operațiunea cu stânga
- verificați dacă coada este plină
- pentru primul element, setați valoarea FRONT la 0
- măriți indicele SPATE cu 1
- adăugați noul element în poziția indicată de SPATE
Operațiunea Dequeue
- verificați dacă coada este goală
- returnează valoarea indicată de FRONT
- măriți indicele FRONT cu 1
- pentru ultimul element, resetați valorile FRONT și SPATE la -1
Operații de stingere și stingere
Implementări de coadă în Python, Java, C și C ++
De obicei folosim tablouri pentru a implementa cozi în Java și C / ++. În cazul Python, folosim 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; )
Limitările cozii
După cum puteți vedea în imaginea de mai jos, după un pic de stoarcere și stoarcere, dimensiunea cozii a fost redusă.
Limitarea unei cozi
Și putem adăuga indexuri 0 și 1 numai atunci când coada este resetată (când toate elementele au fost stinse).
După ce REAR atinge ultimul index, dacă putem stoca elemente suplimentare în spațiile goale (0 și 1), putem folosi spațiile goale. Aceasta este implementată printr-o coadă modificată numită coadă circulară.
Analiza complexității
Complexitatea operațiunilor de coadă și de coadă într-o coadă utilizând o matrice este O(1).
Aplicații ale cozii
- Programarea procesorului, programarea discurilor
- Când datele sunt transferate asincron între două procese. Coada este utilizată pentru sincronizare. De exemplu: tampoane IO, țevi, IO fișier etc.
- Gestionarea întreruperilor în sistemele în timp real.
- Sistemele telefonice din centrul de apeluri folosesc cozi pentru a ține în ordine persoanele care le apelează.
Lecturi recomandate
- Tipuri de coadă
- Coadă circulară
- Deque Structura datelor
- Coadă prioritară
