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

from collections import deque

class MinStack:
    """
    Understand
    
    myStack = MinStack()
    myStack.push(1)
    myStack.push(2)
    myStack.push(3)
    print(myStack.top()) # 3
    print(myStack.getMin()) # 1
    print(myStack.pop()) # 3
    print(myStack.top()) # 2
    myStack.pop() # 2
    myStack.pop() # 1
    myStack.top() # inf
    myStack.getMin() # inf
    
    Plan
    Use minVal instance property to keep track of min val when pushing/popping the stack
    
    When pushing, keep track if there's a lower value
    When popping, keep track whether or not the value that is about to get popped is the lowest value
    if it's the lowest, then update minVal to be the next lowest value
    """

    # O(1)
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = deque()
        self.minVal = float("inf")

    # O(1)
    def push(self, val: int) -> None:
        if val < self.minVal:
            self.minVal = val
        self.stack.append(val)

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

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.minVal


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

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

from collections import deque

class MyStack:

    """
    Understand
    
    myStack = MyStack()
    myStack.push(1)
    myStack.push(2)
    myStack.push(3)
    myStack.top() # 3
    myStack.pop() # 3
    myStack.top() # 2
    myStack.pop() # 2
    myStack.pop() # 1
    myStack.pop() # None
    
    Plan
    
    push - enqueue onto our queue
    pop - transfer all elements in queue1 onto queue2 (except the last element). The last element is the 
    topmost element of the stack. Dequeue it and return it
    """
    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.
        """
        if len(self.queue) == 0:
            return float("inf")

        temp = deque()
        while len(self.queue) > 1:
            temp.append(self.queue.popleft())
        
        lastElement = self.queue.popleft()
        self.queue = temp
        return lastElement

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

        temp = deque()
        while len(self.queue) > 1:
            temp.append(self.queue.popleft())
        
        lastElement = self.queue.popleft()
        temp.append(lastElement)
        self.queue = temp
        return lastElement

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


# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()

## Sandbox

from collections import deque

class Queue:
    def __init__(self):
        self.myDeque = deque()
        
    def enqueue(value):
        self.myDeque.append(value)
        
    def dequeue():
        return self.myDeque.popleft()

    def peek():
        return self.myDeque[0]






class QueueUsingLists:
    def __init__(self):
        self.myList = []
        
    def enqueue(value):
        self.myList.append(value)
        
    def dequeue():
        return self.myList.pop(0)







class Stack:
    def __init__(self):
        self.d = deque()
    
    # O(1)
    def push(self, value):
        self.d.append(value)
    
    # O(1)
    def pop(self):
        return self.d.pop()

class LinkedList:
    def __init__():
        pass
    def addToHead(value):
        pass
    def removeFromHead():
        pass
    
class StackUsingLinkedLists:
    def __init__(self):
        self.linkedList = LinkedList()
    
    # O(1)
    def push(self, value):
        self.linkedList.addToHead(value)
    
    # O(1)
    def pop(self):
        return self.linkedList.removeFromHead()


class StackUsingLists:
    
    def __init__(self):
        self.myList = []
    
    # O(n)
    def push(self, value):
        self.myList.append(value)
    
    # O(n)
    def pop(self):
        return self.myList.pop()