Queue in C++ With Examples [Latest]

We worked on the working as well as the implementation of a Stack in C++ in our previous tutorial. Today in this tutorial, we are going to discuss another data structure, Queue in C++.

What is a Queue?

Basically, a queue is also a linear data structure that follows the First In First Out (FIFO) pattern in the insertion or deletion of data. As far as the pattern is concerned, the first element inserted is deleted first, and the last one to enter the queue is deleted at the last.

Unlike stack, Queue operations take place on both sides. But, note that one operation should be performed on one end, and the other on the other end. Hence, both insertion and deletion operations do not take place on the same side.

Working of Queue in C++

A Queue is analogous to a real-world queue. It works on a first come first serve basis. Hence as mentioned earlier, the first element to enter the queue is deleted first, and the last one to enter is deleted after all the previous members are already deleted. Now let us take a look at the basic operations that can be performed on a queue,

In the next section, we are going to elaborate on the above-mentioned techniques.

1. enqueue() in Queue

enqueue() does the insertion of an element into the queue. It is simply done by adding the element at the end of the queue. So, as we can infer, this operation is performed at the end.

The Algorithm for enqueue is given below,

Procedure ENQUEUE(VALUE)
    If REAR==Size_of_Stack
        Write OVERFLOW
    else
        REAR=REAR+1
        QUEUE[REAR]=VALUE
    END IF
END of Procedure

2. dequeue() in Queue

On the other hand dequeue() removes or deletes and accesses the first element present in the queue. Note, this element is the one which was inserted before all the other ones hence is the first one to get dequeued. This dequeue operation occurs at the front of the present queue. Hence, the opposite side to the one where enqueue was performed.

The Algorithm for dequeue is given below,

Procedure DEQUEUE()
    If FRONT==-1 OR FRONT>REAR  //If the queue is empty
        Write UNDERFLOW
    else
        FRONT=FRONT+1
        RETURN QUEUE[FRONT-1]
    END IF
END of Procedure

3. Show

The show is basically the operation in which the corresponding elements of the queue is shown to the user or in other words, is printed. This allows the user to check the current status of the queue at any point in time.

The Algorithm for show is given below,

Procedure DEQUEUE()
    If FRONT==-1 OR FRONT>REAR  //If the queue is empty
        Write UNDERFLOW
    else
        Repeat While FRONT<=REAR
            PRINT QUEUE[FRONT]
            FRONT=FRONT+1
    END IF
END of Procedure

Implementation of a Queue in C++

Now let us implement the whole concept of a Queue in C++, this will give us a clear understanding of its working.

#include<iostream>
using namespace std;
#define max 10
int queue[max],front=-1,rear=-1;           //queue declaration
void enqueue(int num) //enqueue() inserts an element into the Queue
{
	if(rear==max)  //check if Queue is full
	{
		cout<<"OVERFLOW!";
	}
	else if(front==-1 && rear==-1) //For 1st insertion in Queue
	{
		front++;
		rear++;
		queue[rear]=num;
	}
	else
	{
		rear++;
		queue[rear]=num;
	}
}
int dequeue() //dequeue() deletes out the 1st element from the Queue
{
	if(front==-1 || front>rear)  //check if Queue is empty
	{
		cout<<"UNDERFLOW!";
		return -1;
	}
	else
	{
		cout<<"The deleted data is : "<<queue[front++];   //printing the deleted element
		return queue[front-1];
	}
}
void show()
{
	int i=front;
	if(front==-1 || front>rear)    //if Queue is empty
	{
		cout<<"UNDERFLOW!";
	}
	else
	{
		while(i<=rear) //printing the current Queue elements
		{
			cout<<"t"<<queue[i];
			i++;
		}
		cout<<endl;
	}
}
int main()
{
    int ch,val;
    cout<<"   :::MENU:::";   //Menu for Queue operations
    cout<<"n1.enqueuen2.dequeuen3.Shown4.Exit";
    while(1)
    {
        printf("nEnter the choice:");
        scanf("%d",&ch);
        switch(ch)
        {
            case 1: cout<<"Enter the value to be pushed: ";
            		cin>>val;
            		enqueue(val);
                    break;
            case 2: dequeue();
                    break;
            case 3: cout<<"Stack : ";
					show();
                    break;
            case 4: exit(0);
            default: printf("nError! Invalid choice!...");
        }
    }
    return 0;
}

Output:

Understanding the code,

• Firstly have initially declared two variables, front=-1 and rear=-1, to signify the queue is empty. The size of the queue is stored inside the constant max
• enqueue() – as the name suggests, we use this function to perform the enqueue operation. It adds the passed value to the queue at the rear position
• dequeue() – similarly is used to remove or access the front element from the queue. This function returns the first value removed from the queue
• show() – This function prints the whole queue, all of its elements. Starting from the front up to the rear.

As we saw in our stack tutorial, the repetitive checking the top was important to avoid errors. Similarly in case of a queue too, we need to check whether the given queue is full or empty and print OVERFLOW and UNDERFLOW errors respectively.

Applications

Queues find application in various programming methods and also are used to solve many real-time problems. Some of them are,

1. CPU sharing
2. Breadth-First Search algorithm
3. Waiting lists
4. IO buffers,
5. File IO
6. Keyboard Buffer
7. And many more…

Conclusion

In this tutorial, we have discussed the concept of a queue in C++ as well as the different operations that we perform on it. We have also taken the various applications of a Queue into consideration.

References