Deque in Python

Definition

A deque, short for double-ended queue, is an ordered collection of items that allows rapid insertion and deletion at both ends.

Syntax

In Python, deques are implemented in the collections module:

from collections import deque

# Creating a deque
d = deque(iterable)  # Create deque from iterable (optional)

Operations

1. Appending Elements:

   • append(x): Adds element x to the right end of the deque.
   • appendleft(x): Adds element x to the left end of the deque.

   Program

   from collections import deque
   
   # Initialize a deque
   d = deque([1, 2, 3, 4, 5])
   print("Initial deque:", d)
   
   # Append elements
   d.append(6)
   print("After append(6):", d)
   
   # Append left
   d.appendleft(0)
   print("After appendleft(0):", d)
   

   Output

   Initial deque: deque([1, 2, 3, 4, 5])
   After append(6): deque([1, 2, 3, 4, 5, 6])
   After appendleft(0): deque([0, 1, 2, 3, 4, 5, 6])

2. Removing Elements:

   • pop(): Removes and returns the rightmost element.
   • popleft(): Removes and returns the leftmost element.

   Program

   from collections import deque
   
   # Initialize a deque
   d = deque([1, 2, 3, 4, 5])
   print("Initial deque:", d)
   
   # Pop from the right end
   rightmost = d.pop()
   print("Popped from right end:", rightmost)
   print("Deque after pop():", d)
   
   # Pop from the left end
   leftmost = d.popleft()
   print("Popped from left end:", leftmost)
   print("Deque after popleft():", d)
   

   Output

   Initial deque: deque([1, 2, 3, 4, 5])
   Popped from right end: 5
   Deque after pop(): deque([1, 2, 3, 4])
   Popped from left end: 1
   Deque after popleft(): deque([2, 3, 4])

3. Accessing Elements:

   • deque[index]: Accesses element at index.

   Program

   from collections import deque
   
   # Initialize a deque
   d = deque([1, 2, 3, 4, 5])
   print("Initial deque:", d)
   
   # Accessing elements
   print("Element at index 2:", d[2])
   

   Output

   Initial deque: deque([1, 2, 3, 4, 5])
   Element at index 2: 3
   

4. Other Operations:

   • extend(iterable): Extends deque by appending elements from iterable.
   • extendleft(iterable): Extends deque by appending elements from iterable to the left.
   • rotate(n): Rotates deque n steps to the right (negative n rotates left).

   Program

   from collections import deque
   
   # Initialize a deque
   d = deque([1, 2, 3, 4, 5])
   print("Initial deque:", d)
   
   # Extend deque
   d.extend([6, 7, 8])
   print("After extend([6, 7, 8]):", d)
   
   # Extend left
   d.extendleft([-1, 0])
   print("After extendleft([-1, 0]):", d)
   
   # Rotate deque
   d.rotate(2)
   print("After rotate(2):", d)
   
   # Rotate left
   d.rotate(-3)
   print("After rotate(-3):", d)
   

   Output

   Initial deque: deque([1, 2, 3, 4, 5])
   After extend([6, 7, 8]): deque([1, 2, 3, 4, 5, 6, 7, 8])
   After extendleft([-1, 0]): deque([0, -1, 1, 2, 3, 4, 5, 6, 7, 8])
   After rotate(2): deque([7, 8, 0, -1, 1, 2, 3, 4, 5, 6])
   After rotate(-3): deque([1, 2, 3, 4, 5, 6, 7, 8, 0, -1])
   

Example

1. Finding Maximum in Sliding Window

from collections import deque

def max_sliding_window(nums, k):
    if not nums:
        return []

    d = deque()
    result = []

    for i, num in enumerate(nums):
        # Remove elements from deque that are out of the current window
        if d and d[0] <= i - k:
            d.popleft()

        # Remove elements from deque smaller than the current element
        while d and nums[d[-1]] <= num:
            d.pop()

        d.append(i)

        # Add maximum for current window
        if i >= k - 1:
            result.append(nums[d[0]])

    return result

# Example usage:
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
print("Maximums in sliding window of size", k, "are:", max_sliding_window(nums, k))

Output

Maximums in sliding window of size 3 are: [3, 3, 5, 5, 6, 7]

Applications

• Efficient Queues and Stacks: Deques allow fast O(1) append and pop operations from both ends, making them ideal for implementing queues and stacks.
• Sliding Window Maximum/Minimum: Used in algorithms that require efficient windowed computations.

Advantages

• Efficiency: O(1) time complexity for append and pop operations from both ends.
• Versatility: Can function both as a queue and as a stack.
• Flexible: Supports rotation and slicing operations efficiently.

Disadvantages

• Memory Usage: Requires more memory compared to simple lists due to overhead in managing linked nodes.

Conclusion

• Deques in Python, provided by the collections.deque module, offer efficient double-ended queue operations with O(1) time complexity for append and pop operations on both ends. They are versatile data structures suitable for implementing queues, stacks, and more complex algorithms requiring efficient manipulation of elements at both ends.

• While deques excel in scenarios requiring fast append and pop operations from either end, they do consume more memory compared to simple lists due to their implementation using doubly-linked lists. However, their flexibility and efficiency make them invaluable for various programming tasks and algorithmic solutions.