collections.deque

Python Coding Interviews: Tips & Best Practices James Uejio 03:48

In this lesson, you’ll use the collections.deque data structure to create a ticketing queue. Deques allow for appending to both left and right and popping from both left and right in constant time. Here’s an example:

Python
      
        
      
    
>>> from collections import deque
>>> deq = deque([1, 2, 3])
>>> deq.appendleft(5)
>>> deq.append(6)
>>> deq
deque([5, 1, 2, 3, 6])
>>> deq.popleft()
5
>>> deq.pop()
6
>>> deq
deque([1, 2, 3])

You can read more about deque in the documentation for the Python collections module.

00:00 Let’s move on to the deque data structure, otherwise known as the “DQ” or double-ended queue. So, like always, I’ll show you a solution to a problem not using a deque and then show you the solution using one.

00:13 Here we have the class TicketQueue, which will behave like any ticket queue in the real world, where you can add people to the queue, service people, and potentially bypass the queue. Here’s our .add_person() method, which will add the person to the queue, queue = TicketQueue(), queue.add_person("Jack"), and then it will print out the string, "Jack has been added to the queue".

00:33 Then, you want to service the person at the front of the queue. Here, we have a queue, we add "Jack", and then queue.service_person(), and then it will remove "Jack" from the queue and print out "Jack has been serviced". And then bypassing the queue—let’s just say you’re VIP, or you have a question and you just need to bypass the queue—queue = TicketQueue() queue.add_person("Jack"), and then queue.bypass_queue("Jill"), and it will print out "Jill has bypassed the queue".

00:56 Let’s solve this using a list. self.lst = [], and then .add_person() is simply just self.lst.append(name), and then print().

01:05 I will be using f-string, which you learned about in a couple of videos ago. f"{name} has been added to the queue". I’m just going to stretch this a little bit.

01:16 Cool. And then servicing—name = self.lst.pop(0). So, this is going to remove the first person from the list, and then return that name—print(f"{name} has been serviced").

01:29 Then down here, bypass the queue—you might do something like self.lst = [name] + self.lst.

01:38 Or, you might do something like this: self.lst.insert(0, name). print(f"{name} has bypassed the queue"). Let’s clear, run the doctests for this file,

01:58 and everything passed. Cool! So, looking at the runtime, .add_person() is constant time, .service_person() is actually still constant time because popping off the first element of a list—internally, you can just move that pointer, and so you don’t actually have to shift any values around.

02:12 So this is constant. .bypass_queue(), however, is not. No matter which method we use,

02:19 you will have to shift over all the elements in the list. So either you’re creating a new list by adding [name], which will copy over all these values, or .insert() will shift them over.

02:29 So, this method is going to run O(n) time, where n is the length of our list. This is where a deque comes in handy. With deque, you can .append() and .pop() on both sides in constant time.

02:40 So, let’s import our deque,

02:44 change this to .deque just to make it clearer, and then you make a new deque() like this. You can pass in an iterable here, and it will convert that iterable to a deque—but we’re going to actually start with an empty deque. .add_person()—self.deque.append(). So, .append() will append to the right, and actually, it tells us Add an element to the right side of the deque. .service_person()—.lst.pop().

03:06 So, what we really want is actually to pop the left side of the deque, which will be self.popleft().

03:15 And then here, you need to insert the value at the left side of the deque. Instead of this, you do self.deque.appendleft(name).

03:27 Save, run, and it passes. So, this is another data structure that you can have in your pocket, which will help you solve any problem where you need to append to both sides, or pop from both sides, or both.

03:40 I’ll also link some more documentation down below. In the next video, you’ll learn about namedtuples.

Max on April 24, 2020

Hey James, thanks for this outstanding series, it’s actually way more than a help for an interview - it’s an overview of a lot of cool tips and tricks.

However, in this example I think that running the doctest with these expected outputs doesn’t quite cut it, especially for add_person and bypass_queue. If I understand that correctly, the return string of those methods is only based on the input name, not on what happens to the list/deque. Maybe checking for the actual state of the deque could provide a better solution? But maybe I’m just a bit nitpicky here…

Whatever, the series is great, learned a lot of things I can expand on now.

Best, Max

Piotr on April 26, 2020

The python docs for deque seem to say that .pop(0) is O(n)?

James Uejio RP Team on April 26, 2020

@Max thank you for the kind words. Yes that is totally true and the test cases should have been more thorough. I think a good way to test it would be to check the state of the deque or add multiple people and check that servicing works. For example:

for i in range(5):
    queue.add_person(i)

for i in range(5):
    queue.service_person()

Or something like that.

@Piotr good question, so the actual paragraph says: “Though list objects support similar operations, they are optimized for fast fixed-length operations and incur O(n) memory movement costs for pop(0) and insert(0, v) operations which change both the size and position of the underlying data representation.” So it is talking about list objects ([]) and those take O(n) to pop from the front.

James Uejio RP Team on April 27, 2020

Here is the Python documentation on deque: Python collections module

alizjonizm on June 12, 2021

Is it necessary to write “object” when creating a class TicketQueue(object):? Is there a difference if I write just class TicketQueue:?

Bartosz Zaczyński RP Team on June 13, 2021

@alizjonizm Extending the object was mandatory prior to Python 3. Nowadays, this syntax is considered obsolete.

lltw on Aug. 10, 2021

Hello @James Uejio!

While I really like your lessons, there is one thing that confuses me in this particular lesson: at around ~2:04, you said:

“.service_person() is actually still constant time because popping off the first element of a list - internally, you can just move that pointer, and so you don’t actually have to shift any values around.”

I cannot find anywhere in the documentation, that .pop(0) is ~ O(1), and sources that I found states that, that it is ~ O(n) (eg. here wiki.python.org/moin/TimeComplexity). My C skill is not sufficient to understand the time complexity of this operation by looking at the source code of Python list implementation. Can you provide me with a resource that explains how Python list is actually implemented and why exactly .pop(0) is constant time?

Become a Member to join the conversation.