Deque Implementation in Python

← Back to Data Structures and Algorithms in Python

1. Introduction

A Deque (pronounced 'deck') is a double-ended queue that allows you to add or remove items from both the front and the back. It provides the flexibility of stacks and queues combined. Deques are often used in algorithms that need to add or remove items with both LIFO (Last-In-First-Out) and FIFO (First-In-First-Out) behaviors.

2. Implementation Steps

1. Utilize Python's inbuilt collections module which provides a deque class.

2. Define the append_left and append_right methods to add items to the front and end, respectively.

3. Define the pop_left and pop_right methods to remove items from the front and end, respectively.

4. Implement a method called is_empty to check if the deque is empty.

5. Implement a method called size to get the number of elements in the deque.

3. Implementation in Python

from collections import deque
class Deque:
    def __init__(self):
        # Initialize an empty deque
        self.items = deque()
    def append_left(self, item):
        # Add an item to the front of the deque
        self.items.appendleft(item)
    def append_right(self, item):
        # Add an item to the end of the deque
        self.items.append(item)
    def pop_left(self):
        # Remove and return an item from the front of the deque
        if not self.is_empty():
            return self.items.popleft()
        return None
    def pop_right(self):
        # Remove and return an item from the end of the deque
        if not self.is_empty():
            return self.items.pop()
        return None
    def is_empty(self):
        # Check if the deque is empty
        return len(self.items) == 0
    def size(self):
        # Return the number of items in the deque
        return len(self.items)
# Test the Deque class
dq = Deque()
dq.append_left("front1")
dq.append_right("end1")
print("Popped from left:", dq.pop_left())  # Should print front1
print("Popped from right:", dq.pop_right())  # Should print end1

Output:

Popped from left: front1
Popped from right: end1

Explanation:

1. We use the deque class from Python's collections module to efficiently implement a deque.

2. The append_left method utilizes the appendleft method of the deque class to add an item to the front.

3. The append_right method utilizes the append method of the deque class to add an item to the end.

4. The pop_left method utilizes the popleft method of the deque class to remove and return an item from the front.

5. The pop_right method utilizes the pop method of the deque class to remove and return an item from the end.

6. The is_empty method checks whether the deque is empty by comparing the length of items to 0.

7. The size method returns the number of items in the deque.

Related Data Structures in Python

1. Stack Implementation in Python
2. Queue Implementation in Python
3. Deque Implementation in Python
4. Singly Linked List Implementation in Python
5. Doubly Linked List Implementation in Python
6. Circular Linked List Implementation in Python
7. PriorityQueue Implementation in Python
8. Circular Queue Implementation in Python
9. Binary Search Tree Implementation in Python
10. Stack Implementation Using Linked List in Python
11. Stack Implementation Using Doubly Linked List in Python

← Back to Data Structures and Algorithms in Python