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
Trueif the deque is empty and
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.
Take a look at the provided Deque class code. This lesson will walk through implementing each of the deque operations or methods.
As shown in the gif, we will implement a deque such that we can insert and remove elements in the front and back of the data structure.
Click Up Nextto get started!