# CSPT17 Lecture 7
## [Min Stack](https://leetcode.com/problems/min-stack/)

class MinStack:
    """
    Plan
    Use a deque to implement stack
    Use minSoFar to keep track of min element in the stack
    For pushing - update minSoFar if value to push is < minSoFar
    For popping - if element to pop is > minSoFar, then that's fine
        however, if element == minSoFar, then look at elements left and find new minSoFar
    For top - just return the last element in the deque
    For getMin - return self.minSoFar
    """

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.myStack = deque()
        self.minSoFar = float("inf")

    # Runtime: O(1)
    def push(self, x: int) -> None:
        if x < self.minSoFar:
            self.minSoFar = x
        self.myStack.append(x)

    # Runtime: O(n)
    def pop(self) -> None:
        val = self.myStack.pop()
        if val == self.minSoFar:
            if len(self.myStack) > 0:
                self.minSoFar = min(self.myStack)
            else:
                self.minSoFar = float("inf")

    # O(1)
    def top(self) -> int:
        return self.myStack[-1]

    # O(1)
    def getMin(self) -> int:
        return self.minSoFar

## [Stack Using Queues](https://leetcode.com/problems/implement-stack-using-queues/submissions/)

from collections import deque

class MyStack:
    """
    Understand

    myStack = MyStack()
    myStack.push(1)
    myStack.push(2)
    myStack.top() --> 2
    myStack.pop() --> 2
    myStack.top() --> 1
    myStack.pop() --> 1
    myStack.empty() --> True
    
    Plan
    
    """

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.queue = deque()

    def push(self, x: int) -> None:
        """
        Push element x onto stack.
        """
        self.queue.append(x)

    def pop(self) -> int:
        """
        Removes the element on top of the stack and returns that element.
        """
        newQueue = deque()
        
        # transfer all old elements to a new queue (except for the last one)
        while len(self.queue) > 1:
            curr = self.queue.popleft()
            newQueue.append(curr)
        
        lastElement = self.queue.popleft()
        self.queue = newQueue
        return lastElement

    def top(self) -> int:
        """
        Get the top element.
        """
        return self.queue[-1] if len(self.queue) > 0 else float("inf")

    def empty(self) -> bool:
        """
        Returns whether the stack is empty.
        """
        return len(self.queue) == 0