C++. Queue. General concepts. Ways to implement the queue. Implementing a queue as a dynamic array

Queue. General concepts. Ways to implement the queue. Implementing a queue as a dynamic array


Contents


1. Queue data structure. Features of the implementation of the queue

A queue is a dynamic data structure that consists of a set of elements that are placed sequentially one after another. In this case, the addition of elements is carried out on the one hand, and the removal (stretching) on the other hand.
The queue works according to the FIFO principle – First In – First Out. Figure 1 shows the principle of operation of the queue.

The dynamic data structure Queue

Figure 1. The dynamic data structure Queue

One of the features of the queue is that in the queue some of the sequential elements can be occupied at a given moment in time (Figure 2).

A queue in which some of the elements are currently occupied

Figure 2. A queue in which some of the elements are currently occupied

In everyday life, the use of a queue is quite common, for example:

  • queue in the store;
  • queue of documents for printing on a printer;
  • a sequence of operators in the algorithm that are executed one after another;
  • other cases.

 

2. Types of Queues

The following types of queues are distinguished:

  • simple queue;
  • circular queue. In such a queue, an element that comes from the beginning of the queue will be placed at its end;
  • priority queue. In such a queue, elements are placed according to their priorities (weighting factors). The first item in the queue is the one with the highest priority.

Any type of queue may have a size limit (the number of elements in the queue).

 

3. Ways to implement a Queue

In the program, the queue can be implemented as:

  • static array with size limit in the queue;
  • dynamic array;
  • singly linked list;
  • doubly linked list.

 

4. Circular Queue

In the circular queue, the element that exits (is deleted) from the queue is placed at its end (Figure 3).

Circular Queue

Figure 3. Circular Queue

Figure 4 shows the operation of the ring queue in the case when some of the elements are busy.

Circular Queue. The case when some of the elements are busy

Figure 4. Circular Queue. The case when some of the elements are busy

Examples of circular queue:

  • the movement of trams on a circular route;
  • an event queue for processing them in Windows.

 

5. Queue with priorities. Implementation ways

В очереди с приоритетами элемент, имеющий наивысший приоритет, выходит (удаляется) первым. In the priority queue, each element is assigned a priority (weight coefficient).

The priority queue can be implemented in one of two ways:

  • Queue with priority inclusion. In this case, the element that is added to the queue is immediately placed in it in accordance with its priority (Figure 5). When deleted, this item is simply pulled from the end of the queue;
  • Queue with the priority exclusion. In this case, the new item is simply added to the end of the queue. And pulling an element from the queue is carried out according to its priority, that is, the element with the highest priority is pulled (Figure 6).

 

The queue with priority inclusion. Adding a new item according to its priority

Figure 5. The queue with priority inclusion. Adding a new item according to its priority

Queue with priority exclusion. The item is added to the end of the queue, pulled according to priority

Figure 6. Queue with priority exclusion. The item is added to the end of the queue, pulled according to priority



 

6. An example implementation of a queue in the form of a dynamic array

In the example, the Queue template class is declared, which implements the queue in the form of a dynamic array for some generalized type T.

The following fields and methods are implemented in the class:

  • integer internal variable count – the number of elements in the queue;
  • internal variable p is a pointer to type T. This pointer is an array of data forming a queue. An array element with index 0 is the beginning of the queue. The element with index count-1 is the end of the queue;
  • default constructor;
  • copy constructor Queue(const Queue&);
  • copy operator operator=(const Queue&);
  • method push() – adds an item to the end of the queue;
  • destructor;
  • method pop() – pulls the first element from the queue;
  • method GetItem() – reads the first element from the queue without pulling it;
  • method clear() – clears the queue;
  • method IsEmpty() – checks if the queue is empty;
  • method Get() – returns the number of elements in the queue;
  • method print() – displays the queue on the screen.

The class code is as follows:

#include <iostream>
#include <new>
using namespace std;

// Dynamic data structure Queue
template <typename T>
class Queue
{
private:
  T* p; // dynamic array
  int count; // number of items in the queue

public:
  // default constructor
  Queue()
  {
    count = 0; // queue is empty
  }

  // copy constructor
  Queue(const Queue& obj)
  {
    // copy obj to the current object
    count = obj.count;

    try {
      // attempt to allocate memory for p
      p = new T[count];
      // fill with values
      for (int i = 0; i < count; i++)
        p[i] = obj.p[i];
    }
    catch (bad_alloc e)
    {
      // if no memory is allocated, then display the error text
      cout << e.what() << endl;
      count = 0; // create an empty queue
    }
  }

  // add item to the queue
  void push(T item)
  {
    T* p2; // declare an additional pointer
    p2 = p; // redirect an additional pointer to p

    try {
      // attempt to allocate a new piece of memory for p, but 1 more
      p = new T[count + 1];

      // copy data
      for (int i = 0; i < count; i++)
        p[i] = p2[i];

      // copy last item
      p[count] = item;

      // increase the number of items by 1
      count++;

      // release previously allocated memory
      if (count > 1)
        delete[] p2;
    }
    catch (bad_alloc e)
    {
      // if no memory is allocated
      cout << e.what() << endl; // display error message

      // return old pointer to p
      p = p2;
    }
  }

  // pull the first item from the queue
  T pop()
  {
    if (count == 0)
      return 0;

    // fill in the item that is pulled from the queue
    T item;

    item = p[0];

    // form a new piece of memory that is 1 less
    try {
      T* p2;

      // attempt to allocate memory
      p2 = new T[count - 1];

      count--;

      // p=>p2
      for (int i = 0; i < count; i++)
        p2[i] = p[i + 1]; // all but the first element are copied

      // release the section pointed to by p
      if (count > 0)
        delete[] p;

      // redirect p to p2
      p = p2;

      // return item
      return item;
    }
    catch (bad_alloc e)
    {
      // if memory is not allocated, then return 0
      cout << e.what() << endl;
      return 0;
    }
  }

  // operator function operator=(),
  // implements assignment of objects of type Queue
  Queue& operator=(const Queue& obj)
  {
    T* p2; // pointer to additional memory

    try {
      // attempt to allocate memory for p2
      p2 = new T[obj.count];

      // if the memory is allocated successfully,
      // you can free pre-allocated memory for p
      if (count > 0)
        delete[] p;

      // copy obj to the current object
      p = p2; // redirect p to p2
      count = obj.count;

      // fill with values
      for (int i = 0; i < count; i++)
        p[i] = obj.p[i];
    }
    catch (bad_alloc e)
    {
      // if the memory is not allocated, then display the corresponding message
      cout << e.what() << endl;
    }

    return *this; // return the current object
  }

  // destructor
  ~Queue()
  {
    if (count > 0)
      delete[] p;
  }

  // take the first element from the queue without pulling it
  T GetItem()
  {
    if (count > 0)
      return p[0];
    else
      return 0;
  }

  // queue clearing
  void clear()
  {
    if (count > 0)
    {
      delete[] p;
      count = 0;
    }
  }

  // checking the existence of elements in the queue
  bool IsEmpty()
  {
    return count == 0;
  }

  // number items in the queue
  int GetN()
  {
    return count;
  }

  // method that displays queue
  void print(const char* objName)
  {
    cout << "Object: " << objName << endl;
    for (int i = 0; i < count; i++)
      cout << p[i] << "\t";
    cout << endl;
    cout << "---------------------" << endl;
  }
};

void main()
{
  Queue<int> Q1;
  Q1.print("Q1");

  Q1.push(5);
  Q1.print("Q1");

  Q1.push(8);
  Q1.push(11);
  Q1.push(17); // Q1 = {5,8,11,17}
  Q1.print("Q1");

  int d;
  d = Q1.GetItem();
  cout << "d = " << d << endl;

  Q1.print("Q1");

  Queue<int> Q2 = Q1;
  Q2.print("Q2");

  Queue<int> Q3;
  Q3 = Q1 = Q2;
  Q1.push(333);
  Q2.push(555);

  Q1.print("Q1");
  Q2.print("Q2");
  Q3.print("Q3");

  Q2.clear();
  if (Q2.IsEmpty())
    cout << "OK" << endl;
  else
    cout << "NO" << endl;

  cout << "n = " << Q3.GetN() << endl;
}

The result of the program

Object: Q1

---------------------
Object: Q1
5
---------------------
Object: Q1
5 8 11 17
---------------------
d = 5
Object: Q1
5 8 11 17
---------------------
Object: Q2
5 8 11 17
---------------------
Object: Q1
5 8 11 17 333
---------------------
Object: Q2
5 8 11 17 555
---------------------
Object: Q3
5 8 11 17
---------------------
OK
n = 4

 


Related topics