C language ALDS1_3_B Queue

problem

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

The point

** Queue ** or ** Queue ** is one of the basic ** data structures ** of a computer. Data is held in a first-in, first-out list structure. When retrieving data from the queue, the data that was put in first is fetched in order. Putting data in a queue is called enqueue, and taking it out is called dequeue.

In other words, the Tokoroten method

Round robin [^ 1] scheduling can be simulated using queues that store (manage) processes. First, the processes in the initial state are queued in order. Next, until the queue is empty, repeat the process of "taking out the process from the beginning, processing at most Quantum [^ 2], and adding it to the queue again if the required processing (time) still remains". ..

[^ 1]: Round Robin is written in English as Round Robin. It is a word that means that some roles and turns are exchanged in order under certain conditions. It is used in various places such as task management of the OS of a personal computer in a simple but equally eternal way without using a special head.

[^ 2]: The maximum q ms of processes that can be processed by the CPU. The range that can be processed at one time.

Queue operation

• enqueue(x) --Add element x to the end of the queue.
• dequeue() --Retrieve an element from the beginning of the queue.
• isEmpty() --Check if the queue is empty.
• isFull() --Check if the queue is full.

Implementation

• Q --Integer one-dimensional array for storing data
• head --Integer variable that is the first pointer
• tail --An integer variable that is a tail pointer
• enqueue(x) --Functions that add elements to the queue
• dequeue() --A function that retrieves an element from the beginning of a queue

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;
}

point

--Unused Quantum will not be carried over. --20 --100 = 0 and the loop progresses. --By performing modulo operation, cues are connected in a ring and loop.

Impressions

--The variable names in the commentary I was looking at were oversimplified, so I supplemented them. ――I couldn't understand it unless I debugged it carefully. ――If you imagine the shape of a ring, the concept of head and tail becomes difficult to understand, so it is better to have an image of a tokoroten and look at it as if you were taking it out, processing it, and storing it.

Time required 180 minutes

【review】

• 2020/04/05 ――When I wrote it myself, it became the following way of writing. This one seems to be better. --Manipulate head and tail instead of manipulating the entire queue. --I forgot the idea of using modulo operations while clearing cues.
• Unimplemented --Time required: 80 minutes

    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);
        }
     }