Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
In this article at OpenGenus, we will explore the fundamentals of the Queue data structure with a user-defined objects and how C++ provides a powerful Standard Template Library (STL) which has a container for queue which you can use in your code. Let's begin with a simple question.
What is the queue data structure?
Imagine your grandmother is distributing icecream to you and all of your cousins. She has instructed you all to stand in a line. There are others in front of you and you have to wait for your turn to get the icecream. This line is very similar to a Queue.
A Queue is a data structure which follows FIFO, i.e., the First-In-First-Out principle just like waiting in the line. It basically means that the person who stands first in the line (numbered 1 in image) will get the icecream first and the person who stands last (numbered 5 in image) will get it last. Or, in other words, the first person who arrives in the queue is the first one to get out.
In a queue, you can add elements to the back and remove elements from the front. They are useful when maintaining a specific order is important. Now the next question.
How to use the queue container of the Standard Template Library in C++?
To use the queue container, you must include it's header file at the very beginning of your C++ program. A header file is like a cheat sheet that contains important information about functions, classes etc that can be used in a program. You can access and use pre written code in your programs without writing everything from scratch. Here is how to implement it.
#include<queue>
After including the queue header file, now you can proceed with using Queues for User-Defined objects. But first,
What are User-Defined Objects and how to create them?
User-defined objects are instances of custom data types (class, struct in C++) . To create a user-defined object, you need to define a custom data type with its properties and behaviors and then create an object of that custom data type.
For example, let's say you want to create a user-defined object to represent a car. You can define a custom data type called "Car" with properties like model_name, price and year. Here's an example in C++:
class Car {
public:
string model_name;
int price;
int year;
};
To create a user-defined object based on this data type, you can do the following:
Car myCar; // Creating an object of new custom data type 'Car'
In this case, myCar is an instance of the Car Class. You can then assign values to its properties:
myCar.model_name = "Volkswagen Polo";
myCar.price = "2500000";
myCar.year = 2023;
In this way, myCar represents a specific car with the model_name "Volkswagen Polo", price "2500000" and year "2023".
Now lets move on to the most important part.
How to perform basic Queue operations for user-defined objects?
1. Initializing a Queue
Let's make a queue called myQueue which can contain objects of MyClass data type. We will use myQueue as an example in the coming sections.
#include<queue>
class MyClass{
public:
//define methods and members
};
int main(){
queue<MyClass> myQueue; //myQueue is a queue for objects of MyClass data type.
// .........
}
2. 'queue::push'
This function pushes a new element to the back of the queue. Size of queue increases by one.
MyClass obj1; //creating an object of data type MyClass
myQueue.push(obj1); // inserts obj1 at the back of the queue
3. 'queue::pop'
This function removes the first element from the queue. Size of the queue decreases by one.
myQueue.pop(); // removes first element from the queue
4. 'queue::size'
This function returns the number of elements present in the queue currently.
int queueSize = myQueue.size();
5. 'queue::front'
This function returns the reference of the first element present in the queue which you can access and modify accordingly.
MyClass& firstobj = myQueue.front();
6. 'queue::back'
This function returns the reference of the last element present in the queue which you can access and modify accordingly.
MyClass& lastobj = myQueue.back();
7. 'queue::empty'
This function returns true if there are no elements present in the queue currently and false if there is atleast one element present in the queue. It can be used before performing certain operations on the queue like pop, front, back etc.
bool isEmpty = myQueue.empty(); // true if empty, false if not empty
8. 'queue::emplace'
This function constructs a new object and inserts it in the queue in place using a constructor defined in the custom data type (here, MyClass).
myQueue.emplace(arg1,arg2,arg3,arg4....);
9. 'queue::swap'
This function swaps the contents of two queues of the same type and size thereby exchanging their elements completely.
queue<MyClass> secondQueue;
myQueue.swap(secondQueue); // swaps the content of both queues
10. 'swap'
This function also swaps contents of 2 queues of same type and size. It is different than 'queue::swap' as 'queue::swap' is a function specific to the queue container whereas 'swap' is a general function to swap contents of two entities of the same type.
queue<MyClass> queue1;
queue<MyClass> queue2;
swap(queue1,queue2);
11. Relational operations (Queue)
In C++ STL, relational operators like >,<,==,!=,>= and <= are also supported for queue containers. Elements are compared in the same order in which they are present in the queue. You can use these operators to perform logical operations on the queue contents. However, the operators must be defined for your user-defined object type for this to work.
queue<MyClass> queue1;
queue<MyClass> queue2;
// ...
if (queue1 == queue2) {
//...
}
else if (queue1 < queue2) {
//...
}
else if (queue1 >= queue2) {
...
}
// ....
12. 'uses_allocator'
This functions returns true if queue uses a particular allocator type and false otherwise. An allocator manages memory allocation and deallocation for objects. It's task is to reserve appropriate amount of memory for objects and then later release it when it is no longer needed.
We know myQueue contains objects of MyClass data type. We can use 'uses_allocator' to check if myQueue uses a custom allocator called say, 'myAllocator<MyClass>'
bool usesAllocator = myQueue.uses_allocator<myAllocator<MyClass>>();
To conclude this article at OpenGenus, Standard Template Library of C++ provides a very efficient and easy way to use queues for user-defined objects. With the help of all these functions and relational operators, manipulating queues becomes very convenient while coding your C++ projects.
