How to use C++ Queue

Introduction

A queue is a collection of items, where the first item added into the list, must be the first item to be removed next. So as items are added to the collection, it is growing in size, i.e. it is growing in length. Whenever any item is to be removed, it must be the first one added. If items are removed continuously, then the next one removed, is the second item; the third is removed afterward, and so on.

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
#include
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

queue name()

The following declaration instantiates a queue named, que of type int.

queue que;

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:

queue que(1.1, 2.2, 3.3, 4.4);

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:

queue que;
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:

queue que;
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.

queue que;
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.

const queue que (1.1, 2.2, 3.3, 4.4, 5.5);
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.

queue que;
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.

const queue que (1.1, 2.2, 3.3, 4.4, 5.5);
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:

queue que1 (1.1, 2.2, 3.3, 4.4, 5.5);
cout << que1.empty() << '\n';
queue que2;
cout << que2.empty() << '\n';

The output is:

0
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:

queue que (1.1, 2.2, 3.3, 4.4, 5.5);
cout << que.front() << '\n';
que.pop();
cout << que.size() << '\n';

The output is:

1.1
4

a.swap(b)

Two queues can be swapped, as illustrated in this code segment:

queue que1(1.1, 2.2, 3.3, 4.4, 5.5);
queue 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 que1("kind", "something else");
queue que2("wicked");
int num = que1 == que2;
cout << num << '\n';

The output is: 0.

The != Operator

- opposite of the above. Example:

queue que1("kind", "something else");
queue 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 que1("kind", "something else");
queue 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 que1("kind", "something else");
queue 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 que1("kind", "something else");
queue que2("wicked");
int num = que1 <= que2;
cout << num << '\n';

Output: 1

The >= Operator

- opposite of the above. Example:

queue que1("kind", "something else");
queue 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
#include
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 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.

Chrys