In deze tutorial leer je wat een wachtrij is. Ook vindt u implementatie van wachtrij in C, C ++, Java en Python.
Een wachtrij is een nuttige datastructuur bij het programmeren. Het is vergelijkbaar met de kaartjeswachtrij buiten een bioscoopzaal, waar de eerste persoon die de rij binnenkomt de eerste persoon is die het kaartje krijgt.
De wachtrij volgt de FIFO- regel (First In First Out) : het item dat als eerste naar binnen gaat, is het item dat als eerste naar buiten komt.
FIFO-weergave van wachtrij
In de bovenstaande afbeelding, aangezien 1 vóór 2 in de wachtrij werd gehouden, is het ook de eerste die uit de wachtrij wordt verwijderd. Het volgt de FIFO- regel.
In programmeringstermen wordt het plaatsen van items in de wachtrij enqueue genoemd , en het verwijderen van items uit de wachtrij heet dequeue .
We kunnen de wachtrij implementeren in elke programmeertaal zoals C, C ++, Java, Python of C #, maar de specificatie is vrijwel hetzelfde.
Basisbewerkingen van wachtrij
Een wachtrij is een object (een abstracte gegevensstructuur - ADT) dat de volgende bewerkingen mogelijk maakt:
- In wachtrij plaatsen : voeg een element toe aan het einde van de wachtrij
- Dequeue : Verwijder een element van de voorkant van de wachtrij
- IsEmpty : Controleer of de wachtrij leeg is
- IsFull : controleer of de wachtrij vol is
- Peek : verkrijg de waarde van de voorkant van de wachtrij zonder deze te verwijderen
Werking van wachtrij
Wachtrijbewerkingen werken als volgt:
- twee wijzers VOOR en ACHTER
- FRONT het eerste element van de wachtrij volgen
- REAR volgt het laatste element van de wachtrij
- Stel in eerste instantie de waarde VOOR en ACHTER in op -1
Bewerking in wachtrij plaatsen
- controleer of de wachtrij vol is
- stel voor het eerste element de waarde van FRONT in op 0
- verhoog de REAR-index met 1
- voeg het nieuwe element toe op de positie waarnaar REAR verwijst
Uitschrijven
- controleer of de wachtrij leeg is
- geef de waarde terug met FRONT
- verhoog de FRONT-index met 1
- Stel voor het laatste element de waarden FRONT en REAR opnieuw in op -1
Bewerkingen in wachtrij plaatsen en verwijderen
Wachtrij-implementaties in Python, Java, C en C ++
We gebruiken meestal arrays om wachtrijen in Java en C / ++ te implementeren. In het geval van Python gebruiken we lijsten.
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; )
Beperkingen van wachtrij
Zoals je in de onderstaande afbeelding kunt zien, is de wachtrij na een beetje in de wachtrij plaatsen en uit de wachtrij halen verkleind.
Beperking van een wachtrij
En we kunnen alleen indexen 0 en 1 toevoegen als de wachtrij opnieuw is ingesteld (als alle elementen uit de wachtrij zijn gehaald).
Nadat REAR de laatste index heeft bereikt, kunnen we, als we extra elementen in de lege ruimtes (0 en 1) kunnen opslaan, gebruik maken van de lege ruimtes. Dit wordt geïmplementeerd door een aangepaste wachtrij, de circulaire wachtrij.
Complexiteitsanalyse
De complexiteit van bewerkingen in de wachtrij en de wachtrij ongedaan maken met behulp van een array is O(1).
Toepassingen van Queue
- CPU-planning, schijfplanning
- Wanneer gegevens asynchroon worden overgedragen tussen twee processen, wordt de wachtrij gebruikt voor synchronisatie. Bijvoorbeeld: IO-buffers, pijpen, bestands-IO, enz
- Afhandeling van interrupts in real-time systemen.
- Callcenter-telefoonsystemen gebruiken wachtrijen om mensen die ze bellen op volgorde te houden.
Aanbevolen metingen
- Typen wachtrijen
- Circulaire wachtrij
- Deque-gegevensstructuur
- Prioriteits-rij
