deque and LifoQueue

00:00 In the previous lesson, I showed you how to use Python’s built-in list as a stack. In this lesson, I will show you how to use the double-ended queue and LIFO queue structures instead. Inside of the collections library, you will find a double-ended queue called deque.

00:17 A double-ended queue is one that supports adding and removing items from either end. Because of this, it can be used either as a stack or a queue. Underneath the covers, deque is implemented as a doubly-linked list.

00:32 It has good performance for insertion and deletion but poor performance on random access. Let’s see it in practice. First off, I need to import it.

00:46 Now I will instantiate a deque. I use .append() to push on an item.

00:56 A little bit of déjà vu, and here’s the resulting queue.

01:03 The .appendleft() method puts something on the other end of the queue. Here’s the result. Notice that this is breaking the idea of a stack.

01:12 We’ve just inserted a lunch tray into the bottom of the pile.

01:17 Just like a list, the .pop() method takes the top item off and returns it. There’s a companion to .appendleft(). It’s .popleft() and it does what .pop() does but from the other end of the queue. Again, not strictly a stack operation.

01:34 Similar to the list in the previous lesson, a deque can be used as a stack, but not strictly so. Debugging code is hard. Debugging multithreaded code is doubly hard.

01:46 Whenever you have multiple threads in a system, there’s a danger of race conditions. At any time, the operating system may decide to stop paying attention to the current thread and schedule a different one. If you’re sharing state between threads, bad things can happen. To resolve this kind of problem, your code needs to be able to declare a section atomic.

02:07 It can do this with a lock. The LifoQueue class found in the queue library is a thread-safe stack. It guarantees that operations on it are atomic and won’t be mangled by the operating system context switching to another thread.

02:24 Consider a program with two threads and a shared LifoQueue object between them. First, I’ll start off with the familiar eating action and then Thread 1 will push it onto the LifoQueue using the .put() method.

02:40 Now, 'eat' is in the LifoQueue. Let’s do that again with eat’s companion 'sleep'.

02:51 So far, so good. Now, Thread 2 can call .get() on the LifoQueue to retrieve the top item off the stack, resulting in it receiving 'sleep'.

03:04 Thread 2 making another call to .get() pops 'eat' off the stack.

03:12 If Thread 2 makes another call to .get(), it blocks as there’s nothing in the stack to pop off. Meanwhile, back in Thread 1—you remember Thread 1, right? It was so long ago—I’ll take the next step, and 'code'. Calling .put() pushes it onto the stack.

03:32 And now the block on Thread 2 is released and it receives our third activity. Alternatively, Thread 2 can also call .get_nowait(), which instead of blocking will raise an exception.

03:47 This allows the thread to check if there’s something in the queue for it, but keeps doing other things if there isn’t anything waiting for it. Let’s open up the REPL and take a look at LifoQueue. First off, I’ll import it from the queue library, then instantiate it.

04:06 Now push on the "eat" action using .put(), again for "sleep", and examining the queue gives you a not-so-helpful output.

04:17 LifoQueue uses the default repr, which makes debugging it a little more difficult. I can use .get() to pop an item off. I can use .get_nowait() to get something else.

04:29 And then one more time, and I get the exception. The Empty exception is raised because there was nothing in the queue. That’s all for using queues as stacks. Next up, I’ll talk about the pros and cons of the different ways of getting stack-like behavior in Python.