Deque (Double Ended Queue) (Data Structures & Algorithms)

Why This Matters

In this lesson, we will delve deeper into the world of data structures and algorithms using Python examples by focusing on a versatile and essential data structure called the Deque (Double Ended Queue). Understanding Deques is crucial for tackling problems that require flexible access to items at the beginning or end of a sequence. This data structure plays a significant role in solving real-world problems such as parsing expressions, implementing web browsers' history, and optimizing network traffic management systems. Moreover, knowing how to use Deques can help you stand out during job interviews and coding competitions.

Prerequisites

To fully grasp the concepts presented in this lesson, you should have a solid understanding of Python programming basics, including variables, functions, loops, and data structures like lists and tuples. Familiarity with basic data structures and algorithms is also beneficial. It's recommended that you review these topics before proceeding with this lesson.

Important Concepts to Review:

• Basic Python syntax
• Lists and list comprehensions
• Tuples
• Functions and recursion
• Loops (for, while)
• Error handling (try/except)

Core Concept

A Deque (Double Ended Queue) is an abstract data type that extends the functionality of a traditional queue by allowing insertion and removal of elements from both ends: the front (left) and rear (right). This versatility makes it more flexible than a standard queue, which only allows insertions at the rear and removals from the front.

In Python, we can use the collections module to access the Deque implementation. The deque() function creates an empty deque, while deque(iterable) initializes a deque with elements from an iterable object such as lists, tuples, or strings.

from collections import deque

Creating an empty deque

my_deque = deque()

Initializing a deque with elements

my_deque = deque([1, 2, 3])

Deques in Python are implemented as doubly linked lists, which means each element has both a next and a previous pointer. This allows for constant time (O(1)) insertions and deletions at either end of the deque, making it more efficient than using lists or arrays for certain operations.

### Basic Operations

- `deque.appendleft(x)`: Adds an element `x` to the front of the deque.
- `deque.append(x)`: Adds an element `x` to the rear of the deque.
- `deque.popleft()`: Removes and returns the first (leftmost) element in the deque.
- `deque.pop()`: Removes and returns the last (rightmost) element in the deque.
- `deque.extend(iterable)`: Adds elements from iterable to the rear of the deque.
- `deque.extendleft(iterable)`: Adds elements from iterable to the front of the deque.

Worked Example

Let's consider a simple example where we use a Deque to implement a Last-In-First-Out (LIFO) stack using Python.

from collections import deque

Creating an empty deque as our LIFO stack

my_stack = deque()

Pushing elements onto the stack

my_stack.append(1)

my_stack.append(2)

my_stack.appendleft(3)

print("Stack: ", my_stack) # Output: Stack: deque([3, 1, 2])

Popping elements off the stack (LIFO order)

print(my_stack.pop()) # Output: 2

print(my_stack.pop()) # Output: 3

print(my_stack.pop()) # Output: 1

In this example, we create an empty deque and push elements onto it using the `append()` and `appendleft()` methods. We then pop the elements off the stack in LIFO order by calling the `pop()` method.

### Extending our LIFO Stack Example

Let's now modify the previous example to demonstrate how to check if the stack is empty and add additional functionality to print the current state of the stack.

from collections import deque

Creating an empty deque as our LIFO stack

my_stack = deque()

def push(item):

if not my_stack:

print("Stack is empty. Adding item:", item)

my_stack.appendleft(item)

else:

print("Adding item:", item)

my_stack.appendleft(item)

def pop():

if my_stack:

return my_stack.pop()

else:

print("Stack is empty.")

def print_stack():

print("Current Stack State:", my_stack)

push(4)

push(5)

print_stack() # Output: Current Stack State: deque([5, 4])

print(pop()) # Output: 5

print_stack() # Output: Current Stack State: deque([4])

In this modified example, we've added a `push()` function that checks if the stack is empty before adding an item. We've also created a `pop()` function and a `print_stack()` function for convenience.

Common Mistakes

• Forgetting to import the collections module: Always make sure you have imported the collections module before using the deque() function or any of its methods.
• Incorrectly assuming deque is a built-in data type: Deque is not a built-in Python data structure, so it's essential to import it from the collections module.
• Using list or array methods on a deque object: Since deques are implemented as doubly linked lists, using list or array methods may lead to unexpected results and inefficient code.

Common Mistakes (continued)

• Misunderstanding the order of operations with extend() and extendleft(): The extend() method adds elements to the rear of the deque, while extendleft() adds elements to the front. Be mindful of this when working with these methods.
• Not handling edge cases properly: When using Deques for problems like implementing a LIFO stack or FIFO queue, make sure to handle edge cases such as an empty stack/queue and checking if the maximum size has been reached before adding elements.

Practice Questions

1. Implement a function that takes a string and returns the reverse of the string using a Deque in Python.

from collections import deque

def reverse_string(s):
reversed_s = deque(s)
return "".join(reversed_s)

print(reverse_string("Hello World")) # Output: dlroW olleH

1. Write a program that uses a Deque to implement a FIFO queue with a maximum size of 5 elements.

from collections import deque

class LimitedFIFOQueue:
def __init__(self, max_size):
self.max_size = max_size
self.queue = deque()

def enqueue(self, item):
if len(self.queue) < self.max_size:
self.queue.append(item)
else:
print("Queue is full. Cannot enqueue.", item)

def dequeue(self):
if self.queue:
return self.queue.popleft()
else:
print("Queue is empty. Cannot dequeue.")
return None

Testing the LimitedFIFOQueue class

limited_fifo = LimitedFIFOQueue(5)

limited_fifo.enqueue(1)

limited_fifo.enqueue(2)

limited_fifo.enqueue(3)

limited_fifo.enqueue(4)

limited_fifo.enqueue(5)

print("Dequeued: ", limited_fifo.dequeue()) # Output: Dequeued: 1

print("Dequeued: ", limited_fifo.dequeue()) # Output: Dequeued: 2

limited_fifo.enqueue(6) # This should print "Queue is full. Cannot enqueue. 6"

3. Given two deques representing two stacks, write a function that checks if they are equal (i.e., have the same elements in the same order) using Python.

def are_stacks_equal(stack1, stack2):

if len(stack1) != len(stack2):

return False

while stack1 and stack2:

if stack1[0] != stack2[0]:

return False

stack1.popleft()

stack2.popleft()

return not (stack1 or stack2) # Both stacks are empty

FAQ

What is the time complexity of basic Deque operations?

• appendleft(x): O(1)
• append(x): O(1)
• popleft(): O(1)
• pop(): O(1)
• extend(iterable): O(n)
• extendleft(iterable): O(n)

Is it possible to create a Deque with preallocated memory?

In Python, the size of a deque can be adjusted dynamically as elements are added or removed. However, if you want to initialize a deque with preallocated memory, you can use slicing: deque(iterable)[start:end]. For example, my_deque = deque([0]*10) creates a deque with 10 elements initialized to 0.

What are some real-world applications of Deques?

Deques have various practical uses in programming, such as implementing web browsers' history, parsing expressions, and optimizing network traffic management systems. They can also be used for implementing LIFO stacks, FIFO queues, or circular buffers with efficient insertion and removal at both ends. Additionally, Deques can help optimize certain algorithms like Breadth-First Search (BFS) and Depth-First Search (DFS), as they allow for more flexible traversal of graphs. Furthermore, Deques can be used in solving problems that require frequent insertions and deletions at both ends of a sequence, making them an efficient choice compared to lists or arrays in such cases.