Deque & Monotonic Queue

What is a Deque?

Deque (Double-Ended Queue):

• Definition: A deque is a data structure that allows insertion and deletion of elements from both ends: the front (head) and the back (tail).
• Operations:
  • pushBack(x): Add element x to the back.
  • pushFront(x): Add element x to the front.
  • popBack(): Remove and return the element from the back.
  • popFront(): Remove and return the element from the front.
• Advantages:
  • Provides O(1) time complexity for both append and pop operations from either end.
  • Flexible for use cases requiring operations at both ends.

TypeScript Example (not built-in structure)

// Creata a deque
const deque: Deque<number> = new Deque<number>();

// Push elements
deque.pushBack(1);		// Deque: [1]
deque.pushFront(2);		// Deque: [2, 1]

// Remove elements
deque.popBack();			// Returns 1, Deque: [2]
deque.popFront();			// Returns 2, Deque: []

Python Example:

from collections import deque

# Create a deque
d = deque()

# Append elements
d.append(1)       # Deque: [1]
d.appendleft(2)   # Deque: [2, 1]

# Remove elements
d.pop()           # Returns 1, Deque: [2]
d.popleft()       # Returns 2, Deque: []

What is a Monotonic Queue?

Monotonic Queue:

• Definition: A monotonic queue is a specific type of deque that maintains its elements in a sorted order, either non-increasing or non-decreasing.

• Purpose: It is used to keep track of elements in a way that the largest (or smallest) element is always easily accessible.

• Operations:

  Similar to a deque but with additional steps to maintain the order:

  • Maintain Order on Append:
    • When adding a new element, remove elements from the back that violate the monotonic property.
  • Efficient Extremum Access:
    • The maximum or minimum element is always at the front of the queue.

Example of a Monotonic Decreasing Queue:

TypeScript Example (not built-in structure)

class MonotonicQueue {
	private deque: Deque<number>;

	constructor() {
		this.deque = new Deque<number>();
	}

	// Enqueue in non-increasing order
	public enqueue(num: number): void {
		while (!this.deque.isEmpty() && this.deque.peekBack() < num) {
			this.deque.popBack();
		}
		this.deque.pushBack(num);
	}

	// Only remove if this is the max value in the last window,
	// otherwise it has already been removed during an enqueue process
	public dequeue(num: number): void {
		if (num === this.deque.peekFront()) {
			this.deque.popFront();
		}
	}

	public max(): number {
		return this.deque.peekFront();
	}
}

// Initialize mono queue
const monoQueue: MonotonicQueue = new MonotonicQueue();

// Add elements
monoQueue.enqueue(1);		// Queue: [1]
monoQueue.enqueue(3);  	// Queue: [3]
monoQueue.enqueue(2);		// Queue: [3, 2]

Python Example:

# This example is for maintaining a decreasing order queue
from collections import deque

# Initialize deque
monotonic_queue = deque()

# Function to maintain monotonic decreasing order
def add_element(q, value):
    # Remove elements from the back if they are smaller than the current value
    while q and q[-1] < value:
        q.pop()
    q.append(value)

# Add elements
add_element(monotonic_queue, 1)    # Deque: [1]
add_element(monotonic_queue, 3)    # Deque: [3]
add_element(monotonic_queue, 2)    # Deque: [3, 2]

Why Monotonic Queue is Often Bound with Deque?

1. Efficient Extremum Management:
   • A deque’s double-ended nature allows for efficient addition and removal of elements, which is essential for maintaining the order required by a monotonic queue.
2. Sliding Window Optimization:
   • In sliding window problems, elements at the front of the deque can be quickly checked and removed if they fall out of the current window’s range, ensuring the queue only contains relevant elements.
3. Maintaining Order with Minimal Operations:
   • The operations needed to maintain a monotonic order (removing elements from the back if they violate the order) are straightforward with a deque, making it a natural fit.

Summary

• Deque: Provides efficient double-ended operations.
• Monotonic Queue: Maintains elements in a specific order for quick extremum access.
• Combination Benefits: Together, they offer an optimal solution for sliding window maximum problems by combining efficient order maintenance and rapid element removal/addition.