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.
To learn more about simple queue, visit Queue Data Structure.
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
andREAR
are set to-1
. - For enqueue operation first of all check the queue is full or not. If
FRONT
is -1 then setFRONT
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
.
- If queue is full then its overflow condition. (if (
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
.
- If queue is empty then its underflow condition. (if
Display:
- If queue is empty then print/return queue is empty.
- Print the elements at the position from
FRONT
to REAR, incrementing size ofFRONT
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; } // Adding an element 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 self.head = self.tail = -1 # Insert an element into the circular queue def enqueue(self, data): if ((self.tail + 1) % self.k == self.head): print("Overflow\n") elif (self.head == -1): self.head = 0 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): if (self.head == -1): print("Underflow\n") elif (self.head == self.tail): temp = self.queue[self.head] self.head = -1 self.tail = -1 return temp else: temp = self.queue[self.head] self.head = (self.head + 1) % self.k return temp def printCQueue(self): if(self.head == -1): print("Queue is empty") elif (self.tail >= self.head): for i in range(self.head, self.tail + 1): print(self.queue[i], end=" ") print() else: for i in range(self.head, self.k): 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 == [] def addRear(self, item): self.items.append(item) def addFront(self, 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() d.addRear(1) d.addRear(2) d.addFront(5) print(d.isEmpty()) print(d.size()) d.addRear(11) 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; addRear(arr, 5, &front, &rear); addFront(arr, 12, &front, &rear); addRear(arr, 11, &front, &rear); addFront(arr, 5, &front, &rear); addRear(arr, 6, &front, &rear); addFront(arr, 8, &front, &rear); 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); addRear(arr, 16, &front, &rear); addRear(arr, 7, &front, &rear); 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; }
4) Priority Queue
Visit https://www.geeksforgeeks.org/priority-queue-set-1-introduction/ for more info about priority queue.