by Queue is a data structure used for storing collection of data where order in which data is arriving is important. In Queue, insertion and deletion both happened from the different end.
Data insertion are done at one end which is known as “rear end” while data deletion are done at other end known as “front end“. The data which is arrived first will be deleted first in Queue. This data ordering is called as First in First out or FIFO.
Properties of Queue
- Insertion and Deletion both happened from the different end.
- Sequence in which data is arrived is important.
- Data can be accessed in Queue in FIFO (First in First out) format.
Let’s look into the below diagram to understand how Queue works.
Applications of Queue
- Operating System Jobs scheduling
- Asynchronous data transfer such file, sockets etc.
- FIFO scenario handling such as attending customers
- Multiprogramming
Queue Operations
- Enqueue – This operation will add an entry into the Queue at the rear end of the Queue. In case Queue is full then error is returned. This condition is called Queue Overflow.
- Dequeue – This operation will remove the front entry from the Queue. In case Queue is empty then error is returned. This condition is called Queue Underflow.
- IsEmpty – This operation will check whether Queue is empty or not.
- Size/Entries – This operation will return the number of entries present in Queue.
- AtFront – This operation will return the front element from the Queue. This operation will not remove the front element from the Queue.
Implementation of Queue
- Simple circular array
- Dynamic circular array
- Linked List implementation
Comparison between Simple Array vs Linked List implementation
| Parameter | Simple Array | Linked List |
|---|---|---|
| Space Complexity | O(n) | O(n) |
| Enqueue() Time Complexity | O(1) | O(1) |
| Dequeue() Time Complexity | O(1) | O(1) |
| IsEmpty() Time Complexity | O(1) | O(1) |
| Entries() Time Complexity | O(1) | O(1) |
| IsFull() Time Complexity | O(1) | O(1) |
| DeleteQueue() Time Complexity | O(1) | O(n) |
| Queue Size | Expensive expansion operation once a while | Graceful expansion or shrink operation |
| Space and Time Usage | No extra space needed | Extra space needed along with reference manipulation |
