How to Implement Python Stack Data Structure?

Posted in

How to Implement Python Stack Data Structure?
vinaykhatri

Vinay Khatri
Last updated on May 22, 2024

    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:

    Leave a Comment on this Post

    0 Comments