A linear queue is a linear data structure that mimics real-life queues. It works in FIFO (First In and First Out) order to insert and delete the elements. This is also called a simple queue because it is a basic form of the queue
Representation of Queue
- Front: Front side of the queue
- Rear: Rear side of the queue
- Element: The actual data
- Way In: Insertion on the Rear side
- Way Out: Removal from the Front side
Queue Operations and Time complexity
Here is the table of operations and time complexity of queues. Insertion and deletion work faster in O(1) time, but the search takes O(n) time.
| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Enqueue | Insert a new element on the Rear | O(1) | O(n) |
| Dequeue | Delete the element from Front | O(1) | O(n) |
| Peek | Returns the front element without removing | O(1) | O(n) |
| IsFull | Check if the queue is full | O(1) | O(n) |
| IsEmpty | Check if the queue is empty | O(1) | O(n) |
| Search | Search the element by value. | O(n) | O(n) |
What is Enqueue and Dequeue?
An enqueue operation inserts a new element in the rear side. Whereas, Dequeue removes from the front side. So, these two operations restrict the queues to follow the FIFO order.
Dequeue operation is sometimes confused with the word Deque. But Deque refers to Double Ended Queue.
Implementations of Queue with Example
Queues can be implemented both using Array and Linked List. However, we need to choose based on the nature of the data.
Array Implementation of Queue
Array implementation of the queue is static and limited by size. However, it works faster than linked lists because the array memory is continuous and cache-friendly for the CPU. So, use the array-based implementation for the fixed amount of data.
Queue implementation using Array with Example
Linked List Implementation of Queue
The linked list implementation of the queue is dynamic in size and grows/shrinks based on dynamic data. But it can be slower than the array as it requires runtime allocation and deallocation. So, use the linked list implementation only for the dynamic nature of data.
Queue implementation using Linked List with Example
Advantages and Disadvantages of Linear Queue
The followings are the pros and cons of Linear Queues.
Advantages
- Faster insertion and deletion operations in O(1) time.
Disadvantages
- Memory space is not effectively used in Array Implementation. There will be empty spaces created on the Front side on deletion. But, the Linear Queue is considered Full when the Rear reaches the last position. As a result, the empty spaces in the Front are not utilized until the queue becomes empty. This is a drawback of linear queues. Anyway, this problem is addressed in Circular Queue.
Applications
When to use the Linear Queue
Linear queues can be used in applications that process the data in First In and First Out (FIFO) order. But, avoid using the array-based implementation since it is memory inefficient. Instead, use the Circular Queues.
Realtime Applications of Linear Queue
- Resource sharing operations such as disk scheduling. Disk operations can be queued and run on a FIFO order.
- Asynchronous transfer applications such as pipes use linear queues. A sender can enqueue the input data on the front side while the receiver dequeue from another end. Also, IO buffers rely on this for asynchronous transmission. For example, a keyboard device can buffer the sequence of keystrokes.
- Printers use linear queues to cache the input requests. Thus, process the print requests in FIFO order.
- Music players can use the queue for playlists and play the songs in order.