Skip to content

Instantly share code, notes, and snippets.

@jatinsharrma
Created April 17, 2020 20:35
Show Gist options
  • Save jatinsharrma/b1d19c40e1de22a11c0353a1f0702de4 to your computer and use it in GitHub Desktop.
Save jatinsharrma/b1d19c40e1de22a11c0353a1f0702de4 to your computer and use it in GitHub Desktop.
MinMax Stack :List/Array implementation
#--------------------------------------------
#------------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