Created
April 17, 2020 20:35
-
-
Save jatinsharrma/b1d19c40e1de22a11c0353a1f0702de4 to your computer and use it in GitHub Desktop.
MinMax Stack :List/Array implementation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #-------------------------------------------- | |
| #------------MinMax Stack-------------------- | |
| #-------------------------------------------- | |
| ''' | |
| This is similar to the normal stack with small modification. | |
| MinMax Stack can return min and max value of the stack in O(1) time | |
| Below code is the list/array implementation of stack | |
| Fore linked list implementation in C : https://gist.github.com/jatinsharrma/47b0c3ab06856563b890e400338956da | |
| For static stack implementation in C : https://gist.github.com/jatinsharrma/4bdd922c2f17cc5076561dcbfe3a2c43 | |
| ''' | |
| # MinMax Class | |
| class MinMaxStack: | |
| def __init__(self): | |
| self.stack = [] | |
| self.minmax = [] | |
| self.top = -1 | |
| # this method tel whether the stack is empty or not | |
| def isEmpty(self): | |
| if self.stack: | |
| return False | |
| return True | |
| # this method push new element into the stack | |
| def push(self,value): | |
| if self.isEmpty(): | |
| self.stack.append(value) | |
| self.minmax.append([value,value]) | |
| else: | |
| new_minmax = self.minmax[self.top][:] | |
| if value < new_minmax[0]: | |
| new_minmax[0] = value | |
| elif value > new_minmax[1]: | |
| new_minmax[1] = value | |
| self.stack.append(value) | |
| self.minmax.append(new_minmax) | |
| self.top += 1 | |
| # this method pop the top most element | |
| def pop(self): | |
| if not self.isEmpty(): | |
| self.minmax.pop() | |
| self.top -= 1 | |
| return self.stack.pop() | |
| return False | |
| # this method returns the minimum element | |
| def getMin(self): | |
| if not self.isEmpty(): | |
| return self.minmax[self.top][0] | |
| return False | |
| #this method returns the maximum element | |
| def getMax(self): | |
| if not self.isEmpty(): | |
| return self.minmax[self.top][1] | |
| return False | |
| #testing | |
| if __name__ == "__main__": | |
| stack = MinMaxStack() | |
| items = [4,5,7,8,9,1,5,0] | |
| for i in items: | |
| stack.push(i) | |
| for i in items: | |
| print("Min value : " ,stack.getMin()," | Max value : ",stack.getMax(), " | Top value : ", stack.pop()) | |
| print("Minimum element test in empty stack : ",stack.getMax()) | |
| print("Maximum element test in empty stack : ",stack.getMax()) | |
| print("Top element test in empty stack : ",stack.getMax()) | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment