Stack Data Structure Implementation Using Python

A stack orders a collection of item where you add and remove items at the same end, known as the TOP. The BASE refers to the other end of the stacks. The base of the stack is significant because the items that are closer to the base represent those that have been in the stack for the longest time. Let’s see Stack Data Structure Implementation Using Python.

The most recently added items is in the top position so that you can remove it first. The push operation adds the item to the stack, and the pop operation removes them.

To understand push and pop, let’s take a look at a familiar situation. Suppose, you start working on a word document, you type in a title and then you change its Font size followed by change of color.

So, you can do whatever you want on the Word files, but when you hit the undo button, it only undoes the last tasks you did.

Similarly, in case of stack you can add as many items you want using push but you can pop or remove only the object which is on the top which means last in is first to be removed. This principle of ordering is known as LIFO that stands for Last-in-first-out, where the newer items are near the top, while older items are near the base.

Stacks are important because they are required whenever there is a need to reverse the order of items as the order of removal is reverse of the order of insertion.

Example:

• Pushing back button on browser while surfing on internet.
• Ctrl+Z(undo) in Microsoft applications
• Remove recently used object from cache.

Stacks are commonly used by software programmers, it may not be quite noticeable while using a program as these operations generally take place at the background. However, many times you may come accross Stack overflow error. This happens when a stack actually runs out of memory.

Stacks seem to be very simple. Yet they are one of the most important data structures as you will see very soon. Stacks serves as a very important element of several data structures and algorithms.

What type is the easiest way for Stack Data Structure Implementation Using Python?

Here we will implement Stack using Python lists.

Step 1: Define the Stack Class

#Define stack class
class Stack:

Step 2: Create constructor

Create a constructor that takes self and size(n) of the stack. In the method we declare that self.stack is an empty list( [] ) and self.size is equal to n that is, the size provided.

#Define stack class
class Stack:
    #Constructor
    def __init__(self, n):
        self.stack = []
        self.size = n

Step 3: Define Push Function

A push function will have two arguments self and the element that we want to push in the list. In this function, we first check if the length of the stack is equal to the size provided as input(n). If yes, then it means that the stack is full and prints the message that no more elements can be appended as the stack is full. However, if that is not the case then we can call the append method to push the element to the stack.

#push method
    def push(self, element):
        if len(self.stack) == self.size:
            print("no more elements can be added as the stack is full")
        else:
            self.stack.append(element)

Step 4: Define POP Function

Check the stack. If it is empty, then print: Stack is empty now. There is nothing to POP!! If it is not empty pop the last item from the stack.

#pop method
    def pop(self):
        if(self.stack == []):
            print("Stack is empty now. There is nothing to POP!!")
        else:
            self.stack.pop()

Step 5: Write down the driver code for executing the code.

Execution

s = Stack(3)
s.push(10)
s.push(6)
print(s.stack)
s.pop()
print(s.stack)

The complete code will be as follows:

Code:

#Define stack class
class Stack:
    #Constructor
    def __init__(self, n):
        self.stack = []
        self.size = n

    #push method
    def push(self, element):
        if len(self.stack) == self.size:
            print("no more elements can be added as the stack is full")
        else:
            self.stack.append(element)

    #pop method
    def pop(self):
        if(self.stack == []):
            print("Stack is empty now. There is nothing to POP!!")
        else:
            self.stack.pop()


s = Stack(3)
s.push(10)
s.push(6)
print(s.stack)
s.pop()
print(s.stack)

Output:

[10, 6]
[10]

Example

Write a program to check if a given string has balanced set of parenthesis or not.

Balanced parenthesis (), {}, [], { [ () ] }, and so on.

Here we have to check if pairs or brackets exists in right format in a string. Expressions such as []{()} are correct. However opening brackets does not find the corresponding closing brackets then the parenthesis is a mismatch. For example: [} or {}[)). To solve this problem we will follow following steps:

Step 1: Define class parenthesis_match

class parenthesis_match:

Step 2: Defining lists for opening and closing brackets.

We now define two lists such that the index of an opening brackets matches with the index of the corresponding closing brackets:

1. List opening_brackets will have all types of opening brackets as element as elements – [“(“,”{“,”[“]
2. List closing_brackets will have all types of closing brackets as elements – [“)”, “}”, “]”]

Here is how we define the lists:

class parenthesis_match:
    opening_brackets = ["(","{","["]
    closing_brackets = [")","}","]"]

Step 2: Defining Constructor, Push and Pop functions

Constructor:

The constructor takes expression as parameter which is the string provided for validation of parameters.

We also initialize list for stacking purpose. The push() and pop() functions will be applied on this list.

    #declare constructor
    def __init__(self, expression):
        self.expression = expression
        self.stack = []

Since we are implementing this using a stack it is quite obvious that we would require push() and pop() functions.

The push() function when called, will add element to the stack.

    #push operation
    def push(self, element):
        self.stack.append(element)

The pop() element on the other hand will pop the last element from the stack.

    #pop operation
    def pop(self):
        if self.stack == []:
            print("Unbalanced Paranthesis")
        else:
            self.stack.pop()

Step 4: Defining the function to do the analysis

We will now write the code to analyse the string.

In this, function, we will perform the following steps:

• First we check the length of the expression. A string of balanced parenthesis will always have even number of characters. If the length of the expression is divisible by two only then we would move ahead with the analysis. So, an if..else loop forms the outer structure of this function.

if len(self.expression)%2 == 0:
            ---- we analyse........
                else:
                    print("Unbalanced Paranthesis")

• Now, considering that we have received a length of even number. We can move ahead with analysis and we can write our code in the “if” block. We will now traverse through the list element by element. If we encounter an opening bracketwe will push it on to the stack, if it is not an opening brackets then we check if the element is in the closing bracket list. If yes then we pop the last element from the stack and see if the index of the element in opening_brackets and closing_brackets list is of same bracket. If yes, then there is a match else the list is unbalanced.

def is_match(self):
        print("expression is = ", self.expression)
        if len(self.expression)%2 == 0:
            for element in self.expression:
                print("evaluation ", element)
                if element in self.opening_brackets:
                    print("It is an opening brackets - ", element, "pusing to stack")
                    self.push(element)
                    print("pushed", element, "on to stack the stack is", self.stack)
                elif element in self.closing_brackets:
                    x = self.stack.pop()
                    print("time to pop element is ", x)
                    if self.opening_brackets.index(x) == self.closing_brackets.index(element):
                        print("Match Found")
                    else:
                        print("Match not found - check paranthesis")
                        return;
                else:
                    print("Unbalanced Paranthesis")

Step 5: Write down the steps for executing the code

Execution

pm = parenthesis_match("([{}])")
pm.is_match()

So, the final code will be as follows, to make things easier for the end user, print commands have been added:

class parenthesis_match:
    opening_brackets = ["(","{","["]
    closing_brackets = [")","}","]"]

    #declare constructor
    def __init__(self, expression):
        self.expression = expression
        self.stack = []

    #push operation
    def push(self, element):
        self.stack.append(element)

    #pop operation
    def pop(self):
        if self.stack == []:
            print("Unbalanced Paranthesis")
        else:
            self.stack.pop()


    def is_match(self):
        print("expression is = ", self.expression)
        if len(self.expression)%2 == 0:
            for element in self.expression:
                print("evaluation ", element)
                if element in self.opening_brackets:
                    print("It is an opening brackets - ", element, "pusing to stack")
                    self.push(element)
                    print("pushed", element, "on to stack the stack is", self.stack)
                elif element in self.closing_brackets:
                    x = self.stack.pop()
                    print("time to pop element is ", x)
                    if self.opening_brackets.index(x) == self.closing_brackets.index(element):
                        print("Match Found")
                    else:
                        print("Match not found - check paranthesis")
                        return;
                else:
                    print("Unbalanced Paranthesis")



pm = parenthesis_match("([{}])")
pm.is_match()

Output

expression is =  ([{}])
evaluation  (
It is an opening brackets -  ( pusing to stack
pushed ( on to stack the stack is ['(']
evaluation  [
It is an opening brackets -  [ pusing to stack
pushed [ on to stack the stack is ['(', '[']
evaluation  {
It is an opening brackets -  { pusing to stack
pushed { on to stack the stack is ['(', '[', '{']
evaluation  }
time to pop element is  {
Match Found
evaluation  ]
time to pop element is  [
Match Found
evaluation  )
time to pop element is  (
Match Found

Conclusion

Here i has seen Stack Data Structure Implementation Using Python

How to Create an Professional Blog Using Laravel PHP