Implementing Stack In Python

Software Developers often struggle to implement even the simplest data structures in practical use cases — I was one of them. Stack is one of those data structures.

Have you ever wondered — What exactly is the stack used for? What is the optimal implementation of stack?. Well, you have come to the right place. In this tutorial, you will learn -

1. What is a Stack
2. What are the operations that can be performed on a stack
3. How to implement a Stack using Python
4. How to determine the areas where stack data structure can be used

Let’s begin with a general definition of Stack Data Structure

What Is A Stack In Data Structures?

Just like any other data structure, a Stack is used for storing data with the rule — Last In First Out, also known as a LIFO Data Structure. Real examples of a stack are -

1. Pile of plates in your favorite restaurant
2. Pile of plates in my favorite restaurant

Well, technically it is just Pile Of Plates ;).

From the above example, it is understood that — In a Stack order in which items are inserted is important. A new plate will always be kept on the top of the pile, and if needed, will be taken from the top again.

The more technical definition of the stack — Stack is an ordered list in which insertion and removal of items take place at one end, called Top. The last item inserted is always going to be the first one to be removed — hence stack is known as the LIFO data structure.

Let’s understand the insertion and removal of items from a stack below -

The above example shows an empty stack and pushes operations done on the stack. After three push operations, the final content of the stack becomes — 3, 2, 1. Then the pop operation is carried out and 3 is removed.

As mentioned earlier, all the Stack Operations are done on one end called — Top. Let us now see what are the different kinds of operations that can be performed on a Stack -

1. push() — Inserts data on the stack
2. pop() — Removes data from the stack
3. top() — Returns the last inserted data without actually removing it
4. size() — Returns the size of a stack
5. isEmpty() — Returns true if stack is empty
6. isFull() — Returns true if stack is full

Refer to the below image for the time complexity of each operation on a Stack

Implementing Stack

The stack can be implemented in various ways, but we will cover the following ways for implementing a Stack in Python -

1. Using List
2. Using Inbuilt Python Module — Collections

Implementing Stack Using List

We will implement a stack using List with a totally different approach that you will not find anywhere. We will create a class called Stack that will have attributes and functions that can be performed on its object.

Yes, Object-Oriented Programming is the implementation strategy here, as it will give you a keen sense of how exactly to implement stack in production use cases. Here is the code -

In the above class, the stack is initialized as an empty python list. Also, it takes the max_size as one of the additional parameters that will specify the Maximum Size of the Stack.

Stack class consists of all the basic operations that can be performed on a stack, with proper exception handling on the operation level itself. For example -

If a stack is empty and we try to perform a pop() operation, the above implementation will throw an exception saying — Error:: Stack is Empty!. Similarly, if a stack is full and we try to add more items to it, Error:: Stack is Full! , an error will be thrown.

Now let us perform some of these operations on our stack below -

Most software developers use Lists as their primary stack implementation. But there are few problems when your List is your stack.

In a Python List, items are stored in contiguous memory locations, which means if the List grows, the time to add an item at the end of the list will take longer. The list was made for one sole purpose and that was to have constant time when accessing any data within a List.

A stack implemented using a List will take longer to perform .append() operation, as once the list is full, memory allocation will be required. Not only this, .insert() operation on a list will take longer as well.

Now, how do we avoid this problem? Python’s collections module provides a better way to implement the stack. Let us see that implementation below.

Implementing A Stack Inbuilt Python Module — Collections

There are many inbuilt ways to implement a Stack in Python. One of them is using the deque from the collections module. This is the simplest way you can implement a stack in python. Let us see it in the code below -

All the Stack Operations discussed above can be performed on this stack as well. The major difference in this implementation is — collections.deque is internally built by doubly Linked List. Hence every node or item of the stack is a Linked List node that contains the value and the reference to the next node.

Hence, inserting an item to a Stack implemented this way will have constant time as the item will always be inserted on one end. Let us visualize this operation below -

The constant time .append() and .pop() operations make deque an excellent choice for implementing a Python stack if your code doesn’t use threading.

Practical Use Cases Of Stack

Below listed are few practical implementations of Stack -

1. Page visited history on a Web Browser [Back Button]
2. Matching Tags in HTML
3. Infix-to-postfix conversion
4. Function calls are implemented using stack (for recursion)