Queue Data Structure

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

---

 Queue is a Linear Data Structure in which operation performed in certain order.

Real life example of queue is line of people outside the cinema hall to buy film tickets.

The order of operation in queue is FIFO(First In First Out) or LILO(Last In Last Out).

---

Operations of Queue

Following basic operations are performed in the queue:

1. Enqueue: Add an element to end of the queue. If queue is full then its overflow condition.
2. Dequeue: Remove an element from front of the queue. If queue is empty then its underflow condition.
3. Front: Pick front item from queue.
4. Rear: Pick rear item from queue.
5. isEmpty: Returns True if queue is empty else return False
6. isFull: Returns True if queue is full else return False

Time complexity of enqueue, dequeue, get Front, get Rear, isEmpty and isFull operations in a queue using an array is O(1).

Auxiliary Space required is O(n) where n is size of the array.

---

Applications of Queue

• In Breadth First Search(BFS) algorithm.
• First Come First Serve (FCFS) scheduling.
• Queue is used in router (also called as buffer). If packets arrive faster than the router can process them then the router puts them into the queue.

---

Queue Implementations using array

class Queue:

    def __init__(self):
        self.queue = []

    def enqueue(self, item):
        self.queue.append(item)

    def dequeue(self):
        if len(self.queue) < 1:
            return None
        return self.queue.pop(0)

    def display(self):
        print(self.queue)

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


q = Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)

q.display()

#include <stdio.h>
#define SIZE 5

void enQueue(int value) {
  if (rear == SIZE - 1)
    printf("\nOverflow");
  else {
    if (front == -1)
      front = 0;
    rear++;
    items[rear] = value;
    printf("\nInserted element: %d", value);
  }
}

void deQueue() {
  if (front == -1)
    printf("\nUnderflow");
  else {
    printf("\nDeleted element: %d", items[front]);
    front++;
    if (front > rear)
      front = rear = -1;
  }
}

void display() {
  if (rear == -1)
    printf("\nQueue is Empty!!!");
  else {
    int i;
    printf("\nElements in the queue are:\n");
    for (i = front; i <= rear; i++)
      printf("%d \t", items[i]);
  }
  printf("\n");
}


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

int main() {
  //enQueue 3 elements
  enQueue(1);
  enQueue(2);
  enQueue(3);
  
  //dequeue a element
  deQueue();

  display();

 
  return 0;
}

---

Types of Queue

1. Circular Queue
2. Priority Queue
3. Deque

---

‹ Stack Data Structure
› Types Of Queue