Queue is also an abstract data type or a linear data structure, just like stack data structure, in which the first element is inserted from one end called the REAR(also called tail), and the removal of existing element takes place from the other end called as FRONT(also called head).

This makes queue as FIFO(First in First Out) data structure, which means that element inserted first will be removed first.

Which is exactly how queue system works in real world. If you go to a ticket counter to buy movie tickets, and are first in the queue, then you will be the first one to get the tickets. Right? Same is the case with Queue data structure. Data inserted first, will leave the queue first.

The process to add an element into queue is called Enqueue and the process of removal of an element from queue is called Dequeue.

Basic features of Queue

  1.  Like stack, queue is also an ordered list of elements of similar data types.
  2. Queue is a FIFO( First in First Out ) structure.
  3. Once a new element is inserted into the Queue, all the elements inserted before the new element in the queue must be removed, to remove the new element.
  4. peek( ) function is oftenly used to return the value of first element without dequeuing it.

Applications of Queue

Queue, as the name suggests is used whenever we need to manage any group of objects in an order in which the first one coming in, also gets out first while the others wait for their turn, like in the following scenarios:

  1. Serving requests on a single shared resource, like a printer, CPU task scheduling etc.
  2. In real life scenario, Call Center phone systems uses Queues to hold people calling them in an order, until a service representative is free.
  3. Handling of interrupts in real-time The interrupts are handled in the same order as they arrive i.e First come first served.

Implementation of Queue Data Structure

 Queue can be implemented using an Array, Stack or Linked List. The easiest way of implementing a queue is by using an Array.

Initially the head(FRONT) and the tail(REAR) of the queue points at the first index of the array (starting the index of array from 0). As we add elements to the queue, the tail keeps on moving ahead, always pointing to the position where the next element will be inserted, while the head remains at the first index.

When we remove an element from Queue, we can follow two possible approaches (mentioned [A] and [B] in above diagram). In [A] approach, we remove the element at head position, and then one by one shift all the other elements in forward position.

In approach [B] we remove the element from head position and then move head to the next position.

In approach [A] there is an overhead of shifting the elements one position forward every time we remove the first element.

In approach [B] there is no such overhead, but whenever we move head one position ahead, after removal of first element, the size on Queue is reduced by one space each time.

Algorithm for ENQUEUE operation

  1.  Check if the queue is full or not.
  2. If the queue is full, then print overflow error and exit the program.
  3. If the queue is not full, then increment the tail and add the element.

Algorithm for DEQUEUE operation

  1.  Check if the queue is empty or not.
  2. If the queue is empty, then print underflow error and exit the program.
  3. If the queue is not empty, then print the element at the head and increment the head.

Complexity Analysis of Queue Operations

Just like Stack, in case of a Queue too, we know exactly, on which position new element will be added and from where an element will be removed, hence both these operations requires a single step.

  • Enqueue: O(1)
  • Dequeue: O(1)
  • Size: O(1)

Priority Queue

Priority Queue is more specialized data structure than Queue. Like ordinary queue, priority queue has same method but with a major difference.

In Priority queue items are ordered by key value so that item with the lowest value of key is at front and item with the highest value of key is at rear or vice versa. So we're assigned priority to item based on its key value.

Lower the value, higher the priority. Following are the principal methods of a Priority Queue. Priority Queue Data Structure is a regular Queue Data Structure with additional properties

  • Each element has a priority associated with it
  • An element with high priority is served before an element with low priority
  • If two elements have the same priority, they are served according to the order in which they are enqueue

Basic Operations of Priority Queue

  •  insert / enqueue − add an item to the rear of the queue.
  • remove / dequeue − remove an item from the front of the queue.

Priority Queue Representation

We're going to implement Queue using array in this article. There is few more operations supported by queue which are following.

  • Peek − get the element at front of the queue.
  • isFull − check if queue is full.
  • isEmpty − check if queue is empty.

Insert / Enqueue Operation

 Whenever an element is inserted into queue, priority queue inserts the item according to its order. Here we're assuming that data with high value has low priority.

Remove / Dequeue Operation

Whenever an element is to be removed from queue, queue get the element using item count. Once element is removed. Item count is reduced by one.