Implementing a Stack in Python

00:00 So, how do you go about actually implementing a stack in Python? Well, that’s what I’m going to cover in this lesson. And luckily, there are some great implementations that exist in Python already without you having to do any hard work to make them have this Last-In/First-Out performance that you would want them to have if you wanted a stack data structure.

00:21 So, the three different implementations that I’m going to cover in this course are list, collections.deque, and queue.LifoQueue.

00:30 And in this video, I’m going to go through in the terminal and run you through how to use list and collections.deque. We’ll talk about LifoQueue in the next video.

00:40 So, the first and simplest way to implement a stack in Python is to just use a list. I’ll say stack equals just an empty list. And list has in-built functions which are essentially the same as .push() and .pop().

00:58 And the first of these is .append(). You can .append(1), let’s do .append(2), and let’s just do .append(3).

01:07 And you can take a look. You have a stack, and this is just the order that they were put in [1, 2, 3]. But the 3, as you’ll know from the Last-In/First-Out ordering, will be the first thing to get popped.

01:19 So, stack.pop() and indeed it returns 3, 2, 1. And then, again, you get an error when you pop from an empty list.

01:27 So this is really, really simple and it works really quite well in most cases. But it’s not the fastest possible implementation because under the hood

01:38 a list needs to support indexing. So for example, if I say for i in range(10): and then I add them all to my stack, stack.append(i), then I’ll have a stack with these different elements, but I can get access to those elements really easily just by doing something like this. And this takes very little time, this operation.

01:59 But it does take a little extra overhead to support operations like these on a list. And that manifests itself when sometimes you have to resize the amount of memory that’s taken up by a list in order to accommodate new entries.

02:14 And sometimes that can be a little slower. So, a faster implementation is collections.deque. You have to import that from the collections module, and then we can just say stack = deque().

02:28 And this has essentially exactly the same usage as the list implementation. So you say stack.append() and then stack.pop().

02:40 And deque also has a .popleft(), and you can use that to implement a queue, but that’s for another video series. So, you can just do stack.pop() and you can see it has exactly the same behavior.

02:53 And then it just says pop from an empty deque when you try to pop from an empty deque—exactly. So, again, I’ll just do this to show you real quick.

03:07 And you can take a look at your stack and it’s a deque with this information. And again, 9 will be on the top. You can do the same thing, the same little trick here, and you say while stack:

03:18 stack.pop(). Or I’ll say print(stack.pop()).

03:24 And again, they’re popped in Last-In/First-Out order. So. Those are two really simple and easy ways to implement a stack in Python. deque is a little bit faster, but then again, it doesn’t offer the same indexing capability that the list implementation does.

03:41 Or at least, the indexing isn’t quite as fast because a deque is implemented under the hood as a doubly-linked list, which gives it faster adding performance—you can append elements faster.

03:52 And then a list is implemented as a resizable array under the hood, if you’re interested in things like that, so sometimes it can take a little bit more time to add entries to the end of a list.

04:03 So if you really need pure speed, deque is probably the better way to go.