Prerequisites

In order to understand this stack tutorial, you'll need to learn the Stack data structure which requires the following:

1. Python 3
2. Basic data structure concepts like List (Click here to refresh List concepts)
3. OOP concepts

What is a Stack?

Howdy! If you are reading this article, you are about to learn one of the very basic and most useful data structure concepts. If you know other languages like C or C++, implementation of stack might be tricky (since you will have to keep track of pointers!) but not with Python. Python is so amazing that you can use lists to easily implement them but you will also learn how to implement using pointers to adopt a language agnostic way. But first, let’s understand what they are. If you are already familiar with this, you can skip to the implementation section.

When you hear the word Stack, the first thing that comes to your mind may be a stack of books, and we can use this analogy to explain stacks easily! Some of the commonalities include:

1. There is a book at the top of the stack (if there is only one book in the stack, then that will be considered the topmost book).
2. Only when you remove the topmost book can you get access to the bottom ones. No Jenga games here! (Also assume that you can only lift one book at a time).
3. Once you remove all the books from the top one by one, there will be none left and hence you cannot remove any more books.

Check out this fun game called Towers of Hanoi which beautifully demonstrates how a Stack works. Read the instructions carefully and turn off the music (it is awfully loud!).

To describe the above points programmatically:

1. Keep track of the topmost element as this will give you the information about the number of elements in the stack and whether the stack is empty/full (if the stack is empty then top will be set to 0 or a negative number)
2. The last element to enter the stack will always be the first to leave (Last In First Out - LIFO)
3. If all the elements are removed, then the stack is empty and if you try to remove elements from an empty stack, a warning or an error message is thrown.
4. If the stack has reached its maximum limit and you try to add more elements, a warning or error message is thrown.

Things to remember:

1. The entry and exit of elements happens only from one end of the stack (top)
2. Push - Adding an element to the Stack
3. Pop - Removing an element from the Stack
4. Random access is not allowed - you cannot add or remove an element from the middle.

Note: Always keep track of the Top. This tells us the status of the stack.

How to implement Stack?

Now that you know what a Stack is, let's get started with the implementation!

Stack implementation using List

Here we are going to define a class Stack and add methods to perform the below operations:

1. Push elements into a Stack
2. Pop elements from a Stack and issue a warning if it’s empty
3. Get the size of the Stack
4. Print all the elements of the Stack

class Stack:

    #Constructor creates a list
    def __init__(self):
        self.stack = list()

    #Adding elements to stack
    def push(self,data):
        #Checking to avoid duplicate entries
        if data not in self.stack:
            self.stack.append(data)
            return True
        return False

    #Removing last element from the stack
    def pop(self):
        if len(self.stack)<=0:
            return ("Stack Empty!")
        return self.stack.pop()
        
    #Getting the size of the stack
    def size(self):
        return len(self.stack)

myStack = Stack()
print(myStack.push(5)) #prints True
print(myStack.push(6)) #prints True
print(myStack.push(9)) #prints True
print(myStack.push(5)) #prints False since 5 is there
print(myStack.push(3)) #prints True
print(myStack.size())  #prints 4 
print(myStack.pop())   #prints 3
print(myStack.pop())   #prints 9
print(myStack.pop())   #prints 6
print(myStack.pop())   #prints 5
print(myStack.size())  #prints 0
print(myStack.pop())   #prints Stack Empty!

NOTE: We are not worried about the size of the stack since it is represented by a list which can dynamically change its size.

Stack implementation using Array

Python Lists have made it so easy to implement Stack. However, if you want to implement Stack language agnostically, you have to assume that lists are like arrays (fixed in size) and use a Top pointer to keep a tab on the status of the stack. Check this animation to understand how it works.

Algorithm

1. Declare a list and an integer MaxSize, denoting the maximum size of the Stack
2. Top is initially set to 0
3. Push operation:
   1. Check if Top is less than the MaxSize of the Stack
      1. If yes, append data to stack and increment top by 1
      2. If no, print stack full message
4. Pop operation:
   1. Check if Top is greater than 0:
      1. If yes, pop the last element from the list and decrement top by 1
      2. If no, print stack empty message
5. Size operation:
   1. The value of the Top pointer is the size of the Stack

Program

class Stack:
    
    #Constructor 
    def __init__(self):
        self.stack = list()
        self.maxSize = 8
        self.top = 0
    
    #Adds element to the Stack
    def push(self,data):
        if self.top>=self.maxSize:
            return ("Stack Full!")
        self.stack.append(data)
        self.top += 1
        return True
        
    #Removes element from the stack
    def pop(self):
        if self.top<=0:
            return ("Stack Empty!")
        item = self.stack.pop()
        self.top -= 1
        return item
        
    #Size of the stack
    def size(self):
        return self.top

s = Stack()
print(s.push(1))#prints True
print(s.push(2))#prints True
print(s.push(3))#prints True
print(s.push(4))#prints True
print(s.push(5))#prints True
print(s.push(6))#prints True
print(s.push(7))#prints True
print(s.push(8))#prints True
print(s.push(9))#prints Stack Full!
print(s.size())#prints 8        
print(s.pop())#prints 8
print(s.pop())#prints 7
print(s.pop())#prints 6
print(s.pop())#prints 5
print(s.pop())#prints 4
print(s.pop())#prints 3
print(s.pop())#prints 2
print(s.pop())#prints 1
print(s.pop())#prints Stack Empty!

Note: Element 9 was not added and hence size remains 8.

Apart from the methods described above, you can add methods to return the top element, check if the stack is empty etc.

Conclusion

One of the main application of Stacks is in recursion. Be sure to check this tutorial to know what recursion is.  Once you are familiar with this concept, try to solve these puzzles using recursion - sentence reversal and balancing brackets. Happy Pythoning!