Stacks and Lists
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.
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
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.
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: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).
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.
Become a Member to join the conversation.