Ring queue. Developing a template class that implements a ring queue

Search other resources:

1. Ring queue. General concepts

The ring queue works on the principle of FIFO (First – In – First – Out): first in, first out. The difference between a ring queue and a regular queue is how the first element exits the queue. In a ring queue, the first element is moved to the end of the queue. Examples of a ring queue can be the movement of trolleybuses along a ring route, the water cycle in nature, etc.

Figure 1. Ring Queue. Move the first element to the end of the queue

The ring queue works according to the following principle.

First, elements are added to the queue until some maximum is reached. Elements are added to the end of the queue.
After reaching a certain (maximum) number of elements, the first element is cyclically changed according to the following principle: the first element of the queue is moved to the end of the queue, and the remaining elements of this queue are shifted one position forward. Thus the second element of the queue becomes the first, the third element becomes the second, and so on.

The basic list of operations performed for the ring queue is as follows:

add a new element to the queue;
check if the queue is empty;
check whether the queue is full;
clearing the queue (deleting all elements of the queue);
pull the first element from the queue and place it at the end of the queue.

⇑

2. Features of the program implementation of the ring queue

In program implementation, the queue is implemented in the QueueRing<T> class as a dynamic array. The proposed QueueRing<T> class implements the following internal fields that store the state of the queue:

queue – the last element in the queue;
count – current number of elements in the queue (current queue length);
maxCount – maximum number of elements in the queue (maximum queue length).

The QueueRing class contains the implementation of the following methods (functions):

constructor QueueRing(int) – creates a queue;
copy constructor QueueRing(const QueueRing&) – called when one queue is assigned to another during declaration;
copy operator QueueRing(const QueueRing&) – called when one queue is assigned to another;
isEmpty() method – checking if the queue is empty;
method Clear() – clearing the queue;
isFull() method – checking if the queue is full;
Add(T) – add a new element to the queue;
Move() – pull the first element from the queue and place it at the end of the queue;
method Print() – print the elements of the queue.

Optionally, the QueueRing<T> class can be extended by adding new methods. For example, get a queue element at a given position, add a group of elements to a queue, merge two queues, etc.

⇑

3. Program code of the template class QueueRing<T>, which implements a ring queue

#include <iostream>
using namespace std;

// Ring Queue
template <typename T>
class QueueRing
{
private:
  T* queue; // the last element in the queue
  int count; // the current length of the queue
  int maxCount; // maximum queue size

  // The method that copies the queue
  void Copy(const QueueRing<T>& obj)
  {
    // 1. Release the memory previously allocated for the queue
    if (maxCount > 0)
      delete[] queue;

    // 2. Copy data
    try
    {
      count = obj.count;
      maxCount = obj.maxCount;

      // allocate memory for the new queue
      queue = new T[maxCount];

      // data copy loop
      for (int i = 0; i < maxCount; i++)
        queue[i] = obj.queue[i];
    }
    catch (bad_alloc e)
    {
      cout << e.what() << endl;
    }
  }

public:
  // Constructor
  QueueRing(int _maxCount)
  {
    // Create a queue of size _maxCount
    try
    {
      maxCount = _maxCount;
      queue = new T[maxCount]; // allocate memory for the queue
      count = 0; // while the queue is empty
    }
    catch (bad_alloc e)
    {
      cout << e.what() << endl;
    }
  }

  // Copy constructor
  QueueRing(const QueueRing& obj)
  {
    Copy(obj);
  }

  // Copy operator
  QueueRing<T> operator=(const QueueRing& obj)
  {
    Copy(obj);
    return *this;
  }

  // Clearing the Queue
  void Clear()
  {
    count = 0;
  }

  // Destructor
  ~QueueRing()
  {
    if (maxCount > 0)
      delete[] queue; // release the memory allocated for the queue
  }

  // Checking if the queue is empty?
  bool isEmpty()
  {
    return count == 0;
  }

  // Get the number of items in the queue
  int Count()
  {
    return count;
  }

  // Checking if the queue is full?
  bool isFull()
  {
    return count == maxCount;
  }

  // Add a new element to the queue
  void Add(T item)
  {
    if (!isFull()) // if the queue is not full
      queue[count++] = item;
  }

  // Pull the first element from the queue and push it to the end of the queue
  bool Move()
  {
    if (!isEmpty()) // If the queue is full
    {
      // save the first element
      T item = queue[0];

      // shift of elements
      for (int i = 1; i < count; i++)
        queue[i - 1] = queue[i];

      // put the first element at the end of the queue
      queue[count - 1] = item;
      return true;
    }
    else
      return false;
  }

  // The method that outputs the queue
  void Print(string msg)
  {
    cout << msg + " ";
    for (int i = 0; i < count; i++)
      cout << queue[i] << " ";
    cout << endl;
  }
};

void main()
{
  // Create a queue of up to 4 int elements
  QueueRing<int> Q(4);
  Q.Print("Q(4): ");

  // Add elements to the queue
  Q.Add(25);
  Q.Add(30);
  Q.Add(70);
  Q.Add(10);
  Q.Add(7);
  Q.Print("Q.Add(...): ");

  // Move elements 1 time
  Q.Move();
  Q.Print("Q.Move(): ");

  // Move items 1 more time
  Q.Move();
  Q.Print("Q.Move(): ");

  QueueRing<int> Q2 = Q;
  Q2.Print("Q2: ");

  QueueRing<int> Q3 = Q;
  Q3.Print("Q3: ");
}

⇑

4. Explanation of the program code of some methods of the QueueRing<T> class

At the beginning, an empty queue is created that does not contain a single element. The QueueRing(int) class constructor takes one parameter: the maximum size of the queue. The constructor allocates memory for the entire maximum allowed queue size.

Adding an element to the end of the queue is implemented in the Add() method. The element is added if the queue is not yet filled to the maximum. The current length of the queue (count) is compared with the maximum length of the maxCount queue. If the queue is full (count==maxCount), then the element is not added to the end of the queue.

After the queue reaches its maximum, it is possible to implement a cyclic movement of the elements of queue. This is done in the Move() method, which:

moves the first element to the end of the queue;
cyclic shift of all subsequent elements by one position forward.

The Move() method is only relevant if the queue is full (count==maxCount).

The queue is cleared in the Clear() method. To implement cleanup, the value of the current queue length is set to zero. There is no need to free memory here.

Since the class contains a pointer, the class contains an implementation of the copy constructor and the copy operator. The copy constructor and copy operator implement the correct use of the assignment (=) operation from one queue to another. These methods call the Copy() internal method, which makes a copy from the queue. The copy constructor and copy operator are needed to avoid the disadvantages of bitwise copying. More details about the features of bitwise copying are described here.

The ~QueueRing() destructor frees the memory allocated for the queue.

BestProg

C++. Ring queue. Developing a template class that implements a ring queue

Ring queue. Developing a template class that implements a ring queue

Contents

1. Ring queue. General concepts

⇑

2. Features of the program implementation of the ring queue

⇑

3. Program code of the template class QueueRing<T>, which implements a ring queue

⇑

4. Explanation of the program code of some methods of the QueueRing<T> class

⇑

Related topics

⇑

Programming: theory and practice