Stack

In this lesson, we are going to consider the stack data structure and its implementation in Python.

In subsequent lessons, we’ll provide specific problems where a stack is particularly useful. We’ll be using the implementation that we develop in this lesson to solve those problems.

What is a stack? #

First of all, let me describe what a stack is. Based on the name, it should be a relatively familiar concept.

Let’s assume that we have four books with the following riveting titles:

• A
• B
• C
• D

At the moment, these books are strewn out all over the floor and we want to stack them up neatly.

Now we have a nice neat stack of books! If we want to retrieve a book from this stack, we can take the book on top. Taking a book from the bottom is a bit precarious and we don’t want to topple the entire stack. Therefore, we’ll take down the top book on the stack and read it or do whatever we want to do with it.

Let’s say we want to take Book A. Right now, it is at the bottom of the stack, so we need to take Book D, put it down, then do the same for Book C and Book B, and then we can access Book A.

This is the ...