FIFO (datastruktur)

FIFO (engelska: First In First Out, "först in, först ut") är en benämning på kösystem som används i datorsystem. Uppgifterna behandlas i den ordning de kommer till kön (precis som en "riktig" kö framför en butikskassa). Implementeras normalt datorprogram med hjälp av en kö.

Datalogi

Att använda sig av FIFO inom till exempel schemaläggning kan vara tillämpligt om man vet att de saker som står på kö kommer att slutföras inom en ändlig tid. Problemet är om något som väntar längre ned på kön behöver komma upp och bli färdigt innan alla andra är helt klara. Ofta kan det vara bättre att använda sig av en Round Robin-struktur, som inte tillåter att något som tar lång tid ligger först på kön och aldrig låter senare objekt komma fram.

Som exempel kan man återgå till en "riktig" kö framför en butikskassa. Alla kommer att få betala inom en överskådlig framtid, men ibland kommer det en långsam och krånglig kund som blockerar kassan länge. Då får ingen annan betala förrän den långsamma och krångliga kunden är klar, och irritation kan uppstå.

Nedan följer en enkel implementation i C++:

struct fifo_node 
{
  struct fifo_node *next;
  value_type value;
};

class fifo
{
  fifo_node *front;
  fifo_node *back;

  fifo_node *dequeue(void)
  {
    fifo_node *tmp = front;
    front = front->next;
    return tmp;
  }

  queue(value)
  {
    fifo_node *tempNode = new fifo_node;
    tempNode->value = value;
    back->next = tempNode;
    back = tempNode;
  }
};

Se även

• LIFO Last In, First Out