Hi everyone

In this tutorial we will talk about Queue

So, What is Queue actually?

Queue is a First In First Out(FIFO) data structure.

STL Queue also works the same way

STL Queue container’s underlying data structure deque (Double Ended Queue)

Header File Inclusion for queue

#include <queue>

Declaration

#include <queue>

queue <int> fifoList;

Insertion

push() method

With push() method we insert data into a queue. In a queue data is always inserted at the back.

fifoList.push(64);
fifoList.push(32);
fifoList.push(75);
fifoList.push(12);

After Insertion queue will look like this —

emplace() method

We can also insert values to queue with emplace() method —

fifoList.emplace(25);
fifoList.emplace(35);

After Insertion queue will look like this —

Accessing the element

front() method
front() method of queue returns the front element of the queue

// this will output the front element from queue
cout << fifoList.front() << endl;

Output will be – 64

back() method
back() method of queue returns the tail element of the queue

// this will output the back element from queue
cout << fifoList.back() << endl;

Output will be – 35

Deletion

pop() method

Queue’s pop() method removes the front element from queue

// removing element 64, now current front 32
fifoList.pop();

// removing element 32, now current front 75
fifoList.pop();

// removing element 75, now current front 12
fifoList.pop();

After Deletion queue will look like this —

Swapping

swap() method

There is a scenario that, someone need to swap values between two queue and if he is thinking about creating

auxiliary queues. There is a good news for him. We don’t need to create auxiliary queues if we are using STL queue.

STL queue has a method named swap(), which swaps values of two queue data structures —

queue <int> listOne;
listOne.push(128);
listOne.push(64);
listOne.push(32);

After Insertion listOne will look like this —

128

queue <int> listTwo;
listTwo.push(1);
listTwo.push(2);
listTwo.push(4);

After Insertion listTwo will look like this —

Now, let’s swap the elements of two queue —

// swapping values between two queues
listOne.swap(listTwo);

After Swapping listOne will look like this —

After Swapping listTwo will look like this —

128

Time Complexity

Operation	Description	Time Complexity
push()	Inserts a element at the back of the queue	O(1)
emplace()	Inserts a element at the back of the queue	O(1)
front()	Returns the front element of the queue	O(1)
back()	Returns the back or tail element of the queue	O(1)
pop()	Removes the element from the front of the queue	O(1)
size()	Returns the number of elements of the queue	O(1)
empty()	Returns a bool value False if queue is not empty True if queue is empty	O(1)
swap()	Swap the elements of two queues	O(n)

Applications

- - - BFS Algorithm
    - Finding shortest path
    - FCFS (First Come First Serve) scheduling algorithm

In the next tutorial we will talk about another useful STL container.

Until then
Happy Coding