CS Code

Coding, quiz & more

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.

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 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;
  }
  // 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.

‹ Queue Data Structure
› Linked List Data Structure

Back to top