Queue

Reading Time: 2 minutes

Definition

Queue is a linear data structure that maintains FIFO setting; First In First Out. Queue comes in two possible internal implementations; Singly Linked List or Array. When think of FIFO, we can assume a group of people waiting queued up for buying a cinema ticket. The first person in the queue gets to buy the ticket and it follows the rest of the people in the queue.

Sample Queue Usage Areas

  • Hardware Scheduling; CPUs and Disks are properly scheduled in the concurrent environments,
  • Asynchronous communication makes a great use case while two processes wait for each other to respond in sequence

Implementation

In the internally Queue can implement Singly Linked List or Array. Eventually the Time Complexity of the operations will slightly differ. In this stackoverflow Article, there are more insights and argument about the implementations. In my own implementation I preferred to use the Singly Linked List implementation.

Complexity of Queue

Since the internals of implementations differ for each variationSingly Linked List and Array, the operations can differ. The given table is suitable for Singly Linked List implementation;


image courtesy of  bigocheatsheet.com

Operations on Queue


Queue has three vital operations that we need to cover up. In some other languages and Stack implementations definitely have other additional operations like Java’s Queue implementation. However, these below operations are fundamental properties of the Queue data structure:

  • enqueue:  inserts the element to the head of the stack,
  • denqueue: removes the element from the head  and returns
    denqueued the value,
  • peek: returns the head data but doesn’t delete it, takes a peek at it.

Code

The code can be also found in my Github Repository @ https://github.com/tugrulaslan/BlogCodeSnippets/tree/master/DataStructures to see how the code works, you can also check its Unit Test.

Leave a Reply

Your email address will not be published. Required fields are marked *