Queues on the example of the C language

A queue is a linear list of information, working with which is based on the principle “first come, first go out” (first-in, first-out); This principle (and the queue as a data structure) is sometimes also called FIFO ^[1] . This means that the first queued item will be retrieved from it first, the second placed item will be retrieved second, and so on. This is the only way to work with the queue; random access to individual items is not allowed.

Queues are very common in real life, for example, near banks or fast-food restaurants. To imagine the work of the queue, let's introduce two functions: qstore () and qretrieve () (from "store" - "save", "retrieve" - ​​"receive"). The qstore () function places an element at the end of a queue, and the qretrieve () function removes an element from the front of the queue and returns its value. In tab. 22.1 shows the effect of the sequence of such operations.

It should be borne in mind that the extraction operation removes the item from the queue and destroys it, if it is not stored somewhere else. Therefore, after all items are retrieved, the queue will be empty.

In programming, queues are used to solve many problems. One of the most popular types of such tasks is simulation. Queues are also used in operating system task schedulers and in I / O buffering.

To illustrate the work of the queue, we will write a simple meeting scheduling program. This program allows you to save information about a certain number of meetings; then as you go through each meeting, it is removed from the list. To simplify the description of the meetings is limited to 255 characters, and the number of meetings - an arbitrary number of 100.

When developing this simple scheduling program, you first need to implement the functions of qstore () and qretrieve () described here. They will store pointers to lines containing meeting descriptions.

  #define MAX 100

 char * p [MAX];
 int spos = 0;
 int rpos = 0;

 / * Saving the meeting.  * /
 void qstore (char * q)
 {
   if (spos == MAX) {
     printf ("The list is full \ n");
     return;
   }
   p [spos] = q;
   spos ++;
 }

 / * Getting a meeting.  * /
 char * qretrieve ()
 {
   if (rpos == spos) {
     printf ("There are no more meetings. \ n");
     return '\ 0';
   }
   rpos ++;
   return p [rpos-1];
 }

Note that these two functions require two global variables: spos , which stores the index of the next free space in the list, and rpos , which stores the index of the next item to be sampled. Using these functions, you can organize a queue of data of another type, simply by changing the base type of the array they process.

The qstore () function places the descriptions of new meetings at the end of the list and checks if the list is full. The qretrieve () function retrieves meetings from the queue, if any. When assigning appointments, the value of the spos variable increases , and as they pass, the value of the rpos variable increases . Essentially, rpos "catches" spos in the queue. Figure 22.1 shows what can happen in memory when a program is executed. If rpos and spos are equal, there are no scheduled events. Even though the qretrieve () function does not physically destroy the information stored in the queue, this information can be considered destroyed, since it cannot be re-accessed.

  Start queue

   ↓ spos
 + --- + --- + --- + --- + --- + --- + --- + --- + --- + --- + + --- +
 |  |  |  |  |  |  |  |  |  |  |  |
 + --- + --- + --- + --- + --- + --- + --- + --- + --- + --- + + --- +
   ↑ rpos

	 qstore ('A')

       ↓ spos
 + --- + --- + --- + --- + --- + --- + --- + --- + --- + --- + + --- +
 |  A |  |  |  |  |  |  |  |  |  |  |
 + --- + --- + --- + --- + --- + --- + --- + --- + --- + --- + + --- +
   ↑ rpos

	 qstore ('B')

           ↓ spos
 + --- + --- + --- + --- + --- + --- + --- + --- + --- + --- + + --- +
 |  A |  B |  |  |  |  |  |  |  |  |  |
 + --- + --- + --- + --- + --- + --- + --- + --- + --- + --- + + --- +
   ↑ rpos

	 qretrive ()

           ↓ spos
 + --- + --- + --- + --- + --- + --- + --- + --- + --- + --- + + --- +
 |  |  B |  |  |  |  |  |  |  |  |  |
 + --- + --- + --- + --- + --- + --- + --- + --- + --- + --- + + --- +
       ↑ rpos

	 qretrive ()

           ↓ spos
 + --- + --- + --- + --- + --- + --- + --- + --- + --- + --- + + --- +
 |  |  |  |  |  |  |  |  |  |  |  |
 + --- + --- + --- + --- + --- + --- + --- + --- + --- + --- + + --- +
           ↑ rpos

	 qstore ('A')

               ↓ spos
 + --- + --- + --- + --- + --- + --- + --- + --- + --- + --- + + --- +
 |  |  |  C |  |  |  |  |  |  |  |  |
 + --- + --- + --- + --- + --- + --- + --- + --- + --- + --- + + --- +
           ↑ rpos

The text of the program for a simple meeting planner is complete below. You can modify this program on your own.

  / * Mini Event Scheduler * /

 #include <string.h>
 #include <stdlib.h>
 #include <stdio.h>
 #include <ctype.h>

 #define MAX 100

 char * p [MAX], * qretrieve (void);
 int spos = 0;
 int rpos = 0;
 void enter (void), qstore (char * q), review (void), delete_ap (void);

 int main (void)
 {
   char s [80];
   register int t;

   for (t = 0; t <MAX; ++ t) p [t] = NULL;  / * initialize the array
                                          empty pointers * /

   for (;;) {
     printf ("Enter (E), List (L), Delete (R), Exit (Q):");
     gets (s);
     * s = toupper (* s);

     switch (* s) {
       case 'E':
         enter ();
         break;
       case 'L':
         review ();
         break;
       case 'R':
         delete_ap ();
         break;
       case 'Q':
         exit (0);
     }
   }
   return 0;
 }

 / * Paste into the queue of the new meeting.  * /
 void enter (void)
 {
   char s [256], * p;

   do {
     printf ("Enter appointment% d:", spos + 1);
     gets (s);
     if (* s == 0) break;  / * record was not made * /
     p = (char *) malloc (strlen (s) +1);
     if (! p) {
       printf ("Out of memory. \ n");
       return;
     }
     strcpy (p, s);
     if (* s) qstore (p);
   } while (* s);
 }

 / * View the contents of the queue.  * /
 void review (void)
 {
   register int t;

   for (t = rpos; t <spos; ++ t)
     printf ("% d.% s \ n", t + 1, p [t]);
 }

 / * Deleting appointment from queue.  * /
 void delete_ap (void)
 {
   char * p;

   if ((p = qretrieve ()) == NULL) return;
   printf ("% s \ n", p);
 }

 / * Insert meeting.  * /
 void qstore (char * q)
 {
   if (spos == MAX) {
     printf ("List Full \ n");
     return;
   }
   p [spos] = q;
   spos ++;
 }

 / * Extract meeting.  * /
 char * qretrieve (void)
 {
   if (rpos == spos) {
     printf ("There is no more. \ n");
     return NULL;
   }
   rpos ++;
   return p [rpos-1];
 }

^[1] This principle has other names: “first come, first served”, “in the order of receipt”, “first come, first come out”, “reverse store type”.