Köer
↑Snabböversikt
Section titled “Snabböversikt”En kö följer FIFO: först in, först ut. Det värde som lades till först tas också bort först.
| Operation | Vad händer? | Typisk tid |
|---|---|---|
| Enqueue | Lägg till ett värde | O(1) amorterat |
| Dequeue | Ta bort från början | O(1) |
| Peek | Läs nästa värde utan att ta bort det | O(1) |
Prova operationerna
Section titled “Prova operationerna”Prova själv
Först in först ut (FIFO)
Vi lägger till längst bak och tar bort längst fram. Det äldsta värdet lämnar först.
Så fungerar ordningen
Section titled “Så fungerar ordningen”- Lägg till flera värden i följd.
- Titta på nästa värde. Det har väntat längst i kön.
- Ta bort ett värde. Nästa värde ändras, men de andra ligger kvar i sin ordning.
- Fortsätt tills samlingen är tom.
var items = new Queue<int>();items.Enqueue(10);items.Enqueue(20);Console.WriteLine(items.Peek()); // 10Console.WriteLine(items.Dequeue()); // 10#include <queue>#include <iostream>std::queue<int> items;items.push(10);items.push(20);std::cout << items.front() << '\n'; // 10items.pop(); // pop returns void in C++När använder man den?
Section titled “När använder man den?”Köer används för schemaläggning, händelsehantering och bredden-först-sökning. De bevarar ankomstordningen.
Vad garanterar FIFO?
Section titled “Vad garanterar FIFO?”En kö tar ut det objekt som har väntat längst: först in, först ut. FIFO säger inget om prioritet, färdigställandetid eller rättvisa i ett distribuerat system. Om vissa uppgifter måste gå före kan en prioritetskö eller schemaläggare passa bättre.
Vanliga användningar
Section titled “Vanliga användningar”Köer används i bredden-först-sökning, uppgiftshantering, meddelandeflöden och händelsesystem. De hjälper när producent och konsument arbetar i olika takt, men löser inte överbelastning automatiskt. Du behöver ibland begränsningar och en strategi för att bromsa inflödet.
Prestanda
Section titled “Prestanda”En ringbuffert eller länkad lista kan lägga till och ta bort objekt från kön i konstant tid. Om du tar bort första elementet i en vanlig arraylista kan alla senare objekt behöva flyttas.