# CSPT27 Lecture 10

## Playground

from collections import deque

class Queue:
    def __init__(self):
        self.myDeque = deque()
    
    def __repr__(self):
        return str(self.myDeque)
    
    def push(self, value):
        self.myDeque.append(value)
    
    def pop(self):
        return self.myDeque.popleft()


class Stack:
    def __init__(self):
        self.myList = []
    
    def __repr__(self):
        return str(self.myList)
    
    def push(self, value):
        self.myList.append(value)
    
    def pop(self):
        return self.myList.pop()
    
myQueue = Queue()
myQueue.push(1)
myQueue.push(2)
myQueue.push(3)
print(myQueue.pop())
print(myQueue.pop())
print(myQueue.pop())

## Min Stack

class MinStack:
    """
    Understand
    myStack = MinStack()
    myStack.push(3)
    myStack.push(2)
    myStack.push(1)
    print(myStack.top()) # 1
    print(myStack.getMin()) # 1
    print(myStack.pop()) # 1
    print(myStack.top()) # 2
    print(myStack.getMin()) # 2
    print(myStack.pop()) # 2
    print(myStack.top()) # 3
    
    Plan
    
    """
    # O(1)
    def __init__(self):
        self.stack = deque()
        self.minVal = float("inf")

    # O(1)
    def push(self, val: int) -> None:
        self.stack.append(val)
        if val < self.minVal:
            self.minVal = 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")

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

    # O(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()

## Stacks Using Queues

from collections import deque
class MyStack:
    """
    Understand
    stk = myStack()
    stk.push(1)
    stk.push(2)
    stk.top() # 2
    stk.pop() # 2
    stk.top() # 1
    stk.empty() # false
    stk.pop() # 1
    stk.empty() # true
    
    """
    def __init__(self):
        self.queue = deque()

    def push(self, x: int) -> None:
        self.queue.append(x)

    def pop(self) -> int:
        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:
        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:
        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()