[GO] C-Sprache ALDS1_3_B Warteschlange

Problem

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_3_B&lang=ja

Der Punkt

** Queue ** oder ** Queue ** ist eine der grundlegenden ** Datenstrukturen ** eines Computers. Es enthält Daten in einer First-In- und First-Out-Listenstruktur. Beim Abrufen von Daten aus der Warteschlange werden die zuerst eingegebenen Daten der Reihe nach abgerufen. Das Einfügen von Daten in eine Warteschlange wird als Encuing und das Herausnehmen von Daten als Decuing bezeichnet.

Mit anderen Worten, die Tokoten-Methode

Die Round-Robin-Planung [^ 1] kann mithilfe von Warteschlangen simuliert werden, in denen Prozesse gespeichert (verwaltet) werden. Zunächst werden die Prozesse im Ausgangszustand der Reihe nach in die Warteschlange gestellt. Wiederholen Sie als Nächstes, bis die Warteschlange leer ist, den Vorgang "Nehmen Sie den Prozess von Anfang an heraus, verarbeiten Sie höchstens Quantum [^ 2] und fügen Sie ihn erneut zur Warteschlange hinzu, wenn die erforderliche Verarbeitung (Zeit) noch besteht". ..

[^ 1]: Round Robin ist in englischer Sprache als Round Robin geschrieben. Es ist ein Wort, das bedeutet, dass einige Rollen und Wendungen unter bestimmten Bedingungen in der richtigen Reihenfolge ausgetauscht werden. Es wird an verschiedenen Stellen verwendet, beispielsweise bei der Aufgabenverwaltung des Betriebssystems eines PCs auf einfache, aber ebenso ewige Weise, ohne einen speziellen Kopf zu verwenden.

[^ 2]: Die maximale Anzahl von Prozessen, die die CPU verarbeiten kann. Der Bereich, der gleichzeitig verarbeitet werden kann.

Warteschlangenoperation

• enqueue(x)
• Fügen Sie das Element x am Ende der Warteschlange hinzu.
• dequeue()
• Rufen Sie ein Element vom Anfang der Warteschlange ab.
• isEmpty() --Überprüfen Sie, ob die Warteschlange leer ist.
• isFull() --Überprüfen Sie, ob die Warteschlange voll ist.

Implementierung

• Q
• Eindimensionales Array vom Typ Ganzzahl zum Speichern von Daten
• head
• Ganzzahlvariable, die der erste Zeiger ist
• tail
• Eine Ganzzahlvariable, die ein Endzeiger ist
• enqueue(x)
• Eine Funktion, die einer Warteschlange ein Element hinzufügt
• dequeue()
• Eine Funktion, die Elemente vom Anfang der Warteschlange abruft

Code

#include <stdio.h>
#include <string.h>
#define LEN 100000

typedef struct
{
    char name[100];
    int time;
} Process;

/* global variable */
static Process Q[LEN];
static int head, tail, n;

/* enqueue */
void enqueue(Process process_obj)
{
    Q[tail] = process_obj;
    tail = (tail + 1) % LEN;
}

/* dequeue */
Process dequeue()
{
    Process process_obj;

    process_obj = Q[head];
    head = (head + 1) % LEN;

    return process_obj;
}

int min(int a, int b) { return a < b ? a : b; }

int main(void)
{
    int elapse_time = 0;
    int time_ms;
    int qms;
    Process process_obj;

    /* input */
    scanf("%d %d", &n, &qms);
    for (int i = 1; i <= n; i++)
    {
        scanf("%s", Q[i].name);
        scanf("%d", &Q[i].time);
    }

    /* initialize */
    head = 1;
    tail = n + 1;

    while (head != tail)
    {
        process_obj = dequeue();
        time_ms = min(qms, process_obj.time);
        process_obj.time -= time_ms;
        elapse_time += time_ms;

        if (process_obj.time > 0)
            enqueue(process_obj);
        else
            printf("%s %d\n", process_obj.name, elapse_time);
    }
    return 0;
}

Punkt

• Nicht verwendetes Quantum wird nicht übertragen. --20 --100 = 0 und die Schleife wird fortgesetzt.
• Durch Ausführen eines modularen Vorgangs wird die Warteschlange in einem Ring und Schleifen verbunden.

Impressionen

• Die Variablennamen in der Erklärung, die ich mir ansah, waren zu stark vereinfacht, deshalb habe ich sie ergänzt. ――Ich konnte es ohne sorgfältiges Debuggen nicht verstehen. ――Wenn Sie sich die Form eines Rings vorstellen, ist es schwierig, das Konzept von Kopf und Schwanz zu verstehen. Es ist daher besser, ein Bild von einer Zunge in der Wange zu haben und es so zu betrachten, als ob es herausgenommen, verarbeitet und aufbewahrt würde.

Zeitaufwand 180 Minuten

【Rezension】

• 2020/04/05 ――Wenn ich es selbst schrieb, wurde es die folgende Schreibweise. Dieser scheint besser zu sein.
• Manipulieren Sie Kopf und Schwanz, anstatt die gesamte Warteschlange zu manipulieren. ――Ich habe die Idee vergessen, beim Löschen der Warteschlange mit modularer Berechnung zu verwenden
• Nicht implementiert
• Erforderliche Zeit: 80 Minuten

    while (head != tail)
    {
        process_obj = dequeue();
        if(process_obj.time > qms){
            process_obj.time -= qms;
            elapse_time += qms;
            enqueue(process_obj);
        } else {
            elapse_time += process_obj.time;
            printf("%s %d\n", process_obj.name, elapse_time);
        }
     }