# Types Of Queue

In this tutorial, we are going to learn Types of Queue Data Structure and how to implement them in C, C++, Java, Python .

### 1) Simple Queue

In a simple queue, insertion of element takes place at the rear of queue and removal of element occurs at the front of queue. Simple queue purely follows FIFO approach.

### 2) Circular Queue

Circular Queue is a Linear Data Structure in which operation performed in FIFO(First In First Out) manner.

The last element points to the first element in the circular queue which makes a circular ring.

Advantage of Circular Queue is good memory utilisation, it avoids wastage of memory. For ex. if last position in the circular queue is full and first position is empty then new element/item can be inserted at the first position.

#### Working Of Circular Queue

• Initially `FRONT` and `REAR` are set to `-1`.
• For enqueue operation first of all check the queue is full or not. If `FRONT` is -1 then set `FRONT` to 0 else add the element according to enqueue operation. (Check Circular Queue Operations point for more information)
• For dequeue, check queue is empty or not, if not empty then add element to the queue according to the dequeue operation.
• To display elements in the queue, if queue is not empty then display the elements of queue according to display operation.

#### Operations of Circular Queue

First of all we require two pointers, `FRONT` and `REAR`. `FRONT` points to the first element of the queue and `REAR` points to last element of the queue.

Initially `FRONT` and `REAR` are set to `-1`.

• `Enqueue:`
• If queue is full then its overflow condition. (if (`front == rear + 1`) or `(front == 0 and rear == SIZE - 1)`)
• for first element, set  `FRONT` to 0. i.e. FRONT=0.
• circularly increment the `REAR`  by 1 (i.e. if rear reaches the end of the queue, next it would be at the start of the queue).
• add the new element to the position pointed by the `REAR`.
• `Dequeue:`
• If queue is empty then its underflow condition. (if `(front == -1`).
• Get the value at `FRONT`.
• Increment size of `FRONT` by 1 .
• For the last element(If only one element remains in the queue), set the values of `FRONT` & REAR to `-1`.
• `Display:`
• If queue is empty then print/return queue is empty.
• Print the elements at the position from `FRONT` to REAR, incrementing size of `FRONT` by (`FRONT` + 1) % `QUEUE_SIZE`.
• i.e.` for (i = front; i != rear; i = (i + 1) % SIZE) `

Time complexity of enqueue and dequeue operations in circular queue using an array is `O(1)`.

#### Applications of Circular Queue

• Memory management
• CPU scheduling
• Traffic Management

#### Circular Queue Implementations using array

```#include <stdio.h>

#define SIZE 5

int items[SIZE];
int front = -1, rear = -1;

// Check the queue is full or not
int isFull() {
if ((front == rear + 1) || (front == 0 && rear == SIZE - 1)) return 1;
return 0;
}

// Check the queue is empty or not
int isEmpty() {
if (front == -1) return 1;
return 0;
}

// Adding an element to the queue
void enQueue(int element) {
if (isFull())
printf("\n Overflow\n");
else {
if (front == -1) front = 0;
rear = (rear + 1) % SIZE;
items[rear] = element;
printf("\n Inserted -> %d", element);
}
}

// Removing an element from queue
int deQueue() {
int element;
if (isEmpty()) {
printf("\n Underflow\n");
return (-1);
} else {
element = items[front];
if (front == rear) {
front = -1;
rear = -1;
}
// Queue has only one element, so we reset the  queue after deleting it.
else {
front = (front + 1) % SIZE;
}
printf("\n Deleted element -> %d \n", element);
return (element);
}
}

// Display the queue
void display() {
int i;
if (isEmpty())
printf(" \n Queue is Empty\n");
else {
printf("\n Front -> %d ", front);
printf("\n Items -> ");
for (i = front; i != rear; i = (i + 1) % SIZE) {
printf("%d ", items[i]);
}
printf("%d ", items[i]);
printf("\n Rear -> %d \n", rear);
}
}

int main() {
// prints underflow because queue is empty
deQueue();

enQueue(1);
enQueue(2);
enQueue(3);
enQueue(4);
deQueue();
display();

return 0;
}```
```#include <iostream>
#define SIZE 5 /* Size of Circular Queue */

using namespace std;

class Queue {
private:
int items[SIZE], front, rear;

public:
Queue() {
front = -1;
rear = -1;
}
// Check the queue is full or not
bool isFull() {
if (front == 0 && rear == SIZE - 1) {
return true;
}
if (front == rear + 1) {
return true;
}
return false;
}
// Check  the queue is empty or not
bool isEmpty() {
if (front == -1)
return true;
else
return false;
}
void enQueue(int element) {
if (isFull()) {
cout << "Overflow";
} else {
if (front == -1) front = 0;
rear = (rear + 1) % SIZE;
items[rear] = element;
cout << endl
<< "Inserted " << element << endl;
}
}
// Removing an element
int deQueue() {
int element;
if (isEmpty()) {
cout << "Underflow" << 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 = (front + 1) % SIZE;
}
return (element);
}
}

void display() {
int i;
if (isEmpty()) {
cout << endl
<< "Empty Queue" << endl;
} else {
cout << "Front -> " << front;
cout << endl
<< "Items -> ";
for (i = front; i != rear; i = (i + 1) % SIZE)
cout << items[i];
cout << items[i];
cout << endl
<< "Rear -> " << rear;
}
}
};

int main() {
Queue q;

q.enQueue(1);
q.enQueue(2);
q.enQueue(3);
q.enQueue(4);
q.enQueue(5);

q.display();

return 0;
}```
```class MyCircularQueue():

def __init__(self, k):
self.k = k
self.queue = [None] * k

# Insert an element into the circular queue
def enqueue(self, data):

if ((self.tail + 1) % self.k == self.head):
print("Overflow\n")

self.tail = 0
self.queue[self.tail] = data
else:
self.tail = (self.tail + 1) % self.k
self.queue[self.tail] = data

# Delete an element from the circular queue
def dequeue(self):
print("Underflow\n")

self.tail = -1
return temp
else:
return temp

def printCQueue(self):
print("Queue is empty")

for i in range(self.head, self.tail + 1):
print(self.queue[i], end=" ")
print()
else:
print(self.queue[i], end=" ")
for i in range(0, self.tail + 1):
print(self.queue[i], end=" ")
print()

obj = MyCircularQueue(5)
obj.enqueue(1)
obj.enqueue(2)
obj.enqueue(3)
obj.enqueue(4)

obj.printCQueue()

```

### 3) Deque

Deque (Double Ended Queue) is a type of Queue Data Structure in which insertion and deletion of elements are performed from FRONT or `REAR`.

#### Types of Deque

• Input Restricted Deque
Input is restricted at single end but allows deletion of elements at both the ends.
• Output Restricted Deque
Output is restricted at a single end but allows insertion of elements at both the ends.

#### Operations on a Deque

• `insertFront():` (Insert At Front) Adds an element at the front of Deque.
• `insertLast():` (Insert At Rear) Adds an element at the rear of Deque.
• `deleteFront():` (Delete from Front)Deletes an element from front of Deque.
• `deleteLast():` (Delete from Rear) Deletes an element from rear of Deque.
• `getFront(): `Gets the front element from deque.
• `getRear(): `Gets the last element from deque.
• `isEmpty():` Checks whether Deque is empty or not. If deque is empty then return/print underflow condition.
• `isFull():` Checks whether Deque is full or not. If deque is full then return/print overflow condition.

Time complexity of insertFront(), insertLast(), deleteFront(), deleteLast() is O(1).

#### Applications of Deque:

• Deque supports both stack and queue so it can be used as both.
• Deque is used to store computer code application’s list of undo operations.
• Deque is used to store history of internet browsers.

#### Deque Implementations using array

```class Deque:
def __init__(self):
self.items = []

def isEmpty(self):
return self.items == []

self.items.append(item)

self.items.insert(0, item)

def removeFront(self):
return self.items.pop()

def removeRear(self):
return self.items.pop(0)

def size(self):
return len(self.items)

d = Deque()
print(d.isEmpty())
print(d.size())
print(d.removeFront())
print(d.removeRear())
print(d.items)```

```#include <stdio.h>

#define MAX 10

void addFront(int *, int, int *, int *);
void addRear(int *, int, int *, int *);
int delFront(int *, int *, int *);
int delRear(int *, int *, int *);
void display(int *);
int count(int *);

int main() {
int arr[MAX];
int front, rear, i, n;

front = rear = -1;
for (i = 0; i < MAX; i++)
arr[i] = 0;

printf("\nElements in the deque: ");
display(arr);

i = delFront(arr, &front, &rear);
printf("\nremoved element: %d", i);

printf("\nElements in the deque after deletion: ");
display(arr);

printf("\nElements in the deque after addition: ");
display(arr);

i = delRear(arr, &front, &rear);
printf("\nremoved element: %d", i);

printf("\nElements in the deque after deletion: ");
display(arr);

n = count(arr);
printf("\nTotal number of elements in the deque: %d", n);
}

void addFront(int *arr, int item, int *pfront, int *prear) {
int i, k, c;

if (*pfront == 0 && *prear == MAX - 1) {
printf("\nOverflow.\n");
return;
}

if (*pfront == -1) {
*pfront = *prear = 0;
arr[*pfront] = item;
return;
}

if (*prear != MAX - 1) {
c = count(arr);
k = *prear + 1;
for (i = 1; i <= c; i++) {
arr[k] = arr[k - 1];
k--;
}
arr[k] = item;
*pfront = k;
(*prear)++;
} else {
(*pfront)--;
arr[*pfront] = item;
}
}

void addRear(int *arr, int item, int *pfront, int *prear) {
int i, k;

if (*pfront == 0 && *prear == MAX - 1) {
printf("\nOverflow\n");
return;
}

if (*pfront == -1) {
*prear = *pfront = 0;
arr[*prear] = item;
return;
}

if (*prear == MAX - 1) {
k = *pfront - 1;
for (i = *pfront - 1; i < *prear; i++) {
k = i;
if (k == MAX - 1)
arr[k] = 0;
else
arr[k] = arr[i + 1];
}
(*prear)--;
(*pfront)--;
}
(*prear)++;
arr[*prear] = item;
}

int delFront(int *arr, int *pfront, int *prear) {
int item;

if (*pfront == -1) {
printf("\nUndeflow");
return 0;
}

item = arr[*pfront];
arr[*pfront] = 0;

if (*pfront == *prear)
*pfront = *prear = -1;
else
(*pfront)++;

return item;
}

int delRear(int *arr, int *pfront, int *prear) {
int item;

if (*pfront == -1) {
printf("\nUnderflow.\n");
return 0;
}

item = arr[*prear];
arr[*prear] = 0;
(*prear)--;
if (*prear == -1)
*pfront = -1;
return item;
}

void display(int *arr) {
int i;

printf("\n front:  ");
for (i = 0; i < MAX; i++)
printf("  %d", arr[i]);
printf("  :rear");
}

int count(int *arr) {
int c = 0, i;

for (i = 0; i < MAX; i++) {
if (arr[i] != 0)
c++;
}
return c;
}```

```#include <iostream>
using namespace std;

#define MAX 10

class Deque {
int arr[MAX];
int front;
int rear;
int size;

public:
Deque(int size) {
front = -1;
rear = 0;
this->size = size;
}

void insertfront(int key);
void insertrear(int key);
void deletefront();
void deleterear();
bool isFull();
bool isEmpty();
int getFront();
int getRear();
};

bool Deque::isFull() {
return ((front == 0 && rear == size - 1) ||
front == rear + 1);
}

bool Deque::isEmpty() {
return (front == -1);
}

void Deque::insertfront(int key) {
if (isFull()) {
cout << "Overflow\n"
<< endl;
return;
}

if (front == -1) {
front = 0;
rear = 0;
}

else if (front == 0)
front = size - 1;

else
front = front - 1;

arr[front] = key;
}

void Deque ::insertrear(int key) {
if (isFull()) {
cout << " Overflow\n " << endl;
return;
}

if (front == -1) {
front = 0;
rear = 0;
}

else if (rear == size - 1)
rear = 0;

else
rear = rear + 1;

arr[rear] = key;
}

void Deque ::deletefront() {
if (isEmpty()) {
cout << "Underflow\n"
<< endl;
return;
}

if (front == rear) {
front = -1;
rear = -1;
} else if (front == size - 1)
front = 0;

else
front = front + 1;
}

void Deque::deleterear() {
if (isEmpty()) {
cout << " Underflow\n"
<< endl;
return;
}

if (front == rear) {
front = -1;
rear = -1;
} else if (rear == 0)
rear = size - 1;
else
rear = rear - 1;
}

int Deque::getFront() {
if (isEmpty()) {
cout << " Underflow\n"
<< endl;
return -1;
}
return arr[front];
}

int Deque::getRear() {
if (isEmpty() || rear < 0) {
cout << " Underflow\n"
<< endl;
return -1;
}
return arr[rear];
}

int main() {
Deque dq(4);

cout << "insert element at rear \n";
dq.insertrear(5);
dq.insertrear(11);

cout << "rear element: "
<< dq.getRear() << endl;

dq.deleterear();
cout << "after deletion of the rear element, the new rear element is : " << dq.getRear() << endl;

cout << "insert element at front  \n";

dq.insertfront(8);

cout << "front element: " << dq.getFront() << endl;

dq.deletefront();

cout << "after deletion of front element new front element: " << dq.getFront() << endl;
}```