Join us and get access to thousands of tutorials and a community of expert Pythonistas.
This lesson is for members only.Join us and get access to thousands of tutorials and a community of expert Pythonistas.
Implementing a Stack in Python
In this lesson, you’ll see how toimplement astack in Python. There are some great implementations that exist already, so you don’t have to do all the hard work! You’ll start by learning aboutlist andcollections.deque. In the next lesson, you’ll look atqueue.LifoQueue.
00:00So, 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 alreadywithout you having to do any hard work to make them have this Last-In/First-Outperformance that you would want them to have if you wanted a stack datastructure.
00:21So, the three different implementations that I’m going to cover in this coursearelist,collections.deque, andqueue.LifoQueue.
00:30And in this video,I’m going to go through in the terminal and run you through how to uselist andcollections.deque. We’ll talk aboutLifoQueue in the next video.
00:40So, the first and simplest way to implement a stack in Python is to just use alist.I’ll saystack equals just an empty list. Andlist has in-built functionswhich are essentially the same as.push() and.pop().
00:58And the first of these is.append(). You can.append(1),let’s do.append(2), and let’s just do.append(3).
01:07And you can take a look. You have a stack,and this is just the order that they were put in[1, 2, 3].But the3, as you’ll knowfrom the Last-In/First-Out ordering, will be the first thing to get popped.
01:19So,stack.pop() and indeed it returns3,2,1.And then, again, you get an error when you pop from an empty list.
01:27So this is really, really simple andit works really quite well in most cases.But it’s not the fastest possible implementation because under the hood
01:38alist needs to support indexing. So for example,if I sayfor i in range(10): and then I add them all to mystack,stack.append(i), then I’ll havea stack with these different elements,but I can get access to those elements really easily just by doing somethinglike this. And this takes very little time, this operation.
01:59But it does take a little extra overhead to support operations like these on alist.And that manifests itself when sometimes you have to resize the amount of memorythat’s taken up by a list in order to accommodate new entries.
02:14And sometimes that can be a little slower.So, a faster implementation iscollections.deque.You have to import that from thecollections module,and then we can just saystack = deque().
02:28And this has essentially exactly the same usage as thelist implementation.So you saystack.append() and thenstack.pop().
02:40Anddeque also has a.popleft(), and you can use that to implement a queue,but that’s for another video series.So, you can just dostack.pop() and you can see it has exactly the same behavior.
02:53And then it just sayspop from an empty deque when you try to pop from an emptydeque—exactly. So, again, I’ll just do this to show you real quick.
03:07And you can take a look at yourstack and it’s adeque with this information.And again,9 will be on the top. You can do the same thing,the same little trick here, and you saywhile stack:
03:18stack.pop(). Or I’ll sayprint(stack.pop()).
03:24And 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 thelist implementation does.
03:41Or at least, the indexing isn’t quite as fast because adeque is implementedunder the hood as a doubly-linked list,which gives it faster adding performance—you can append elements faster.
03:52And then alist 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 endof alist.
04:03So if you really need pure speed,deque is probably the better way to go.
Course Contents
