In the previous article, we covered Stacks. In this article, we will look at a similar data structure called Queues. So what is a queue? Let's have a look.

What is a Queue?

As the name sugggests, Queue is a data structure where data is saved like a queue, one after each other. A visual representation would be helpful i guess..

In the above image, you can see a horizontal container and some operations being done on it. We will talk about the operations in detail ahead. The horizontal container is a stack. Queue is a very useful data structure.

• A queue is a First In First Out (FIFO) structure, that is, first item you put in is the first item you can take out.
• A real-life example of a queue data structure is a line of people waiting to buy a ticket at a cinema hall
• Managing requests on a single shared resource such as CPU scheduling and disk scheduling
• Handling hardware or real-time systems interrupts
• Maintaining the playlist in media players

Syntax and In-Built Functions

• Just like Stacks, there are two ways to create a queue. One is to build a queue manually with an array and 2 pointers and the other is by using an in-built queue (which most programming languages have). We will talk about the second way here. If you are interested in knowing how stacks are built internally, feel free to go and read this article.
• We will use the in-built queue data type to learn about queue. Below is the syntax to create a queue.

queue<int> que;  // queue <data_type> <name of the queue>

• Easy right. The stack has 3 major operations. Push, Pop, and Front
• Push: This operation is used to push a new element in the end of the queue.
• Pop: This operation is used to remove the first element of the queue.
• Front: This function is used to peek at the first element of the queue.

que.push(3); // queue is [3]
que.push(7); // queue is [3,7]
que.push(1); // queue is [3,7,1]
que.pop(); // queue is [7,1]
int curr = que.front(); // returns 7

Time Complexities

There are other in-built functions like empty() and size()which are useful while using a queue. The time complexities of all the functions of a queue are as follows.

Push: O(1) Pop: O(1) Peek: O(1) Size: O(N) Empty: O(N)

Some other types of Queues

Hmm.. Looks like we have a variety of queues. There are 2 more important type of queues. They are 1) Circular Queues and 2) Doubly-Ended Queue.

In a circular queue, the last node is connected to the first node. It is also known as a Ring Buffer as all the ends are connected to another end. Insertion takes place at the front of the queue and deletion at the end of the queue.

The time complexities of a circular queue is same as a normal queue.

Doubly-Ended Queues are same as normal queues. The only difference is that in a doubly ended queue you can pop elements from both end of the queue. So, we have two functions called as pop_back() & pop_front() instead of a normal pop().

Code Example

Here is a complete code snippet of all the functions discussed above.

#include<bits/stdc++.h>

using namespace std;

int main()
{
   queue<int>que;
   que.push(3);
   que.push(7);
   que.push(1);
   que.pop();
   int y = que.top();
   bool x = que.empty();
   int sz = que.size();
}

Conclusion

This concludes our article on Queues. Now you have a good understanding of the basics of a queue, different types of queues, and its time complexities. You can now go on your IDE and play around with them.