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:
>>> 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.
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.
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".
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".
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.
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
.append() will append to the right, and actually, it tells us Add an element to the right side of the deque.
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.
Become a Member to join the conversation.