Learn the implementation of commonly used algorithms and data structures to write programs for real-world problems.

Zero to Hero in Python

This module provides a comprehensive description of the most common data structures and algorithms that we'll see in interviews and our everyday work. The module extensively covers implementation details, together with thorough explanations and hands-on coding exercises. By the end of this module, we'll have the confidence to solve various problems, no matter their complexity.

Data Structures in Python

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 main idea of a stack. The data structure stack is very similar to a physical stack that you'd most likely be familiar with. The stack data structure allows us to place any programming artifact, variable or object on it, just as our example stack allowed us to put books in it.

# Stack Operations

## `Push`

The operation to insert elements in a stack is called **push**. When we *push* the book on a stack, we put the book on the previous *top* element which means that the new book becomes the *top* element. This is what we mean when we use the *push* operation, we *push* elements onto a stack. We insert elements onto a stack and the last element to be pushed is the new *top* of the stack.

## `Pop`

There is another operation that we can perform on the stack, popping. Popping is when we take the top book of the stack and put it down. This implies that when we remove an element from the stack, the stack follows the *First-In, Last Out* property. This means that the top element, the last to be inserted, is removed when we perform the pop operation. 

`Push` and `Pop` are two fundamental routines that we'll need for this data structure.  

## `Peek`
Another thing that we can do is view the top element of the stack so we can
ask the data structure: "What's the top
element?" and it can give that to us using the *peek* operation. Note that the *peek* operation does not remove the *top* element, it merely returns it. 

We can also check whether or not the
stack is empty, and a few other things
too, that will come along the way
as we implement it. 

Now I'm going to create a stack class, and the constructor of the class is going to initialize a Python list. The Python list has a lot of things that we're after, and it's going to make it
easier for us to tweak Python's
implementation of the list to be adapted
to what we would expect to see in a
stack, namely, push/pop.  

This lesson will introduce you to the stack data structure and its implementation in Python which we'll use in the problems throughout this chapter. 