3.2 Stack Min

Created: August 29, 2021 7:58 PM Tags: inheritance, minimum, stack

3.2 Stack Min : How would you design a stack which, in addition to push and pop, has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time.

• Answer)

• 답변) stack클래스에 최소값을 가지는 변수 minVal를 하나 생성하여 이용할 수 있지만 최소값 minVal을 pop할때 새로운 최소값을 찾기 위해 스택을 전체 탐색해야하는 문제가 있다. 즉, pop 혹은 push 연산 시 O(1) time 이 깨진다.

  이를 해결하기 위해 아래와 같이 Stack의 모든 노드에 최소값을 함께 저장할 수 있는데, 스택이 커질 경우 이는 엄천난 공간 낭비를 초래한다.

    class NodeWithMin(self):
    	def __init__(self, value, min):
    		self.value = value
    		self.min = min
  

  따라서, 최소값을 저장하는 또 하나의 스택을 만들어 관리한다면 공간적으로 조금 더 효율적일 것이다. 특히, 최소값은 현 최소값보다 작은 데이터가 push되지 않는 이상 또 다른 스택에 데이터가 쌓이지 않으니 생각보다 제법 공간 효율적일 것이다.

    #describe the Stack's ADT(Abstract Data Type).
    class Stack:
        def __init__(self):
            self.stack = []
        def push(item):
            #add the item to the top of the stack
  
        def pop():
            #remove the item from the top of the stack
  
        def isEmpty():
            #check if the stack is emtpy
  
        def peek():
            #just get the top data of the stack, without removing it
  
    class Stack:
        def __init__(self):
            # store the minimums data.
            # it will update when we push or pop.
            # when we push the data to the stack, I will check whether it is smaller than latest min.
            # and if it is, I will push the data to the mimimums stack.
            # also when we pop the data from the stack and if it is the top data of the minimums stack,
            # we should pop the minimum data from stack2 as well.
            self.stack = []
    	      self.stack2 = []
  
    # Example
    # push(5)  stack1 : {5}, stack2 : {5}
    # push(6)  stack1 : {6,5}, stack2 : {5}
    # push(3)  stack1 : {3,6,5} , stack2 : {3,5}
    # push(7)  stack1 : {7,3,6,5}, stack2 : {3,5}
    # pop() stack1 : {3,6,5} 7 / stack2 : {3,5}
    # pop() stack1 : {6,5} 3 / stack2 : {5}
    # # add : minVal as a top of the stack2
    # # the item smaller than minVal
  
        def push(self, item):
            self.stack.append(item)
            if item <= self.min():
                self.stack2.append(item)
  
        def pop(self):
            val = self.stack.pop()
            if val == self.min():
                self.stack2.pop()
            return val
  
        def min(self):
            if self.stack2.isEmpty():
                return None
            else:
                return self.stack2[-1] #return the top value of the stack2