In computer science, efficient data structure implementations are vital for building high-performance software. One such challenge is implementing a queue that supports `push_rear()`, `pop_front()`, and `get_min()` operations, all of which need to run in constant time: $O(1)$. Achieving this necessitates careful design. In this article, we explore a solution using a combination of deque and auxiliary structures.

Core Concepts

A queue traditionally supports following operations:

• Push Rear: Add element to the rear end.
• Pop Front: Remove element from the front.
• Get Minimum: Retrieve the smallest element in the queue.

Meeting the constant time constraint for all three operations requires a hybrid approach leveraging multiple data structures.

Data Structures Used

1. Deque (Double-ended Queue): Allows insertion and deletion of elements from both ends in constant time.
2. Auxiliary Min-Tracking Deque: This additional deque helps keep track of the minimum element, updating efficiently when elements are added or removed.

Operational Details

Here are the operational mechanics and how constant time complexity is achieved:

1. push_rear(x):
   • Append the element `x` to the main deque 'Q'.
   • While the auxiliary deque 'MinDeque' is not empty and the element at the rear is greater than `x`, remove the element from the rear of 'MinDeque'.
   • Append `x` to the rear of 'MinDeque'. This ensures 'MinDeque' remains sorted in increasing order from front to rear, maintaining potential minimum values.
2. pop_front():
   • Remove the element from the front of the main deque 'Q'.
   • If this element is equal to the front element of 'MinDeque', pop that front element from 'MinDeque' as well. Ensures the minimum element deque accurately corresponds to the elements in 'Q'.
3. get_min():
   • Simply return the front element of 'MinDeque', which is the smallest element in 'Q'.

Example Implementation

To see this approach in action, consider the following Python snippet:

• Empty queue operations must be handled gracefully to avoid exceptions or logical errors.
• Handling non-integer data types may require adaptation depending on data type properties (e.g., string comparison).