Last Updated on July 20, 2022 by Ria Pathak
Queue:
A queue is basically a linear data structure that works on the principle of FIFO (First in First out) which means an element that is enqueued first will be dequeued first. Element is enqueued from the rear end of the queue and dequeued from the front end. The insertion operation in the queue is known as enqueue and the deletion operation in the queue is known as dequeue.
The queue is used when the operations are to be performed in the manner of First in First out order just like Breadth-First Search.
For Example A ticket Queue outside a cinema hall where the person enters the queue first will get the ticket first.
Basic Operations of Queue:
-
Enqueue: This operation is used to Insert an element at the rear end of the queue.
-
Dequeue: This operation is used to remove and return an element from the front end of the queue.
-
isEmpty(): This operation is used to check whether the queue is empty or not. It returns bool value, if the queue is empty then this operation will return true else false.
-
isFull(): This operation is used to check whether the queue is full or not. It return true is the queue is full, else it will return false.
-
Peek(): This operation is used to get the value of the element from the front of the queue.
Working of queue:
- We can implement queue by using two pointers i.e. FRONT and REAR.
- FRONT is used to track the first element of the queue.
- REAR is used to track the last element of the queue.
- Initially, we’ll set the values of FRONT and REAR to -1.
Enqueue Operation / Insertion:
- First check if the queue is full or not.
- For the first element, set the FRONT pointer to 0.
- Increment the REAR index by 1.
- Add the new element in the position which was pointed by REAR.
void enQueue(int value) {
if (rear == SIZE - 1)
printf("\nQueue is Full!!");
else {
if (front == -1)
front = 0;
rear++;
items[rear] = value;
printf("\nInserted -> %d", value);
}
}
void enQueue(int element) {
if (isFull()) {
cout << "Queue is full";
} else {
if (front == -1) front = 0;
rear++;
items[rear] = element;
cout << endl
<< "Inserted " << element << endl;
}
}
void enQueue(int element) {
if (isFull()) {
System.out.println("Queue is full");
} else {
if (front == -1)
front = 0;
rear++;
items[rear] = element;
System.out.println("Inserted " + element);
}
}
def EnQueue(self, element):
if self.isFull():
print("Queue is Full")
return
if self.front == -1:
self.front = 0
self.rear += 1
self.items[self.rear] = element
print("Inserted", element)
Dequeue Operation / Remove:
- First check if the queue is empty or not.
- Return the value which was pointed by FRONT.
- Increment the FRONT index by 1.
- For the last element, reset the values of FRONT and REAR to -1.
void deQueue() {
if (front == -1)
printf("\nQueue is Empty!!");
else {
printf("\nDeleted : %d", items[front]);
front++;
if (front > rear)
front = rear = -1;
}
}
int deQueue() {
int element;
if (isEmpty()) {
cout << "Queue is empty" << endl;
return (-1);
} else {
element = items[front];
if (front >= rear) {
front = -1;
rear = -1;
}
else {
front++;
}
cout << endl
<< "Deleted -> " << element << endl;
return (element);
}
}
int deQueue() {
int element;
if (isEmpty()) {
System.out.println("Queue is empty");
return (-1);
} else {
element = items[front];
if (front >= rear) {
front = -1;
rear = -1;
} else {
front++;
}
System.out.println("Deleted -> " + element);
return (element);
}
}
def DeQueue(self):
if self.isEmpty():
print("Queue is Empty")
return -1
else:
element = self.items[self.front]
if self.front >= self.rear:
self.front = -1
self.rear = -1
else:
self.front += 1
print("Deleted ->", element)
return element
Queue Implementation:
#include <stdio.h>
#define SIZE 5
void enQueue(int);
void deQueue();
void display();
int items[SIZE], front = -1, rear = -1;
int main() {
deQueue();
//enQueue 5 elements
EnQueue(1);
EnQueue(2);
EnQueue(3);
EnQueue(4);
EnQueue(5);
// 6th element can't be added to because the queue is full
EnQueue(6);
display();
//deQueue removes element entered first i.e. 1
deQueue();
//Now we have just 4 elements
display();
return 0;
}
void EnQueue(int value) {
if (rear == SIZE - 1)
printf("\nQueue is Full!!");
else {
if (front == -1)
front = 0;
rear++;
items[rear] = value;
printf("\nInserted -> %d", value);
}
}
void deQueue() {
if (front == -1)
printf("\nQueue is Empty!!");
else {
printf("\nDeleted : %d", items[front]);
front++;
if (front > rear)
front = rear = -1;
}
}
// Function to print the queue
void display() {
if (rear == -1)
printf("\nQueue is Empty!!!");
else {
int i;
printf("\nQueue elements are:\n");
for (i = front; i <= rear; i++)
printf("%d ", items[i]);
}
printf("\n");
}
#include <iostream>
#define SIZE 5
using namespace std;
class Queue {
private:
int items[SIZE], front, rear;
public:
Queue() {
front = -1;
rear = -1;
}
bool isFull() {
if (front == 0 && rear == SIZE - 1) {
return true;
}
return false;
}
bool isEmpty() {
if (front == -1)
return true;
else
return false;
}
void EnQueue(int element) {
if (isFull()) {
cout << "Queue is full";
} else {
if (front == -1) front = 0;
rear++;
items[rear] = element;
cout << endl
<< "Inserted " << element << endl;
}
}
int deQueue() {
int element;
if (isEmpty()) {
cout << "Queue is empty" << endl;
return (-1);
} else {
element = items[front];
if (front >= rear) {
front = -1;
rear = -1;
} /* Q has only one element, so we reset the queue after deleting it. */
else {
front++;
}
cout << endl
<< "Deleted -> " << element << endl;
return (element);
}
}
void display() {
/* Function to display elements of Queue */
int i;
if (isEmpty()) {
cout << endl
<< "Empty Queue" << endl;
} else {
cout << endl
<< "Front index-> " << front;
cout << endl
<< "Items -> ";
for (i = front; i <= rear; i++)
cout << items[i] << " ";
cout << endl
<< "Rear index-> " << rear << endl;
}
}
};
int main() {
Queue q;
//deQueue is not possible on empty queue
q.deQueue();
//enQueue 5 elements
q.EnQueue(1);
q.EnQueue(2);
q.EnQueue(3);
q.EnQueue(4);
q.EnQueue(5);
// 6th element can't be added to because the queue is full
q.EnQueue(6);
q.display();
//deQueue removes element entered first i.e. 1
q.deQueue();
//Now we have just 4 elements
q.display();
return 0;
}
import java.util.*;
public class Queue {
int SIZE = 5;
int items[] = new int[SIZE];
int front, rear;
Queue() {
front = -1;
rear = -1;
}
boolean isFull() {
if (front == 0 && rear == SIZE - 1) {
return true;
}
return false;
}
boolean isEmpty() {
if (front == -1)
return true;
else
return false;
}
void enQueue(int element) {
if (isFull()) {
System.out.println("Queue is full");
} else {
if (front == -1)
front = 0;
rear++;
items[rear] = element;
System.out.println("Inserted " + element);
}
}
int deQueue() {
int element;
if (isEmpty()) {
System.out.println("Queue is empty");
return (-1);
} else {
element = items[front];
if (front >= rear) {
front = -1;
rear = -1;
}
else {
front++;
}
System.out.println("Deleted -> " + element);
return (element);
}
}
void display() {
int i;
if (isEmpty()) {
System.out.println("Empty Queue");
} else {
System.out.println("\nFront index-> " + front);
System.out.println("Items -> ");
for (i = front; i <= rear; i++)
System.out.print(items[i] + " ");
System.out.println("\nRear index-> " + rear);
}
}
public static void main(String[] args) {
Queue q = new Queue();
q.deQueue();
// enQueue 5 elements
q.enQueue(1);
q.enQueue(2);
q.enQueue(3);
q.enQueue(4);
q.enQueue(5);
q.enQueue(6);
q.display();
q.deQueue();
q.display();
}
}
class Queue:
def __init__(self,size):
self.size = size
self.items = [0] * size
self.front = -1
self.rear = -1
def isFull(self):
if self.front == 0 and self.rear == self.size - 1:
return True
return False
def isEmpty(self):
if self.front == -1:
return True
return False
def EnQueue(self, element):
if self.isFull():
print("Queue is Full")
return
if self.front == -1:
self.front = 0
self.rear += 1
self.items[self.rear] = element
print("Inserted", element)
def DeQueue(self):
if self.isEmpty():
print("Queue is Empty")
return -1
else:
element = self.items[self.front]
if self.front >= self.rear:
self.front = -1
self.rear = -1
else:
self.front += 1
print("Deleted ->", element)
return element
def display(self):
if self.isEmpty():
print("Empty Queue")
else:
print("Front Index-> ", self.front)
print("Items-> ", end = "")
for i in range(self.front, self.rear + 1):
print(self.items[i], end = " ")
print("\nRear index-> ", self.rear)
q = Queue(5)
q.DeQueue()
q.EnQueue(1)
q.EnQueue(2)
q.EnQueue(3)
q.EnQueue(4)
q.EnQueue(5)
q.EnQueue(6)
q.display()
q.DeQueue()
q.display()
This article tried to discuss Queue Data Structure. Hope this blog helps you understand the concept. To practice problems feel free to check MYCODE | Competitive Programming.