先进先出算法

Data Queue.svg

先进先出算法(英语:first in, first out,简称 FIFO)是一种计算机科学的排程算法。它描述了一个伫列所使用的先到先得服务方式:先进入伫列的工作将先被完成,之后进来的则必须稍候。

范例

一个C++语言的范例

#include <iostream>
#include <stdexcept>
 
template <typename T>
class FIFO
{
private:

    struct Node {
        T     value;
        Node *next;

        Node(T _value) : value(_value), next(NULL) {}
    };

    Node *front;
    Node *back;

public:
    FIFO() : front(NULL), back(NULL) {}

    ~FIFO() {
        while (front != NULL)
            dequeue();
    }

    void enqueue(T _value) {
        Node *newNode = new Node(_value);

        if (front == NULL)
            front = newNode;
        else
            back->next = newNode;

        back = newNode;
    }

    T dequeue() {
        if (front == NULL)
           throw std::underflow_error("Nothing to dequeue");

        Node *temp   = front;        
        T     result = front->value;

        front = front->next;
        delete temp;

        return result;
    }
};