Created
May 30, 2017 08:00
-
-
Save kishan3/9197936abfc7f2dffe2034d0251c926c to your computer and use it in GitHub Desktop.
Optimized stack implementation which give minimum element from stack in O(1) time.
This file contains 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
class Stack(object): | |
"""docstring for Stack""" | |
def __init__(self): | |
self.stack = [] | |
self.min_stack = [] | |
def push(self, x): | |
if self.isEmpty(): | |
self.stack.append(x) | |
self.min_stack.append(x) | |
else: | |
self.stack.append(x) | |
mini = self.min_stack[-1] | |
if x <= mini: | |
self.min_stack.append(x) | |
def isEmpty(self): | |
return self.stack == [] | |
def peek(self): | |
if not self.isEmpty(): | |
return self.stack[-1] | |
return 0 | |
def pop(self): | |
if self.isEmpty(): | |
print "Stack is empty.Can not pop anymore." | |
res = self.stack.pop() | |
if res == self.min_stack[-1]: | |
self.min_stack.pop() | |
return res | |
def getMin(self): | |
return self.min_stack[-1] | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment