How to Implement Python Stack Data Structure?

What is Stack?

A Stack is a linear data structure which organizes its elements in sequential or linear order. It follows the LIFO(Last In, First Out) principle, which means the element inserted at last in the data structure would be the first one to move out. Undo (ctrl+z) is a real-life example of the stack implementation, in which the last edit gets removed.

Basic Stack Operations

Every data structure has some basic operations or methods that can manipulate and display data structure elements. Similarly, the stack has some of its own operations.

• Push
• pop
• is_empty

Push: Push operation is used to push or insert the element at the top of the stack.

Pop: The pop operation is used to remove or pop out the last inserted element.

is_empty: The is_empty operation is used to check if the stack contains any element or not.

<Note>: Push and pop are the two major operations of stack data structure.

Python Stack Implementation

In Python, there are various techniques we can follow to implement a stack data structure . But here we have mentioned only two major methods.

• Python list
• collections library

How to Implement a stack using class and List

The stack is a very simple data structure, and the Python list is very close to it. Using the Python list data structure, we can implement a Stack.

Example

class Stack:
    def __init__(self):
        self.s = []

    def push(self,item):
        self.s.append(item)
        print(item, "has been inserted to stack")

    def pop(self):
        p = self.s.pop()
        print("item",p, "has been removed from stack")

    def is_empty(self):
        if len(self.s)==0:
            print("YES, stack is empty")
        else:
            print("NO, there are", len(self.s), "items present in stack")

# initialize the stack object s1
s1 = Stack()
#check if stack is empty
s1.is_empty()

# push element in stack
s1.push(10)
s1.push(20)
s1.is_empty()

# pop last element from the stack
s1.pop()

Output

YES, stack is empty
10 has been inserted to stack
20 has been inserted to stack
NO, there are 2 items present in stack
item 20 has been removed from stack
NO, there are 1 items present in stack

How to Implement stack using Python collections library

Python has an in-built library called Collections which has deque class. deque can also use to implement a stack data structure. deque is faster than Python list that's why it preferred over list for the implementation of a stack.

Example

from collections import deque

class Stack:
    def __init__(self):
        # initializing deque() object
        self.s = deque()

    def push(self,item):
        self.s.append(item)
        print(item, "has been inserted to stack")

    def pop(self):
        p = self.s.pop()
        print("item",p, "has been removed from stack")

    def is_empty(self):
        if len(self.s)==0:
            print("YES, stack is empty")
        else:
            print("NO, there are", len(self.s), "items present in stack")

# initialize the stack object s1
s1 = Stack()
#check if stack is empty
s1.is_empty()

# push element in stack
s1.push(10)
s1.push(20)
s1.is_empty()

# pop last element from the stack
s1.pop()
s1.is_empty()

Output

YES, stack is empty
10 has been inserted to stack
20 has been inserted to stack
NO, there are 2 items present in stack
item 20 has been removed from stack
NO, there are 1 items present in stack

Summary

• Stack stores elements in linear order.
• In Python, we can use a list or collections library deque() module to implement a stack.
• Deque () module is faster than a list.
• deque() has a time complexity of O(1) for push and pop operations.

People are also reading:

• Remove Duplicates from a Python List
• How to check the size of a file using Python?
• Find all Files in a Directory in Python
• Del, Remove and Pop on Python Lists
• Port Vulnerability Scanner in Python
• Python Remove Empty String from a List of Strings
• What is CherryPy Python?
• What is Flask?
• Python Pyramid Framework
• Bottle Framework in Python