Data Structures

Linear Queue in Data Structure

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

Linear Queue Representation
Linear Queue Representation
  • 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.

OperationDescriptionTime
Complexity
Space
Complexity
EnqueueInsert a new element on the RearO(1)O(n)
DequeueDelete the element from FrontO(1)O(n)
PeekReturns the front element without removingO(1)O(n)
IsFullCheck if the queue is fullO(1)O(n)
IsEmptyCheck if the queue is emptyO(1) O(n)
SearchSearch the element by value.O(n)O(n)
Time and Space complexity of Queue operations

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.
Copyright copyright 2024 Simplerize