Building a Dictionary-Based Queue

00:00 Building a Dictionary-Based Queue. A use case where you should consider using an OrderedDict is when you need to implement a dictionary-based queue.

00:10 Queues are common and useful data structures that manage their items in a first-in/first-out manner. This means that you push in new items at the end of the queue, and old items pop out from the beginning of the queue. Typically, queues implement an operation to add an item to their end, which is known as an enqueue operation.

00:31 Queues also implement an operation to remove items from their beginning, which is known as a dequeue operation. To create a dictionary-based queue, create a new Python module called queue.py and add the code seen on-screen to it.

01:03 In Queue, you first initialize an instance attribute called .data. This attribute holds an empty ordered dictionary that you’ll use to store the data. The class initializer takes a first optional argument, initial_data, that allows you to provide initial data when you instantiate the class.

01:25 The initializer also takes optional keyword arguments, kwargs, to allow you to use keyword arguments in the constructor. Then you code .enqueue(), which allows you to add key-value pairs to the queue.

01:43 In this case, you use .move_to_end() if the key already exists, and you use a normal assignment for new keys. Note that for this method to work, you need to provide a two-item tuple or list with a valid key-value pair.

01:59 The .dequeue() implementation uses .popitem() with last set to False to remove and return items from the beginning of data. In this case, you use a try … except block to handle the KeyError that occurs when you call .popitem() on an empty dictionary.

02:16 The special method .__len__() provides the required functionality for retrieving the length of the internal ordered dictionary, .data. Finally, the special method .__repr__() provides a user-friendly string representation of the queue when you print the data structure to the screen.

02:36 On-screen, you can see some examples of Queue in action. First, you create three different Queue objects using different approaches.

03:11 Then you use .enqueue() to add a single item to the end of numbers_queue.

03:23 Finally, you call .dequeue() several times to remove all the items from numbers_queue.

03:37 Note that the final call to .dequeue() prints a message to the screen to inform you that the queue is already empty. In the next section of the course, you’ll take a look back at what you’ve learned.