**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 -

- What is a Stack
- What are the operations that can be performed on a stack
- How to implement a Stack using Python
- 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 — **L**ast **I**n **F**irst **O**ut, also known as a LIFO Data Structure. Real examples of a stack are -

- Pile of plates in your favorite restaurant
- 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

**operation is carried out and 3 is removed.**

*pop*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 -

**push()**— Inserts data on the stack**pop()**— Removes data from the stack**top()**— Returns the last inserted data without actually removing it**size()**— Returns the size of a stack**isEmpty()**— Returns true if stack is empty**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 -

- Using List
- 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 —

**. Similarly, if a stack is full and we try to add more items to it,**

*Error:: Stack is Empty!***, an error will be thrown.**

*Error:: Stack is Full!*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,

**operation on a list will take longer as well.**

*.insert()*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

**module. This is the simplest way you can implement a stack in python. Let us see it in the code below -**

*collections*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 -

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

# More About The Author

I am a full-time software engineer with 4+ years of experience in Python, AWS, and many more technologies. I have started writing recently as it helps me to read more. I am looking forward to sharing technical knowledge and my life experiences with people out there.

- Github — https://github.com/varun-singh-01
- LinkedIn — https://www.linkedin.com/in/varun-singh-a02b2b118/
- Twitter — https://twitter.com/varunsh89
*Follow for more interesting articles —**T*alkHash