http://www.lintcode.com/en/problem/implement-queue-by-two-stacks/
In [1]:
class MyQueue:
def __init__(self):
self.stack1 = []
self.stack2 = []
def push(self, element):
# write your code here
self.stack1.append(element)
def top(self):
# write your code here
# return the top element
if len(self.stack2) == 0:
while self.stack1:
self.stack2.append(self.stack1.pop())
return self.stack2[-1]
def pop(self):
# write your code here
# pop and return the top element
if len(self.stack2) == 0:
while self.stack1:
self.stack2.append(self.stack1.pop())
return self.stack2.pop()
http://www.lintcode.com/en/problem/implement-stack-by-two-queues/
In [2]:
class Stack:
# initialize your data structure here.
def __init__(self):
self.queue = []
# @param x, an integer, push a new item into the stack
# @return nothing
def push(self, x):
# Write your code here
self.queue.append(x)
# @return nothing, pop the top of the stack
def pop(self):
# Write your code here
n = len(self.queue)
for i in range(n-1):
self.queue.append(self.queue.pop(0))
return self.queue.pop(0)
# @return an integer, return the top of the stack
def top(self):
# Write your code here
top = None
n = len(self.queue)
for i in range(n):
top = self.queue.pop(0)
self.queue.append(top)
return top
# @return an boolean, check the stack is empty or not.
def isEmpty(self):
# Write your code here
return self.queue == []
Implement a stack with min() function, which will return the smallest number in the stack.
It should support push, pop and min operation all in O(1) cost.
In [3]:
class MinStack(object):
def __init__(self):
# do some intialize if necessary
self.stack = []
def push(self, number):
# write yout code here
curMin = self.min()
if curMin is None or number < curMin:
curMin = number
self.stack.append([number, curMin])
def pop(self):
# pop and return the top item in stack
pop = self.stack.pop()
return pop[0]
def min(self):
# return the minimum number in stack
if len(self.stack) == 0:
return None
else:
return self.stack[-1][1]
In [ ]: