From the course: Python Data Structures and Algorithms

Understand the stack data structure - Python Tutorial

From the course: Python Data Structures and Algorithms

Start my 1-month free trial

Understand the stack data structure

“

- [Instructor] Stacks are a very important data structure in programming and computer science. Think of a stack of plates. The top plate is the only easy access point, whether you want to add a new plate or remove an existing one. A stack is a data structure in which all insertions and deletions are made at one end called the top of the stack. The stack is a LIFO data structure that's last in first out, and it's well worth remembering this acronym. So the last element to be added is the first element to be removed. And we have some common stack operations, which are push, which is adding an item to the top of the stack. Pop, which is removing an item. Peak is when we want to see what's on the top of the stack where we don't want to remove it. And also it's very useful to have a method for checking if the stack is empty. So on this slide, we have a visual representation. It's worth noting that sometimes even though we call it the top of the stack, depending on the implementation, it may turn out to be the left-hand side or the right-hand side. So the word top doesn't necessarily mean vertically out the top. And finally, we have some applications of the stack. Now this is just a small selection, just to give you a flavor. So inside of computers, we use reverse Polish notation for evaluating arithmetic expressions. Stacks are used for syntax parsing. And in a CPU, there's a thing called a cold stack, which holds frames containing all of our local variables for each function code that we make. And that becomes particularly relevant with recursion, which we're not going to go into much in this course, but it's good to be aware of it, that's one common use of a stack inside of a computer. Also things like undo and redo operations in a word processor. And when you get into low-level and assembly programming, you're going to be making a lot of use of a stack if you go down that road as well. So this just gives you a flavor of some of the applications. Okay, so that's the concept of a stack. It's actually a very, very simple concept with a lot of surprisingly powerful applications. In the next video, we'll have a look at how to implement it in Python.

Contents