Queue data structure with C++

Contrary to a Stack, the queue data structure uses FIFO (First In, First Out). In order to explain this concept, we can imagine some people standing in a line.

Where person A (Blue) is the first one to enter the line. A will then be the last to go out from the line. Person F (Grey) is the last to enter, so the person will therefor be the last to get out from the line. With other words, with FIFO the first element in a sequence will also be the first to go out of the sequence.

Creating a queue class with C++ we will need some functions, such as enqueue(), dequeue(), queue_size(), is_empty() and display(). So let's make a class with those.

#define SIZE 10
class Queue {
public:

       Queue() {

             front = -1;

             rear = -1;

       }

       void display();

       void enqueue(int n);

       void dequeue();
       void queue_size();

       bool is_empty();

bool is_full();

private:

       int st[SIZE];

       int st_size = 0;

       int front;

       int rear;

};

Let's start by looking at certain aspects of the class. The class is based on 6 functions, 1 constructor (Essentially a function) and 4 private variables. The private variables has an array called st[ ], with a size of SIZE (In this case we defined it as 10). A variable called st_size that we will use for measuring the number of elements in the array, and lastly a front and rear variable.

First and foremost we can look at the constructor, where we're setting front = -1 and rear = -1. The reason for this is because we want to create a navigation system, which can visually be seen as.

In the image above we can see that rear and front is pointing towards a grey circle. This is an illustration to show that rear and front is pointing to something outside of the queue. The reason we're not setting rear and front equal to zero in the first place, is simply because we want to check if we've created an queue or not. Because, as soon as front = 0 and rear = 0 we won't know if there's something there or not. But we will be able to know if the queue is created or not if they're outside.

Maybe this will be clearer if we look at how some of the functions works. Let's start with the is_full() and is_empty() function.

bool Queue::is_full() {

       if (rear == SIZE - 1) {

             return true;

       }

       else {

             return false;

       }

}

bool Queue::is_empty() {

       if (front == -1) {

             return true;

       }

       else {

             return false;

       }

}

Here we can see that in is_empty() we'll see the queue as empty if front is equal to -1. While in is_full() if rear is equal to SIZE - 1, we will already have filled the last spot in the queue. Which means that we cannot exceed this, and therefor it's considered as full.

Now, to the enqueue() function.

void Queue::enqueue(int n) {

       if (is_full()) {

             std::cout << std::endl << "Queue is full" << std::endl;

       }

       else {

             if (front == -1){
                   front = 0;
             }

             rear = (rear + 1) % SIZE;

             st[rear] = n;

             std::cout << std::endl << "Inserted: " << n << std::endl;

             st_size++;

       }
}

In this function we are taking in a paramter int n. From there we will first try to check if the queue is full or not. If it's full, we'll do nothing but print out a message about the queue being full. If it's not full and front is equal to -1 (Meaning that the queue was empty), we will set front equal 0. Indicating that we have now started the queue. Visually this can be seen as.

Now let us imagine that we are enqueuing the numbers: 2, 8, 6, 12, 14, 96, 38, 27, 99 and 13. With that we first placed 13 into the queue, followed by 99 and so on. The sequence in the array will then be.

What's happening here is that we're placing the numbers into the array st[ ]. Where we first sent 13 through enqueue(int n), defining n = 13. Since the queue is empty at this point, we will go right into the if-statement about front being -1. Which will result in front being set as 0. We will then move out of the if-statement and set rear as rear = (rear + 1) % SIZE. In this case, rear = (-1 + 1) % SIZE will land on rear = 0. From there we will overwrite the array index at position rear with st[rear] = n.

With this logic we will have 2 at rear = 0 (Which is the front), then 8 at rear = (0 + 1) = 1, 6 at rear = (1 + 1) = 2 and so forth. In other words, we will have the same array as pictured above. Now let's move on with dequeue().

void Queue::dequeue() {

       if (is_empty()) {

             std::cout << "Can't dequeue anything. Queue is empty." << std::endl;

       }

       else {

             if (front == rear) {

                    Queue();

             }

             int element = st[front];

             front++ % SIZE;

             std::cout << "Removed: " << element << std::endl;

             st_size--;

       }

}

In this function we're first checking if the queue is empty. Because if it is, then there's really nothing to dequeue. However, if it isn't we'll move into the else-statement. Where we will first do a check to see if there's only one element in the queue, namely checking if front == rear. If that's true, then we will run the constructor again, which restart the whole queue and set front and rear equal to -1. From there we will create a temporary variable called element and set it equal to the number we want to dequeue. Then we will increase front with 1 and print out a message saying we removed element from the queue. Lastly, we will decrease the size of the queue.

Moving onto display().

void Queue::display() {

       std::cout << "Your Queue consists of: ";

       for (int i = front; i < rear + 1; i++) {

             std::cout << st[i] << " ";

       }

       std::cout << std::endl;

}

This is a simple function, where we are just printing out the content of the array with a for-loop. We are starting at front and when we're at rear + 1 we end the loop.

Lastly, the queue_size() function.

void Queue::queue_size() {

       std::cout << "Size of queue is " << st_size << std::endl;

}

This is the simplest of all the functions. We are just using the variable that we have been either adding to, or taking from.