Queue Data Structure

Queue is a basic data structure in which an element in inserted from the one end(REAR) and removed from the other end(FRONT). This makes queue as First-In-First-Out(FIFO) data structure, which means that element inserted first will also be removed first. Queue, in real life could be related to a line of people waiting at bus stand. First person standing in line will be first to get in and any new person will be added behind. Another good example is the printer queue, the first job sent to printer will always be printed first.

There are mainly 2 functions that are performed on queue

  • enqueue(), adds an item to the end of the queue,
  • dequeue(), removes the item from the head/start of the queue
queue data structure

Consider example of a queue

  1. queue = []
    output : 5 , queue=[5]
  2. queue = [5]
    output : 4, queue=[5, 6]
  3. queue = [5, 6]
    output : 5, queue=[6]
  4. queue = [6]
    output : 5 , queue=[6, 5]

Types of the queue

  1. Circular Queue
  2. Priority Queue

Anaylsis of Queue Operations

  1. Add an element O(1)
  2. Remove an element(from FRONT) O(1)
  3. Search an element O(n)

Implementation details: Queue can be implemented using LinkedList or Arrays.