Learn about the deque data structure and how to implement it in Python!

Implementing Deque in Python

Congratulations! You've completed the lesson and have learned what deques are and how to implement one in Python. We have covered:

* What a deque is and how it relates to queues and stacks
* What operations (methods) are needed to implement a deque
* How to implement these deque methods
* The time complexity for each deque method

Happy Coding!

Review

You may need a way to determine if the plane is empty of passengers (to ensure everyone has deboarded) or to see exactly how many passengers are on board. To do this, we can implement two methods: `is_empty()` and `size()`. These methods are also helpful in making sure we avoid calling our deque methods on an empty deque. 

To determine if the deque is empty, we implement the `is_empty()` method, which should:

* Return `True` if the deque is empty (has 0 items in the `elements` list) or `False` if the deque contains one or more elements.

To obtain the size of the deque, we implement the `size()` method, which should:

* Return the length of the deque(the number of items in the `elements` list).

Implementing is_empty and size

A *deque*, which stands for double-ended queue, is a data structure that allows users to insert and delete items at both ends of the queue. Because we can insert and delete from both ends, a deque is considered both a queue and a stack.
 
There are some basic operations involved when implementing a deque using a list structure:
 
* `add_first(item)`: adds an item to the front of the deque
* `add_last(item)`: adds an item to the rear of the deque
* `remove_first()`: removes (and returns) the item in the front of the deque
* `remove_last()`: removes (and returns) the item in the rear of the deque
* `is_empty()`: returns `True` if the deque is empty and `False` otherwise
* `size()`: returns the size of the deque (number of elements)
 
Peek operations are also common for a deque. They allow us to view the front or rear items in the deque without removing them.
 
The front and rear of the deque should be determined first. The front and rear designations are interchangeable, however, the deque operation implementations would need to be adjusted based on which ends become the rear and front. Throughout this lesson, we will designate the front of the deque as the rightmost end of the deque and the rear of the deque as the leftmost end.

As we step through implementing a deque in Python, let's introduce a real-world scenario of when we would use a deque that we can reference as we implement each operation. Imagine you are an airport gate attendant in charge of flight boarding. The plane in which you are overseeing the boarding of allows for boarding and deboarding from both the front and back doors of the plane for efficiency.

Introduction to Deques

Imagine we want to board (or insert) a passenger from the front door of the plane. To insert items into the front of the deque, we need to implement an `add_first(item)` method. This method should:
 
* Take in one input parameter, `item`, which is the element to add to the front of the deque.
* Append the `item` to the `elements` list. Since the front of our deque is the rightmost side, `item` should become the last item in our list, which means we need to append.
 
The time complexity of this method is *O(1)*, or constant time, since adding `item` to the `elements` list only requires one iteration of executing the method.



Implementing add_first

Imagine we want to board (or insert) a passenger from the rear door of the plane. To insert items into the rear of the deque, we need to implement an `add_last(item)` method. This method should:
 
* Take in one input parameter, `item`, which is the element to add to the rear of the deque.
* Since the rear of our deque is the leftmost side, `item` should become the first item in our list, which means we need to prepend it, or insert it at position 0.
 
The time complexity of this method is *O(1)*, since adding `item` to the `elements` list only requires iteration over one element to execute the method.


Implementing add_last

We can deboard the rear passengers while we deboard the front passengers thanks to the flexibility of the deque structure. When we remove a passenger from the rear door of the plane, we must remove them from the rear of the deque. To remove an item from the rear of the deque, we need to use a `remove_last()` method to do so. The removed item will be returned by this method, allowing us to use the popped item elsewhere in the code.

The `remove_last()` method should:

* Pop the last (or leftmost at index 0) item from the `elements` list.
* Return the popped item at the end of the method.

The time complexity of this method is *O(1)*, constant time, since only one iteration of executing the method is needed to remove and return the last `item` from the `elements` list.

Implementing remove_last

The flight has landed, and it's time to deboard the passengers. When we remove a passenger from the front door of the plane, we must remove them from the front of the deque. To remove an item from the front of the deque, we need to use a `remove_first()` method to do so. This method will return the removed item, allowing us to use the popped item elsewhere in the code.

The `remove_first()` method should:

* Pop the first (or rightmost) item from the `elements` list.
* Return the popped item at the end of the method.

The time complexity of this method is *O(1)*, constant time, since the Python method `pop()` has a runtime of *O(1)*.
