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 strings containing meeting descriptions.

  #define MAX 100

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

 / * Save 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.

Fig. 22.1. Sample index "catching up" insertion index

  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 
 #include 
 #include 
 #include 

 #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 

   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 

 / * Deleting an appointment from the 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”.

Cyclic queue

When studying the previous example of the meeting scheduling program, you might have thought of the following way to improve it: when you reach the end of the array in which the queue is stored, you can not stop the program, but set the insertion indexes ( spos ) and extracts ( rpos ) so that they pointed to the beginning of the array. This will allow to place in the queue any number of items subject to their timely retrieval. This implementation of the queue is called a cyclic queue , since the array is used as if it is not a linear list, but a ring.

To organize a cyclic queue in the scheduler, the functions qstore () and qretrieve () need to be rewritten as follows:

  void qstore (char * q)
 {
   / * The queue is full when spos are on one
      less than rpos, or when spos indicates
      at the end of the array, and rpos - at the beginning.
   * /
   if (spos + 1 == rpos || (spos + 1 == MAX &&! rpos)) {
     printf ("The list is full \ n");
     return;
   }

   p [spos] = q;
   spos ++;
   if (spos == MAX) spos = 0;  / * set to start * /
 }

 char * qretrieve (void)
 {
   if (rpos == MAX) rpos = 0;  / * set to start * /
   if (rpos == spos) {
     printf ("There are no more meetings. \ n");
     return NULL;
   }
   rpos ++;
   return p [rpos-1];
 }

In this version of the program, the queue is full when the record index is immediately before the extraction index; otherwise, there is still room to insert the event. The queue is empty when rpos equals spos .

Probably, most often cyclic queues are used in operating systems for storing information recorded and written to disk files or to the console. Cyclic queues are also used in real-time processing programs, which must continue to process information while buffering I / O requests. Many word processors use this technique during paragraph reformatting or line alignment. The entered text is not displayed on the screen until the end of the process. To do this, the application must validate keystrokes during the execution of another task. If a key has been pressed, the character entered is quickly placed in the queue, and the process continues. After it is completed, characters are retrieved from the queue.

In order to experience in practice this application of cyclic queues, let's consider a simple program consisting of two processes. The first process in the program displays numbers from 1 to 32,000. The second process places the characters in a queue as they are entered, without displaying them on the screen until the user presses . The characters entered are not displayed, since the first process is given priority over the output to the screen. After pressing , characters from the queue are retrieved and printed.

For the program to work as described above, it is necessary to use two functions that are not defined in the standard C language: _kbhit () and _getch () . The _kbhit () function returns TRUE if a key was pressed on the keyboard; otherwise, it returns FALSE. The _getch () function reads the entered character, but does not duplicate it on the screen. The C language standard does not provide functions for checking the status of the keyboard or reading characters without being displayed on the screen, since these functions depend on the operating system. However, most compiler libraries have functions that perform these tasks. The small program shown here is compiled using the Microsoft compiler.

  / * An example of a circular queue as a keyboard buffer.  * /
 #include 
 #include 
 #include 

 #define MAX 80

 char buf [MAX + 1];
 int spos = 0;
 int rpos = 0;

 void qstore (char q);
 char qretrieve (void);

 int main (void)
 {
   register char ch;
   int t;

   buf [80] = '\ 0';

   / * Accept characters before pressing .  * /
   for (ch = '', t = 0; t <32000 && ch! = '\ r'; ++ t) {
     if (_kbhit ()) {
       ch = _getch ();
       qstore (ch);
     }
     printf ("% d", t);
     if (ch == '\ r') {
       / * Display the contents of the keyboard buffer
          and free the buffer.  * /
       printf ("\ n");
       while ((ch = qretrieve ())! = '\ 0') printf ("% c", ch);
       printf ("\ n");
     }
   }
   return 0;
 }

 / * Enter a character in the queue.  * /
 void qstore (char q)
 {
   if (spos + 1 == rpos || (spos + 1 == MAX &&! rpos)) {
     printf ("The list is full \ n");
     return;
   }
   buf [spos] = q;
   spos ++;
   if (spos == MAX) spos = 0;  / * set to start * /
 }

 / * Getting the character from the queue.  * /
 char qretrieve (void)
 {
   if (rpos == MAX) rpos = 0;  / * set to start * /
   if (rpos == spos) return '\ 0';

   rpos ++;
   return buf [rpos-1];

}