Queues With list and deque

00:00 In the previous lesson, I wrapped up the section on stacks. In this lesson, I’ll introduce you to queues in Python. Like a stack, a queue is an ordered container for arbitrary objects.

00:12 The difference is that queues are FIFO: First-In/First-Out. This is like a bank line-up. First person to arrive in the morning is the first person served. Operations on a queue are commonly called enqueue and dequeue.

00:29 Like stacks, queues don’t typically support random access, or if they do, it tends to be an expensive operation, whereas the insert and delete operations on a queue are typically aimed at being O(1). Common uses for queues are scheduling and breadth-first search of a tree-like data structure.

00:51 The built-in list type in Python can be used as a queue by popping items off the front of the list. You can do this by adding an extra parameter to the call to .pop(). The underlying structure of a list is a dynamic array. Lists were implemented this way to optimize for random access, but the cost of this is the first spot in the list must be the first spot in memory.

01:14 Popping an item out of the list from anywhere but the end leaves a hole, which the list then has to deal with. Everything to the right of that hole is moved one position left.

01:25 This is an O(n) operation, n for everything to the right of the hole, which could be the entire list. This doesn’t mean not to use a list as a queue. The cost of O(n) isn’t too bad if n is small. Lists are good enough for small amounts of data.

01:45 Here’s a list. To be consistent, I’ll append the string "eat". Déjà vu all over again, thanks Yogi. Once more, and here it is.

02:01 Getting an item from the front of the list still uses the .pop() method, but this time using an argument of 0. 0 is the index of the element being popped, indicating the first position.

02:13 There you have it! A list as a FIFO queue.

02:17 If you aren’t playing with small amounts of data, a better alternative is to use the deque object in the collections library. The .append() and .popleft() methods act as enqueue and dequeue respectively.

02:30 Use of deque can be seen in the lesson on stacks. I previously mentioned that lists were optimized for random access at the cost of performance.

02:40 Well, deque is optimized for performance at the cost of random access. Choose the right implementation based on your need.

02:50 Next up, I’ll talk about queues when coding with threads and multiprocessing.