Queue

Queue is a Non Primitive, Linear Data Structure which follows FIFO (First In First Out) pattern. That means, an element which is inserted first will be deleted or accessed first.

Types of Queue in Data Structure

Basically there a four types of Queue in Data Structure

  1. Simple Queue
  2. Circular Queue
  3. Deque (Double Ended Queue)
  4. Priority Queue

1. Simple Queue

  • A queue is a linear list of elements in which deletion can take place only at one end, called the FRONT and insertion can take place only at the other end, called the REAR.
  • The information in such a list is processed in FIFO (First In First Out) pattern.
  • The process to add an element in a queue is called Enqueue Operation.
  • The process of removal of element from a queue is called Dequeue Operation.
  • Ex. Checkout line at supermarket cash register where the first person in line is usually the first to be checked out.
  •  Queue is maintained by a linear array ie. “Q” and two pointer variables
    • FRONT : Containing location of Front element of Queue.
    • REAR : Containing location of Rear element of the Queue.
  • The condition FRONT = -1 will indicate Q is Empty.
  • The condition REAR >= N-1 will indicate Q is Full.

Simple Queue Data Structure


Algorithm for Insertion and Deletion in Simple Queue :

Simple Queue Insertion Operation : Enqueue() Algorithm 

Copy to Clipboard


Simple Queue Deletion Operation : Dequeue() Algorithm

Copy to Clipboard

There is one drawback of Simple Queue. That is, if simple queue is full ie. R == N-1 and if we delete elements from front end of queue. Now, even though we have some free spaces available at front end in simple queue, we can not utilize that space and insert new elements at front. So to overcome this drawback of simple queue, Circular Queue is introduced.


2. Circular Queue

  • A more suitable method of representing simple queue which prevents an excessive use of memory is to arrange elements in a Circular fashion, this is called Circular Queue.
  • In Circular Queue, last node is connected back to the first node to make a circle.
  • The process to add an element in a Circular queue is also called Enqueue Operation.
  • The process of removal of element from a Circular queue is also called Dequeue Operation.
  •  Queue is maintained by a linear array ie. “Q” and two pointer variables
    • FRONT : Containing location of Front element of Queue.
    • REAR : Containing location of Rear element of the Queue.

Circular Queue Data Structure

Algorithm for Insertion and Deletion in Circular Queue :

Circular Queue Insertion Operation : Enqueue() Algorithm 

Copy to Clipboard


Circular Queue Deletion Operation : Dequeue() Algorithm

Copy to Clipboard


3. Dequeue (Double Ended Queue)

  • A Dequeue is a linear list in which insertion and deletion are performed from the either end of the structure.
  • There are two variations of Dequeue
    • Input Restricted Dequeue:
      • It allows insertion at only one end (REAR end only) and allows deletion from both the ends.
    • Output Restricted Dequeue:
      • It allows deletion from only one end (FRONT end only) and allows insertion from both the ends.
  • The process to add an element in a Circular queue is also called Enqueue Operation.
  • The process of removal of element from a Circular queue is also called Dequeue Operation.
  •  Queue is maintained by a linear array ie. “Q” and two pointer variables
    • FRONT : Containing location of Front element of Queue.
    • REAR : Containing location of Rear element of the Queue.
  • Such a structure can be represented by figure shown below.

Double Ended Queue Data Structure


4. Priority Queue

  • A priority queue is a collection of elements such that each element has been assigned a priority and such that the order in which elements are deleted and processed comes from following rules
    1. An element with higher priority is processed before any element with lower priority.
    2. Two elements with the same priority are processed according to the order in which they were added to the queue.
  • A prototype of a priority queue is a time-sharing system: Programs of high priority are processed first, and programs with the same priority form a standard queue (FIFO).

In this article, we have learned about all basic types of queue in Data Structure with algorithm for Insertion and Deletion operation in Queue. I hope you understand basics about queue.