Stack in Python

A stack is a derived data structure that is used to store items in a 'Last in First out' or LIFO format. Stacks can be used to store and extract data in the order of their entry into the stack in such a way that the element inserted last is the first element that is extracted.

Stacks are implemented in different programming languages in different ways. They are very important data structures both in terms of utility and comprehensibility of data and program control. And are often used in the internal working of the operating systems.
d100

Operations on stacks

The top variable holds the index of the last inserted value of the stack.

  • push() - it is used to insert elements into the stack at the end (that is after the top element), and the top variable gets updated
  • pop() - it is used to remove the last inserted element into the stack, that is the top variable which also gets updated
  • top() - returns the index of the topmost element of the stack, that is the last inserted element
  • size() - returns the size of the stack
  • empty() - returns whether the stack is empty or not

Stacks in Python using Lists

Stacks in Python can be implemented using the object-oriented feature of Python, that is classes.

The list data structure can be used to implement the stack. Elements can be appended to the list and removed to simulate the push() and pop() functions. This can be achieved by defining these functions as class methods as follows:

Steps to define a class to implement stacks:

  1. Declare the class
    class stack:​
  2. Declare and initialize the empty stack list and top variable (as '-1') via the 'init' method
        def __init__(self):
            self.tops = -1
            self.stack_ds = []
  3. Creating the push() method to add an element and update the top variable
        def push(self, val):
            self.stack_ds.append(val)
            self.tops += 1
    
  4. Creating the pop() method to remove the last inserted element from the stack and thereby update the top variable
        def pop(self):
            if self.empty() == True:
                print("Stack empty")
                return
            self.tops -= 1
            return self.stack_ds.pop()
  5. Creating the top() method which returns the index of the topmost or last inserted element of the stack
        def top(self):
            if self.empty() == True:
                print("Stack empty")
                return
            return self.tops
  6. Creating the empty() method which checks whether a stack is empty or not
        def empty(self):
            if self.tops == -1:
                return True
            else:
                return False​
  7. Now if we compile and run the stack class after creating an instance of the class
    class stack:
        def __init__(self):
            self.tops = -1
            self.stack_ds = []
    
        def push(self, val):
            self.stack_ds.append(val)
            self.tops += 1
    
        def pop(self):
            if self.empty() is True:
                print("Stack empty")
                return
            self.tops -= 1
            return self.stack_ds.pop()
    
        def top(self):
            if self.empty() is True:
                print("Stack empty")
                return
            return self.tops
    
        def empty(self):
            if self.tops == -1:
                return True
            else:
                return False
    
    
    a = stack()
    a.push(1)
    a.push(2)
    print(a.stack_ds)
    print(a.pop())
    print(a.stack_ds)
    print(a.top())
    print(a.empty())

    output

    [1, 2]
    2
    [1]
    0
    False

Stacks in Python using Linked Lists

Stacks can be implemented in Python using linked lists as well. The basic functions of a stack in general remain the same. Classes are once again used in this case to define and thus build linked lists.

Here two main classes are created.

  1. node class - which acts as a data element instance and is used to actually implement the stack structure via node class instance elements
  2. stack class - which inherits from the node class and holds the stack data structure and the methods to manipulate it and other associated variables like top, head, etc.

Stacks in Python can be implemented using linked lists by following these steps:

  1. Creating the node class
    class Node:
        def __init__(self, val):
            self.value = val
            self.next = None
  2. Creating the stack class with the head and top variables
    class stack:
        def __init__(self):
            self.head = None
            self.top = None
  3. Creating the push() function to insert elements and update the top variable
        def push(self, val):
            if self.empty() is True:
                self.head = Node(val)
                self.top = self.head
            else:
                self.top.next = Node(val)
                self.top = self.top.next
    
  4. Creating the pop() function to remove and return the last inserted element into the stack, and in turn, update the top variable
        def pop(self):
            if self.empty() is True:
                print("Stack empty")
                return
            elif self.head.next is None:
                qtr = self.top
                self.head = None
                self.top = None
                return qtr.value
            ptr = self.head
            qtr = self.top
            while ptr.next != self.top:
                ptr = ptr.next
            ptr.next = None
            return qtr.value​
  5. Creating the display() function to display the linked list in a user-comprehensible form
        def display(self):
            if self.empty() is True:
                print("Stack is empty")
                return
            ptr = self.head
            print("The stack")
            while ptr.next is not None:
                print(ptr.value)
                ptr = ptr.next
            print(ptr.value, " <--top")​
  6. Creating the peek() function which enables the user to view the value of the topmost element
        def peek(self):
            if self.empty() is True:
                print("STack is empty")
                return
            return self.top.value​
  7. Creating the empty() function to check whether a stack is empty or not
        def empty(self):
            if self.head is None:
                return True
            else:
                return False​
  8. Lastly, we create an instance of the stack class and implement the different methods defined to manipulate it
    class Node:
        def __init__(self, val):
            self.value = val
            self.next = None
    
    
    class stack:
        def __init__(self):
            self.head = None
            self.top = None
    
        def push(self, val):
            if self.empty() is True:
                self.head = Node(val)
                self.top = self.head
            else:
                self.top.next = Node(val)
                self.top = self.top.next
    
        def pop(self):
            if self.empty() is True:
                print("Stack empty")
                return
            elif self.head.next is None:
                qtr = self.top
                self.head = None
                self.top = None
                return qtr.value
            ptr = self.head
            qtr = self.top
            while ptr.next != self.top:
                ptr = ptr.next
            ptr.next = None
            return qtr.value
    
        def display(self):
            if self.empty() is True:
                print("Stack is empty")
                return
            ptr = self.head
            print("The stack")
            while ptr.next is not None:
                print(ptr.value)
                ptr = ptr.next
            print(ptr.value, " <--top")
    
        def peek(self):
            if self.empty() is True:
                print("STack is empty")
                return
            return self.top.value
    
        def empty(self):
            if self.head is None:
                return True
            else:
                return False
    
    
    a = stack()
    a.push(1)
    a.push(2)
    a.display()
    a.pop()
    a.display()
    a.pop()
    a.pop()
    a.display()
    a.push(5)
    a.push(6)
    a.display()
    print(a.peek())

    output

    The stack
    1
    2  <--top
    The stack
    1  <--top
    Stack empty
    Stack is empty
    The stack
    5
    6  <--top
    6

Advantages and disadvantages of Stacks in Python

Advantages
  1. Helps in program control change manipulation and local variable storage
  2. Allows to control allocation and deallocation of memory
  3. They are robust data structures
  4. Cross-platform usage
  5. Less hardware requirement
Disadvantages
  1. Not flexible
  2. Lack of scalability
  3. Memory space wastage

Applications of Stacks

  • Used for expression evaluation
  • Conversion of one form of expression to another
  • Reversing input data
  • Memory management
  • Backtracking problems
  • Solving the Parentheses Problem

The Parenthesis Problem

The Parentheses Problem is used to check the following in an expression:

  1. Whether all the parentheses used in the test expression have been opened and closed accordingly or not, and
  2. Whether all the parentheses in the expression are opened and closed in the correct order not.

The Python code implementation for the Parenthese Problem using Stacks in Python is:

class stack:
    def __init__(self):
        self.tops = -1
        self.stack_ds = []

    def push(self, val):
        self.stack_ds.append(val)
        self.tops += 1

    def pop(self):
        if self.empty() is True:
            print("Stack empty")
            return
        self.tops -= 1
        return self.stack_ds.pop()

    def top(self):
        if self.empty() is True:
            print("Stack empty")
            return
        return self.tops

    def empty(self):
        if self.tops == -1:
            return True
        else:
            return False


def parentheses_check(exp):
    para = stack()
    for i in exp:
        if i in ['(', '{', '[']:
            para.push(i)
        elif i in [')', '}', ']']:
            temp = para.top()
            if (para.stack_ds[temp] != '(' or i != ')') and (para.stack_ds[temp] != '{' or i != '}') and (
                    para.stack_ds[temp] != '[' or i != ']'):
                return False
            else:
                para.pop()
                continue
        else:
            continue
    if para.empty() is True:
        return True
    else:
        return False


exp1 = '[{(})]'
exp2 = '{[(){}]}'
exp3 = '[{}]('
exp4 = '[(){}]({})'

print("Is exp1 a complete expression? Ans: ", parentheses_check(exp1))
print("Is exp1 a complete expression? Ans: ", parentheses_check(exp2))
print("Is exp1 a complete expression? Ans: ", parentheses_check(exp3))
print("Is exp1 a complete expression? Ans: ", parentheses_check(exp4))

The output of the above implementation is,

Is exp1 a complete expression? Ans:  False
Is exp1 a complete expression? Ans:  True
Is exp1 a complete expression? Ans:  False
Is exp1 a complete expression? Ans:  True
0 results
Comment / Suggestion Section
Point our Mistakes and Post Your Suggestions