Cyclic queue on the example of the C language

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 insert ( spos ) and extract ( rpos ) indexes so 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 circular 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 <Enter>. The characters entered are not displayed, since the first process is given priority over the output to the screen. After pressing <Enter>, 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 <stdio.h>
 #include <conio.h>
 #include <stdlib.h>

 #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 <Enter>.  * /
   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 * /
 }

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

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