Queues- Introduction and Memory Representation

Queue is linear data structure based on “First In First Out” (FIFO) principle. The elements that are inserted earlier will be deleted before those elements which are added later.  It is used to maintain sequence of events occurring. Queue Applications is in solving problems where you have to maintain the first come first serve sequence of tasks or action. 

It can be visualised as a memory area that keeps on adding the elements at the end of existing elements. When you wish to remove an element, you can do so from the beginning of the list. A new element ia always added at the end of the existing elements’ list.

In real world you can see queues of people standing to buy a movie ticket or get on a bus at bus stop. The luggage counters in airports, taxis entering and exiting a tunnel are other queue applications in real life. In all these physical applications of queue, an item is added at the end and removed from the beginning. First In First Out!!!!

Memory Representation of Queues

Like Stacks, Queues can also be represented in memory in two ways.

  • Using the contiguous memory like an array
  • Using the non-contiguous memory like a linked list

Using the Contiguous Memory like an Array

In this representation the Queue is implemented using the array. Variables used in this case are

  • QUEUE- the name of the array storing queue elements.
  • FRONT- the index where the first element is stored in the array representing the queue.
  • REAR- the index where the last element is stored in array representing the queue.
  • MAX- defining that how many elements (maximum count) can be stored in the array representing the  queue.
Queue Application using Array

Using the Non-Contiguous Memory like a Linked List

In this representation the queue is implemented using the dynamic data structure Linked List. Using linked list for creating a queue makes it flexible in terms of size and storage. You don’t have to define the maximum number of elements in the queue.

Pointers (links) to store addresses of nodes for defining a queue are.

  • FRONT- address of the first element of the Linked list storing the Queue.
  • REAR- address of the last element of the Linked list storing the Queue.
Linked List Representation of Queue

Queue Applications

Queues are used in various applications in Computer Science-

  • Job scheduling tasks of CPU.
  • Printer’s Buffer to store printing commands initiated by a user.
  • Input commands sent to CPU by  devices like Keyboard and Mouse.
  • Document downloading from internet.
  • User Requests for  call center services.
  • Order Queue for Online Food Delivery Chains.
  • Online Cab Booking applications.

Be First to Comment

Leave a Reply

Your email address will not be published.