Stack Explained with Example in Python

(86 Views)


Any software developer must have a solid understanding of data structures. A stack is one of the most important data structures out there.

A stack is the most popular linear data structure which follows a particular order in which the operations are performed. If you want to learn more about Stack, see this implementation.

Image Reference: faceprep.in

One of the most popular Stack questions is "Reverse a string using stack".

string = "Solutionfactory" string = reverse(string) print("Reversed string is " + string) # Outputs "yrotcafnoituloS"

First we define pop and push functions.

# Function to add an item to stack def push(stack, item): stack.append(item)
# Function to remove an item from the stack. def pop(stack): if len(stack) == 0: return return stack.pop()

The reverse function pushes all characters of the string into the stack, empties the string and then pops all characters from the stack back to the string. The result is the reversed version of the original string.

def reverse(string): n = len(string) stack = [] # Push all characters of string to stack for i in range(0, n, 1): push(stack, string[ i ]) string = "" # Pop all characters of the string and put them back to string for i in range(0, n, 1): string += pop(stack) return string

Python code for stack with functions to retrieve the max and min elements from it in O(1) time complexity.

class Stack: def __init__(self): self.__vals = [] self.__mins = [float("+inf")] self.__maxes = [float("-inf")] def __raise_if_empty(self): if self.is_empty(): raise Exception("Stack is empty!") def is_empty(self): """ O(1) """ return len(self.__vals) == 0 def push(self, value): """ O(1) """ new_min = min(value, self.__mins[-1]) new_max = max(value, self.__maxes[-1]) self.__vals .append(value) self.__mins .append(new_min) self.__maxes.append(new_max) def pop(self): """ O(1) """ self.__raise_if_empty() self.__maxes.pop() self.__mins.pop() return self.__vals.pop() def max(self): """ O(1) """ self.__raise_if_empty() return self.__maxes[-1] def min(self): """ O(1) """ self.__raise_if_empty() return self.__mins[-1] if __name__ == '__main__': """ Some test example """ s = Stack() for val in [2, 3, 1, 4]: # any numbers print("push:", val) s.push(val) print("min:",s.min(),", max:",s.max()) print("Stack is empty:", s.is_empty()) # False while not s.is_empty(): print("pop:", s.pop()) print("Stack is empty:", s.is_empty()) # True # s.pop() # raises the exception

Solution Worked 0 UpvotesUpvote

        

Solution Didn't Worked 0 DownvotesDownvote



Comments



Get Programming Help
Search

Play 2048 Game Online


Search Tags

    Simple Stack explanation

    Python code for stack push and pop function