Create a resume that lands you SDE interviews at MAANG

Speaker

Anubhav Sinha

SDE-2 @

12 Jun, 2024 @ 01:30 PM

Introduction

A data structure is a method of managing data in a computer that can be used effectively. For example, we have linked lists, stacks, trees, and queues as some of the data structures that can organize data. Similarly, we can store a list of items having a similar data type using the array data structure.

Queues

A Queue is a linear data structure that follows the FIFO principle i.e., the First-In-First-Out method. The 2 ends of a queue are called Front and Rear. At the start, both Front and Rear are equal to -1 so the queue is empty. Insertion takes place at the Rear end, and the elements are removed or accessed from the Front.

Some applications of queues are :

Scheduling: Job Scheduling, CPU Scheduling.

Buffers: I/O Buffers.

Operations supported by Queues

Some operations performed on a queue are:

enqueue(): Inserting a new element in the queue.

dequeue(): Remove an element from the front of the queue.

showfront(): To show the element at the front.

isempty(): To check if queue is empty.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Inserting elements in a queue

Let us take an example of a queue of size= 5.

To insert (enqueue) the element (suppose here 8) in the Queue, we will have to increment the Rear by one and insert 8 at the Rear.

When inserting we have to take care of two special cases:

When the Queue is empty, the initial value of Front and Rear will be -1, so we will make Front = 0 and increment Rear and insert the element at the Rear.

When the Queue is full, here, we cannot insert any elements in the Queue.

Code for Insertion:

void enqueue(int element) {
// to check if queue is full or not
if (size == rear) {
cout << "Queue is full" << endl;
return;
}
// to insert an element at the rear of the queue
else {
cout << "Element inserted" << endl;
queue[rear] = element;
rear++;
}
return;
}

If the rear is equal to the size-1 then we will print the queue is full; else we will increment the rear index and store the new element at the rear index.

Deleting elements in a queue

If we have to remove the first element from the Queue, we will increment Front by one.

While removing (dequeue) elements from the Queue, we also have two exceptional cases:

The queue is empty - in that case, the Front and Rear will be equal to -1, and as there are no elements in the Queue, we cannot perform the dequeue operation.

The queue has only one element - in that case, the Front will be equal to the Rear, and we will make both equal to -1.

Code for Deletion:

void dequeue() {
// to check if the queue is empty
if (front == rear) {
cout << "Queue is empty" << endl;
return;
} else {
for (int i = 0; i < rear - 1; i++) {
queue[i] = queue[i + 1];
}
cout << "Element deleted" << endl;
// decrement the rear
rear--;
}
return;
}

First, we will check if the queue is empty or not. If the queue is empty then we will print that the queue is empty. Else, we will shift all the elements from the start to end to the left by 1. Here we will ignore the element's value at index 0 because we have to remove the element at index 0.

Displaying the whole queue

void printQueue() {
// to check if queue is empty
if (front == rear) {
cout << "Queue is Empty" << endl;
return;
}
//traversing from front to rear to print the elements
cout << "The queue is: ";
for (int i = front; i < rear - 1; i++) {
cout << queue[i] << " <-- ";
}
cout << queue[rear - 1] << endl;
return;
}

First, we will check if the queue is empty or not. If the queue is empty then we will print that the queue is empty else we will simply print all the elements of the queue.

Displaying only the front element of the queue

void getFront() {
// to check if the queue is empty
if (front == rear) {
cout << "Queue is Empty" << endl;
return;
}
cout << "Front element is: " << queue[front] << endl;
return;
}

We will first check if the queue is empty or not. If the queue is empty then we will print that the queue is empty else we will just print the front element by using the front variable which is keeping the index of the front variable.

Code for implementation of queues using array

#include <bits/stdc++.h>
using namespace std;
struct Queue {
int front, rear, size;
int* queue;
Queue(int c)
{
front = rear = 0;
size = c;
queue = new int;
}
~Queue() { delete[] queue; }
// to insert an element in the queue
void enqueue(int element)
{
if (size == rear) {
cout<<"Queue is full"<<endl;
return;
}
else {
cout<<"Element inserted"<<endl;
queue[rear] = element;
rear++;
}
return;
}
// function to delete an element from the queue
void dequeue()
{
// to check if the queue is empty
if (front == rear) {
cout<<"Queue is empty"<<endl;
return;
}
// shift all the elements from index 1 till the last element to the left by 1
else {
for (int i = 0; i < rear - 1; i++) {
queue[i] = queue[i + 1];
}
cout<<"Element deleted"<<endl;
// decrement the rear
rear--;
}
return;
}
// function to print the elements of the queue
void printQueue()
{
// to check if queue is empty
if (front == rear) {
cout<<"Queue is Empty"<<endl;
return;
}
// traverse front to rear and print elements
cout<<"The queue is: ";
for (int i = front; i < rear-1; i++) {
cout<<queue[i]<<" <-- ";
}
cout<<queue[rear-1]<<endl;
return;
}
// print the front of the queue
void getFront()
{
// to check if the queue is empty
if (front == rear) {
cout<<"The Queue is Empty"<<endl;
return;
}
cout<<"Front element is: "<< queue[front]<<endl;
return;
}
};
// Driver code
int main()
{
// To create a queue of size 5
Queue queue(5);
// print the queue elements
queue.printQueue();
// inserting elements in the queue
queue.enqueue(7);
queue.enqueue(4);
queue.enqueue(9);
queue.enqueue(6);
// printing the queue elements
queue.printQueue();
// inserting the element in the queue
queue.enqueue(1);
// printing the queue elements
queue.printQueue();
// deleting the front element from the queue
queue.dequeue();
// printing the queue elements
queue.printQueue();
// deleting the front element from the queue
queue.dequeue();
// print Queue elements
queue.printQueue();
// print the front element of the queue
queue.getFront();
return 0;
}

Output:

The Queue is Empty
Element inserted
Element inserted
Element inserted
Element inserted
The queue is: 7 <-- 4 <-- 9 <-- 6
Element inserted
The queue is: 7 <-- 4 <-- 9 <-- 6 <-- 1
Element deleted
The queue is: 4 <-- 9 <-- 6 <-- 1
Element deleted
The queue is: 9 <-- 6 <-- 1
Front element is: 9

Dequeue a double-ended queue, or a data structure, where the elements can be deleted or inserted at both ends (FRONT and REAR).

Name some applications of queue Data Structure.

To keep the playlist in media players (to add or remove the songs)

To reverse strings

To verify if delimiters (parenthesis, brackets etc.) are balanced in a computer program

To search the vertices of a graph.

Name some operations that can be performed on queues

enqueue() : Inserting a new element in queue.

dequeue() : Removing an element from the front of the queue.

showfront() : To show the element in the front.

isempty() : To check if queue is empty.

What is the time complexity of push and pop functions of queues?

The time complexity of enqueue is O(1) and the time complexity of Dequeue is O(n).

What are Priority Queues?

A priority queue is a specialized queue in which the items are associated with a "priority" so that the highest key is always on the Front. So when you get an item from a priority queue, you always get the highest value.

Conclusion

This article demonstrated the implementation of queues using arrays in C++. Once you are done with this, you may check out our Interview Preparation Course to level up your programming journey and get placed at your dream company.

We hope that this blog has helped you increase your knowledge regarding queue data structure, and if you liked this blog, check other links. Do upvote our blog to help other ninjas grow. Happy Coding!"