Circular buffers (wrap-around queues)

There are times when we want to implement a queue of values (i.e. enqueue at the back of the queue and dequeue from the front) with a fixed maximum size.

For such an implementation an array would seem to be a logical choice (rather than a linked-list style of implementation).

If we keep track of the 'back' of the queue it is easy to enqueue: 

const int QueueSize = 10;
float Queue[QueueSize];
int back = 0; // position to enqueue at
int front = -1; // position to dequeue from, -1 when queue is empty

// to enqueue items simply put them at position 'back' and increment it, 
// and as long as back < QueueSize it is ok

// enqueue 1.0
Queue[back] = 1.0;
back++;

// now enqueue 3.1
Queue[back] = 3.1;
back++;
However, there is a problem: what do we do when we dequeue?

If we want to keep position 0 in the array as the front then we need to shuffle everything forward one position every time we dequeue. This is a slow/cumbersome way of doing things if the array is large and we do a lot of enqueues/dequeues.

We could increment front every time we dequeue, e.g. 

// dequeue and print front element
cout << Queue[front];
front++;
There are some problems though
(i) we need to make sure front doesn't go past back (i.e. we can't do more dequeues than enqueues)
(ii) eventually back hits the end of the array, but (if there have been some dequeues) there may be empty space available at the front of the array

The typical solution is to 'wrap-around' when back or front hit the end of the array. E.g. every time we increment back we check and see if it has reached QueueSize in the example above, and if so we reset it to 0. Similarly anytime we increment front we check to see if it has reached QueueSize, in which case we reset it to 0.

The example below fills in some of the gaps and special cases: 
#include <iostream>
using namespace std;

// maximum number of values that can be
//   stored at any given moment
const int BufferSize = 4;

int main()
{
   // the buffer for storing values
   float buffer[BufferSize];

   // location of current first and last elements in buffer,
   //    both are set to -1 when nothing is in the queue
   int front = -1;
   int back = -1;

   // the number of values currently stored in the queue
   int bsize = 0;

   // let the user go for as long as they want,
   // on each turn they can do any one of:
   //    enqueue an item at the back (if the buffer isn't full)
   //    dequeue the front item (if the buffer isn't empty)
   //    quit
   char cmd;
   do {

      // get the user's command
      cout << "Enter E to enqueue, D to dequeue, or Q to quit" << endl;
      cin >> cmd;
      cmd = toupper(cmd);  // (convert to uppercase for simplicity)

      // handle quit commands
      if (cmd == 'Q') {
         cout << "Bye!" << endl;
      } 

      // handle enqueue commands
      else if (cmd == 'E') {

         // make sure the buffer isn't full
         if (bsize >= BufferSize) {
            cout << "Cannot enqueue, buffer is full" << endl;
         } 

         // get the new value from the user
         // if the queue is empty
         //    then start front and back at 0
         // otherwise
         //    increment back, wrap-around if needed
         //    insert the new value
         //    and update the buffer size
         else {
            float value;
            cout << "Enter the new value:" << endl;
            cin >> value;
            if (front < 0) {
               front = 0;
               back = 0;
               bsize = 1;
               buffer[0] = value;
            } else {
               back++;
               if (back >= BufferSize) {
                  back = 0;
               }
               buffer[back] = value;
               bsize++;
            }
            cout << "Enqueued value " << value << endl;
         }
      }

      // handle dequeue commands 
      else if (cmd == 'D') {

         // make sure the buffer isn't empty
         if (bsize < 1) {
            cout << "Cannot dequeue, buffer is empty" << endl;
         } 

         // copy out the front value,
         // increment front, and wrap-around if needed
         // decrement the size,
         //    and if size drops to 0 reset front/back to -1
         else {
            cout << "Dequeued value " << buffer[front] << endl;
            front++;
            if (front >= BufferSize) {
               front = 0;
            }
            bsize--;
            if (bsize <= 0) {
               front = -1;
               back = -1;
            }
         }
      } 
    
      // handle invalid commands
      else {
        cout << "Invalid command entered" << endl;
      }
   } while (cmd != 'Q');
}