Contents
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 variation; Singly 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.