Stacks and Lists

00:00 In the previous lesson, I gave an overview of the course. In this lesson, I will be introducing you to stacks in Python. A stack is a data structure that holds whatever you put into it.

00:12 What defines a stack is the way the stuff inside is accessed. Stacks support LIFO, or Last-In/First-Out, semantics. This means that the last thing you put in is the first thing available to be taken out. Consider a pile of trays in a lunchroom.

00:29 A new item—in this case, a tray—is put on top of the stack. This is called a push. I haven’t seen one in years but in olden times, the stack of trays often sat on top of a big spring so that no matter how many trays were in the stack, the top-most tray in the pile was level with the counter.

00:46 Putting a new tray on the stack is pushing this spring down one by one. Taking an item off the stack isn’t called a pull, but a pop. You are popping the tray on top of the spring-loaded pile off.

01:00 Due to the nature of the pile, you can’t randomly access an element in the stack. Push and pop are the only two options. Consider the following example. I’m going to push 24 onto the stack, then push 35,

01:19 then 88. Now if I want something in the stack, I have to pop an item out. When I pop, I get 88. If I push something new, it goes on top, burying the 35. Popping the stack results in 13 coming out.

01:44 Stacks tend to be performant. A good implementation will do pushes and pops in O(1) (order 1) time. Stacks are commonly used for language parsing, depth-first searches of tree type data structures, and execution call stacks.

02:01 The built-in list type supports both push and pop operations. This course is the third in three parts. As discussed in the first part of this course, lists are actually implemented as dynamic array structures.

02:14 This means that they have direct access. Unlike their name implies, they’re not a linked list. Python lists resize as needed when inserting a new item means they need more space.

02:26 When using a list as a stack, the push and pop operations are O(1), except when Python decides the list needs new memory allocation—then it’s a bit slower. When Python allocates space for a list, it oversizes. Not every insert is going to require new memory allocation, meaning not every push is more expensive than O(1).

02:48 Although stack operations are normally called push and pop, because the list is more than a stack, it deviates from this terminology. When using a list as a stack, you want to use the .append() method for the push operation and the .pop() method for a pop. If you stick with these two operations, you will have a performant stack.

03:06 If you mix in the use of .insert(), one, you’re potentially violating the strict LIFO sense of a stack, and two, you’re not going to stay in the O(1) performance range.

03:20 Let’s look at using a list as a stack in practice. I’ll use the .append() method as a push,

03:29 then push some more,

03:33 and one more time,

03:37 and now I can examine the list. You can see that the list is ordered in the way items were pushed inside.

03:46 Calling .pop() pulls the last item off the list, the last thing pushed on, and returns it—in this case, 'code'. Once again looking at the list, and you see 'eat' and 'sleep' are what are left.

04:01 Pop some more, and again, and one more time. And this is what happens if you pop an empty list.

04:15 And that is how a list can be a stack. Next up, I’ll show you how a queue can also be a stack.