Python deque

In Python, the `deque` (double-ended queue) is a collection from the `collections` module that allows fast and efficient insertion and removal of elements from both ends. Unlike lists, `deque` is optimized for quick append and pop operations at either end, making it suitable for queue and stack-like structures.

Key features of `deque`:
- Fast appends and pops from both the left and right ends.
- Optimized for handling larger collections where both ends require frequent access.
- Supports a maximum length limit, causing automatic discarding of elements from the opposite end when this limit is exceeded.

Deque Representation

As mentioned, deque allows you to efficiently add and remove elements from both ends. Here's a basic representation:

Front → [ A | B | C | D | E ] ← Back

Key Operations

Adding Elements:
Append (at the back):

deque.append(F)
→ [ A | B | C | D | E | F ]

Appendleft (at the front):

deque.appendleft(Z)
→ [ Z | A | B | C | D | E | F ]

Removing Elements:
Pop (from the back):

deque.pop()
→ [ A | B | C | D | E ]

Popleft (from the front):

deque.popleft()
→ [ B | C | D | E ]

1. Importing `deque`

To use `deque`, you need to import it from the `collections` module.

from collections import deque

2. Creating and Initializing a `deque`

A `deque` can be initialized empty or with an initial iterable of values. Here are examples:

# Initializing an empty deque
dq = deque()
print("Empty deque:", dq)

# Initializing deque with elements
dq_with_values = deque([1, 2, 3])
print("Deque with initial values:", dq_with_values)

Output:
Empty deque: deque([])
Deque with initial values: deque([1, 2, 3])

3. Basic Operations with `deque`

Adding Elements
With `deque`, you can add elements to either end using `append` and `appendleft`:

dq = deque([2, 3])

# Append to the right
dq.append(4)
print("After append(4):", dq)

# Append to the left
dq.appendleft(1)
print("After appendleft(1):", dq)

Output:
After append(4): deque([2, 3, 4])
After appendleft(1): deque([1, 2, 3, 4])

Removing Elements
Remove elements from both ends using `pop` (right) and `popleft` (left):

# Removing from both ends
dq = deque([1, 2, 3, 4])

# Pop from the right
dq.pop()
print("After pop():", dq)

# Pop from the left
dq.popleft()
print("After popleft():", dq)

Output:
After pop(): deque([1, 2, 3])
After popleft(): deque([2, 3])

4. Working with `maxlen` in `deque`

The `maxlen` parameter sets a maximum length for the `deque`. If this limit is reached, adding new elements discards items from the opposite end:

# Creating a deque with maxlen of 3
dq_max = deque([1, 2, 3], maxlen=3)
print("Initial deque with maxlen=3:", dq_max)

# Adding a new element
dq_max.append(4)
print("After appending 4:", dq_max)

Output:
Initial deque with maxlen=3: deque([1, 2, 3], maxlen=3)
After appending 4: deque([2, 3, 4], maxlen=3)

Explanation: When `4` is appended, the oldest item (`1`) is discarded due to the maximum length constraint.

5. `deque` Rotation

`deque` provides a `rotate()` method that shifts elements to the right or left, effectively rotating them:

dq = deque([1, 2, 3, 4, 5])

# Rotate right by 2
dq.rotate(2)
print("After rotating right by 2:", dq)

# Rotate left by 1 (same as rotating right by -1)
dq.rotate(-1)
print("After rotating left by 1:", dq)

Output:
After rotating right by 2: deque([4, 5, 1, 2, 3])
After rotating left by 1: deque([5, 1, 2, 3, 4])

Explanation: Positive values rotate to the right, while negative values rotate to the left.

6. `deque` Extend Operations

`deque` offers `extend` and `extendleft` methods to add multiple elements at once.

dq = deque([3, 4])

# Extending at the right end
dq.extend([5, 6])
print("After extend([5, 6]):", dq)

# Extending at the left end
dq.extendleft([2, 1])
print("After extendleft([2, 1]):", dq)

Output:
After extend([5, 6]): deque([3, 4, 5, 6])
After extendleft([2, 1]): deque([1, 2, 3, 4, 5, 6])

Explanation: `extendleft` adds items in reverse order.

7. `deque` as a Stack

Using `deque` as a stack, we can leverage `append` and `pop` for Last In, First Out (LIFO) behavior:

stack = deque()

# Pushing elements onto stack
stack.append("A")
stack.append("B")
stack.append("C")
print("Stack after pushes:", stack)

# Popping elements from stack
stack.pop()
print("Stack after pop:", stack)

Output:
Stack after pushes: deque(['A', 'B', 'C'])
Stack after pop: deque(['A', 'B'])

8. `deque` as a Queue

Using `deque` as a queue, we can use `append` and `popleft` for First In, First Out (FIFO) behavior:

queue = deque()

# Enqueue elements
queue.append("A")
queue.append("B")
queue.append("C")
print("Queue after enqueues:", queue)

# Dequeue elements
queue.popleft()
print("Queue after dequeue:", queue)

Output:
Queue after enqueues: deque(['A', 'B', 'C'])
Queue after dequeue: deque(['B', 'C'])

9. Checking Membership in `deque`

`deque` supports checking if an element exists using `in` and `not in`:

dq = deque([1, 2, 3, 4, 5])

# Check for presence of elements
print("Is 3 in deque?", 3 in dq)
print("Is 6 not in deque?", 6 not in dq)

Output:
Is 3 in deque? True
Is 6 not in deque? True

10. Clearing a `deque`

The `clear` method removes all elements from the `deque`:

dq = deque([1, 2, 3])
dq.clear()
print("Deque after clear:", dq)

Output:
Deque after clear: deque([])

Summary

`deque` provides an efficient, versatile data structure for operations at both ends. It supports FIFO and LIFO usage patterns, allowing it to serve as both a queue and a stack, and includes methods for rotating, extending, and even limiting length with `maxlen`. This makes `deque` a powerful tool for real-time data processing and applications requiring rapid data manipulation.