After the first item of the original list has been removed, the second becomes the first item. After the second item has been removed, the third becomes the first item, and so on.
A good real-life example of a queue is when people line up to wait for service or good. The first person is served first before the last. However, the queue talked about in this tutorial, is the software queue, as designed in C++.
FIFO
FIFO stands for First-In, First-Out. It is another way of appreciating the queue. This means, the first item to enter the list, is the first item to be removed, whenever removal is to take place. The beginning of the list is called the head or front; the end of the list is called the back or tail.
Essential Operations
A software queue must have at least the following operations:
push
This operation, adds a new element at the back of the queue. This operation is officially called, enqueue.
shift
This operation removes the first element of the queue, and the second element becomes the new first element. This operation is officially called dequeue. It is called pop in C++.
This article explains how to use the C++ queue data structure. You should know C++ pointers and references to understand the rest of this article.
Class and Objects
A class is a set of variables and functions that work together, where the variables do not have values assigned to. When values are assigned to the variables, the class becomes an object. Different values given to the same class result in different objects; that is, different objects are the same class with different values. Creating an object from a class is said to be instantiating the object.
The name, queue, is a class. An object created from the queue class has a programmer chosen name.
A function that belongs to a class is needed to instantiate an object from the class. In C++, that function has the same name as the name of the class. Objects created (instantiated) from the class have different names given to them, by the programmer.
Creating an object from the class means constructing the object; it also means instantiating.
A C++ program which uses the queue class, starts with the following lines at the top of the file:
#include <squeue>
using namespace std;
The first line is for input/output. The second line is to allow the program to use all the features of the queue class. The third line allows the program to use the names in the standard namespace.
Overloading a Function
When two or more different function signatures have the same name, that name is said to be overloaded. When one function is called, the number and type of arguments, determine which function is actually executed.
Construction
The following declaration instantiates a queue named, que of type int.
The queue is empty. The declaration begins with the reserved word, queue followed by angle brackets with the data type. Then you have the programmer given name for the queue.
Constructing with Initializer List
The following definition shows how to create a queue with initializer list:
Destroying a Queue
To destroy a queue, just let it go out of scope.
Queue Element Access
push(value)
A queue is a First-In-First-Out list. So, each value is added from the back. The following code segment creates an empty queue, after which five float values are added from the back:
que.push(1.1);
que.push(2.2);
que.push(3.3);
que.push(4.4);
que.push(5.5);
size() const
This returns the number of elements in the queue. The following code illustrates:
que.push(1.1); que.push(2.2); que.push(3.3); que.push(4.4); que.push(5.5);
cout << que.size() << '\n';
The output is 5.
front()
This returns a reference to the first element of the queue, without removing the element. The output of the following code is 1.1.
que.push(1.1); que.push(2.2); que.push(3.3); que.push(4.4); que.push(5.5);
cout << que.front() << '\n';
The element is not removed from the queue.
front() const
When the queue construction is preceded by const, the expression “front() const” is executed instead of “front()”. It is used in the following code, for example.
cout << que.front() << '\n';
A constant reference is returned. The element is not removed from the vector. The queue elements cannot be changed.
back()
This returns a reference to the last element of the queue, without removing the element. The output of the following code is 5.5.
que.push(1.1); que.push(2.2); que.push(3.3); que.push(4.4); que.push(5.5);
cout << que.back() << '\n';
back() const
When the queue construction is preceded by const, the expression “back() const” is executed instead of “back()”. It is used in the following code, for example.
cout << que.back() << '\n';
A constant reference is returned. The element is not removed from the queue. With the preceding const for the queue construction, the elements in the queue cannot be changed.
Queue Capacity
size() const
– see above
empty() const
This returns 1 for true if there are no elements in the queue, or 0 for false if the queue is empty. The following code illustrates this:
cout << que1.empty() << '\n';
queue<float> que2;
cout << que2.empty() << '\n';
The output is:
1
Queue Modifiers
pop()
A queue is FIFO, so any element that has to be removed must be removed from the top (head) of the queue. This member function removes the first element without returning it. The following code illustrates this:
cout << que.front() << '\n';
que.pop();
cout << que.size() << '\n';
The output is:
4
a.swap(b)
Two queues can be swapped, as illustrated in this code segment:
queue <float> que2({10, 20});
que1.swap(que2);
cout << "First element and size of que1:"
<< que1.front() <<", "<< que1.size() << '\n';
cout << "First element and size of que2 "<<
que2.front() <<", "<< que2.size() << '\n';
The output is:
First element and size of que1: 10, 2
First element and size of que2: 1.1, 5
Note that the length of a queue is increased if necessary. Also, values that did not have replacements, are replaced by some default value. The data types must be of the same type.
Equality and Relational Operators for Queues
For ordinary characters in C++, in ascending order, numbers come before uppercase letters, which come before lowercase letters. The space character comes before zero and all of them.
Equality Operators
Returns 1 for true and 0 for false.
The == Operator
Returns 1 if the two queues have the same size and the corresponding elements are equal; otherwise it returns 0. Example:
queue <const char*> que2({"wicked"});
int num = que1 == que2;
cout << num << '\n';
The output is: 0.
The != Operator
– opposite of the above. Example:
queue <const char*> que2({"wicked"});
int num = que1 != que2;
cout << num << '\n';
The output is: 1.
Relational Operators
Returns 1 for true and 0 for false.
The < Operator
Returns 1 if the first queue is the initial subset of the second queue, with the elements of the two equal portions being the same and in the same order. If both queues are of the same size or different sizes, and moving from left to right, an element is encountered in the first queue that is less than the corresponding element in the second queue, then 1 will still be returned. Otherwise 0 is returned. Example:
queue <const char*> que2({"wicked"});
int num = que1 < que2;
cout << num << '\n';
The output is 1. < does not include the case when the size and order are the same.
The > Operator
– opposite of the above. Example:
queue <const char*> que2({"wicked"});
int num = que1 > que2;
cout << num << '\n';
Output: 0
The <= Operator
– same as < but includes the case when the size and order are the same. Example:
queue <const char*> que2({"wicked"});
int num = que1 <= que2;
cout << num << '\n';
Output: 1
The >= Operator
– opposite of the above. Example:
queue <const char*> que2({"wicked"});
int num = que1 >= que2;
cout << num << '\n';
Output: 0
Class and its Instantiated Objects
A value is to a data type, as an instantiated object is to a class. The queue construction can also accept a class as a data type. The following program illustrates this:
#include <queue>
using namespace std;
class TheCla
{
public:
int num;
static char ch;
void func (char cha, const char *str) {
cout << "There are " << num << " books worth " <<
cha << str << " in the store." << '\n';
}
static void fun (char ch) {
if (ch == 'a')
cout << "Official static member function" << '\n';
}
};
int main() {
TheCla obj1; TheCla obj2; TheCla obj3; TheCla obj4; TheCla obj5;
queue <TheCla> que;
que.push(obj1);
que.push(obj2);
que.push(obj3);
que.push(obj4);
que.push(obj5);
cout << que.size() << '\n';
return 0;
}
The output is 5.
Linked List
The queue list is technically called a linked list. There are two types of linked lists for the queue: singly linked list and doubly linked list.
A singly linked list element can be implemented by a struct of two members. One member holds a pointer to the next element and the other member holds the datum (singular for data).
A doubly linked list element can be implemented by a struct of three members. The middle member holds the datum, while the first and third members hold pointers to their adjacent elements.
Applications of the Queue
The queue is a first-in-first-out data structure. There are situations in computing when data arrives in the form of a queue, necessitating first-in-first-out behavior.
Sharing Computer Resources
A resource in a computer is any physical or virtual component of limited availability. They include the CPU, video card, hard drive, and memory. Sharing such a resource needs a queue.
Handling Interrupts
Computer peripherals need to interrupt the computer from time to time. The interrupts have to be handled in the same way that they arrived. This needs a queue.
Manage information.
The queue can be used, for example, to manage application files for a job, if the files are stored in the computer.
Conclusion
A queue is a list data structure, which is either a singly linked list or a doubly-linked list. As a rule, the first element that enters the list is the first element to come out. C++ provides a queue data structure in its standard library. The categories of member functions and operators available for this structure are queue construction, queue element access, queue capacity, queue modifiers, and queue overloaded operators.
Any queue data structure must provide at least, the push() and pop() member functions. push() means, sending a new element at the back of the queue; and pop() means, removing the element that is at the front of the queue. Unfortunately, in C++, these functions do not return the value pushed or popped. So, to know the last element before pushing, the extra back() function has to be used; and to know the first element before popping, the extra front() function has to be used.
A value is to a data type, as an instantiated object is to a class. So, a particular class can be used as a data type for the queue template instantiation. Different objects for the class become like different values for the class.
The queue has applications on the computer. It can be used, for example, to manage application files for a job, if the files are stored in the computer.
