Implementing a Stack in Python

Key Takeaways

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 so the three different implementations that I'm going to cover in this course are list collections deck and qfo Q and in this video I'm gonna go through in the terminal and run you through how to use lists and collections deck we'll talk about life oq in the next video so the first and simplest way to implement a stack in Python is to just use a list so I'll say stack equals just an empty list and list has inbuilt functions which are essentially the same as push and pop and the first of these is append and so you can append one it's to append two and to append three and you can take a look so 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 so stacked up pop and indeed it returns 3 to 1 and then again you get an error when you pop from an empty list 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 a list needs to support indexing so for example if I say for I and range 10 and then I add them all to my stack stacked on append I then I'll have a stack with these four 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 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 entry and sometimes that can be a little slower so a faster implementation is collections deck and so you have to import that from the collections module and then we can just say stack equals deck and this has essentially exactly the same the same usage as the list implementation so you say stacked on a pen and then stacked up pop and deck also has a pop left and you can use that to implement a queue but that's for another video series so you can just do stacked up pop and you can see has exactly the same behavior and then it just says pop from an empty deck when you try to pop from an empty deck exactly so again I'll just do to show you real quick and you can take a look at your stack and it's a deck with this information and again nine will be on the top so you can do the same thing the same little trick here and you say while stack stack dot pop or I'll say print stack top and again there popped in last in first out order so those are two really simple and easy ways to implement a stack in Python deck is a little bit faster but then again it doesn't offer the same indexing capability that the list implementation does or at least the indexing isn't quite as fast because the deck is implanted under the hood as a doubly linked list which gives it faster adding performance you can append elements faster and then a list is implemented as a resizable array under the hood if you're interested in things like that so it takes sometimes can take a little bit more time to add entries to the end of a list so if you really need pure speed deck is probably the better way to go