Datenstrukturen in c++: Queue

in StemSocial23 days ago

Eine warteschlange (Queue) ist die Umkehrung eines Stacks. Es folgt dem Prinzip First-In-First-Out. Elemente die zuerst eingefügt werden, werden auch zuerst verarbeitet. Um eine Queue besser zu demonstrieren habe ich die Tasks, um eine Funktionalität erweitert. Nun können Tasks eine Priorität von 1,2 oder 3 haben. 3 bedeutet höchste Priorität und 1 niedrige Priorität. Nachdem die Priorität einer Task überprüft wird, wird diese entweder verarbeitet oder wieder an die Queue angehangen. In diesem Fall wird die Priorität von dem angehangenen Task um 1 erhöht. Mit diesem Verhalten kann man eine Prioritätswarteschlange (Priority Queue) simulieren.

Auch hier, wer mehr zur Theorie erfahren möchte: https://peakd.com/hive-196387/@ozelot47/datenstrukturen-queue-warteschlange

cpp_queue.png

#include <iostream>
#include <queue>

class Task {
public:
    int id;
    explicit Task(int id) : id(id) { }
    void doIt(){
        std::cout << "Task-ID: " << id << "\n";
    }
    void increasePriority(){
        id++;
    }
};

void queue(){
    /* the queue is the opposite from a stack. It follows
     * the FIFO princip (First In First Out) */
    std::queue<Task> container;

    /* insert tasks with different prioroties */
    container.push(Task(1));
    container.push(Task(1));
    container.push(Task(3));
    container.push(Task(2));
    container.push(Task(1));

    /* consume all urgent tasks (highest number) first. Increase priority level from
     * waiting tasks */
    while(!container.empty()){
        Task &task = container.front();
        /* very urgent */
        if ( task.id == 3) {
            task.doIt();
            container.pop();
        } else {
            task.increasePriority();
            container.pop();
            container.push(task);
        }
    }
}

int main(){
    queue();
    return 0;
}