Building Efficient Queues With Deque

00:00 In this lesson, you’re going to learn how to implement a queue using a deque. Queues are collections of items. You can modify queues by adding items at one end and removing items from the opposite end.

00:12 When people say queue, they usually mean a First-In/First-Out queue, but other variants exist as well. Last-In/First-Out queues remove the most recently added item first, and priority queues remove items by priority rather than insertion order. This lesson focuses on the standard First-In/First-Out queue. They work as a pipe where you push in new items at one end of the pipe and pop old items out from the other end.

00:40 Adding an item to one end of the queue is known as an .enqueue() operation, and removing an item from the other end is called .dequeue().

00:50 When it comes to implementing queues, you could create your own abstract data type as you’ll learn in this lesson, or you could use the queue module from the standard library.

01:00 In general, you should use the high-level abstraction over deque unless you’re implementing your own data structure.

01:09 To better understand how queues work, think of your favorite restaurant. The restaurant has a queue of people waiting for a table to order their food. The last person to arrive will stand at the end of the queue. The person at the beginning of the queue will leave it as soon as a table is available.

01:26 Now let’s emulate that process using a bare-bones deque object. We could simulate people arriving as an .enqueue() operation, so you could use .append() from the deque for that, which adds an individual item into the right end.

01:44 For instance, we have people arriving, first Jane, then John, and now Linda. If we look at the customers, we have them in the right order in which they arrived.

01:55 And now we can simulate people getting tables as a .dequeue() operation, and we could use the .popleft() for that, which removes and returns the item at the left end of the queue.

02:07 So first Jane gets her table, then John, and lastly Linda. Now at this point, there are no people in the queue, so if we do .popleft() again, we will get an error that we cannot do that because the deque is empty.

02:25 So now the queue simulation works. However, deque is a generalization of a queue. That means its API doesn’t match the typical queue API. For example, instead of .enqueue(), you have .append(), and also you have .popleft() instead of .dequeue(). And deque provides several other operations that might not fit your specific use case for a queue.

02:49 That’s why it’s a good idea to create a custom Queue class with the exact functionality you need. Let’s create a custom queue that provides only the following features.

03:00 Enqueuing items, dequeuing items, returning the length of the queue,

03:06 supporting membership tests, supporting normal and reversed iteration, and providing a user-friendly string representation. You can write a Queue class where you’ll internally use a deque to store the data and provide a desired functionality in your custom queue.

03:24 _items holds a deque object. Your custom Queue class implements .enqueue() using deque .append() to add items to the end of the queue.

03:34 And it also implements .dequeue() using deque .popleft() to efficiently remove items from the beginning of the queue, making sure that you hide the implementation details so that the error that is raised is about the queue and not about the deque.

03:51 You’ll also need to implement these special methods to allow your custom class to behave like a built-in Python collection. __len__ defines what should be returned when len() is called on the object.

04:03 __contains__ defines how membership tests using the in operator work. __iter__ returns an iterator, allowing the object to be used in a for loop.

04:14 __reversed__ defines how the object should be traversed when reversed() is called. And __repr__ returns a string representation of the object, which is useful for debugging and display.

04:26 In your Queue class, you don’t have to implement these special methods from scratch. Instead, you delegate them to the deque stored in self._items.

04:37 Now you can use your Queue class in your code. First, you import the Queue class you just created. And then you can create an empty queue.

04:49 When the queue is displayed, Python automatically calls __repr__ to obtain a string representation of the object. Then you can add some items to the queue.

05:05 And now, the queue contains four elements. You can check the length of the queue because you implemented the __len__. And you can also check whether an item exists in the queue because you implemented __contains__.

05:22 Also, if it’s not in a queue. And you can also iterate over the queue thanks to having implemented __iter__.

05:35 In the next lesson, you’ll explore three powerful deque features: maxlen for bounded queues,

05:42 .rotate() for circular shifts, and .extendleft() for efficiently adding multiple items to the front of a deque.