# -*- coding: utf-8 -*-
"""qandstack.ipynb

Automatically generated by Colaboratory.

Original file is located at
    https://colab.research.google.com/drive/1Nr_QNCQNn2BqTil9swxDWfpsBcdumEbQ

# Queues and Stacks

## Queue
- think of a queue as a line of people queing up to be served
- FIFO (First In First Out)

## Stack
- think of a stack as a stack of recipts on a nail or pin
- LIFO (Last In First Out)

What data structure could be of use as an underlying data storage for a stack or queue?
"""

# lets write a simple stack
class Stack:
    def __init__(self):
        self.storage = []

    def push(self, item):
        """
    push the item on to the top of the stack
    """
        self.storage.append(item)

    def pop(self):
        """
    pop the item from the top of the stack returning said item if there is anything on the stack.
    otherwise return "The Stack is Empty"
    """
        if len(self.storage) > 0:
            return self.storage.pop()
        return "The Stack is Empty"

    def peek(self):
        if len(self.storage) > 0:
            return self.storage[-1]
        return "The Stack is Empty"


s = Stack()
s.push(10)
s.push(20)
s.push(30)
l = []
l.append(s.pop())
l.append(s.pop())
l.append(s.pop())
print(l)

# lets write a simple queue
class Queue:
    def __init__(self):
        self.storage = []

    def enqueue(self, item):
        """
    enqueues the item in to the queue
    """
        self.storage.append(item)

    def dequeue(self):
        """
    dequeue the item from the front of the queue returning said item if there is anything on the queue.
    otherwise return "The Queue is Empty"
    """
        if len(self.storage) > 0:
            return self.storage.pop(0)
        return "The Queue is Empty"


q = Queue()
q.enqueue(10)
q.enqueue(20)
q.enqueue(30)

l2 = []
l2.append(q.dequeue())
l2.append(q.dequeue())
l2.append(q.dequeue())

print(l2)

# lets write a more performant queue
"""
  F      R
[10]-> [20]-> None
"""


class LLNode:
    def __init__(self, data):
        self.data = data
        self.next = None

    def __repr__(self):
        return f"[{self.data}]"


class LLQueue:
    def __init__(self):
        self.front = None
        self.rear = None

    def enqueue(self, item):
        new_node = LLNode(item)

        if self.rear is None:
            self.front = new_node
            self.rear = new_node
        else:
            self.rear.next = new_node
            self.rear = new_node

    def dequeue(self):
        old_front = "The Queue is Empty"
        if self.front is not None:
            old_front = self.front
            self.front = old_front.next

        if self.front is None:
            self.rear = None

        return old_front


q = LLQueue()
q.enqueue(10)
q.enqueue(20)
q.enqueue(30)

l2 = []
l2.append(q.dequeue())
l2.append(q.dequeue())
l2.append(q.dequeue())
l2.append(q.dequeue())

print(l2)

"""# Break
# CODE 8119
"""

# lets write a more performant stack
class LLNode:
    def __init__(self, data):
        self.data = data
        self.next = None

    def __repr__(self):
        return f"[{self.data}]"


class LLStack:
    def __init__(self):
        self.top = None

    def push(self, data):
        new_node = LLNode(data)
        new_node.next = self.top
        self.top = new_node

    def pop(self):
        if self.top is not None:
            poped_node = self.top
            self.top = poped_node.next

            return poped_node
        else:
            return "The Stack is Empty"


"""# Demos"""

"""
You've encountered a situation where you want to easily be able to pull the
largest integer from a stack.
You already have a `Stack` class that you've implemented using a dynamic array.
Use this `Stack` class to implement a new class `MaxStack` with a method
`get_max()` that returns the largest element in the stack. `get_max()` should
not remove the item.
*Note: Your stacks will contain only integers. You should be able to get a
runtime of O(1) for push(), pop(), and get_max().*
"""


class Stack:
    def __init__(self):
        """Initialize an empty stack"""
        self.items = []

    def push(self, item):
        """Push a new item onto the stack"""
        self.items.append(item)

    def pop(self):
        """Remove and return the last item"""
        # If the stack is empty, return None
        # (it would also be reasonable to throw an exception)
        if not self.items:
            return None

        return self.items.pop()

    def peek(self):
        """Return the last item without removing it"""
        if not self.items:
            return None
        return self.items[-1]


class MaxStack:
    def __init__(self):
        # Your code here
        self.stack = Stack()
        self.maxes_stack = Stack()

    def push(self, item):
        """Add a new item onto the top of our stack."""
        # Your code here
        self.stack.push(item)

        if self.maxes_stack.peek() is None or item >= self.maxes_stack.peek():
            self.maxes_stack.push(item)

    def pop(self):
        """Remove and return the top item from our stack."""
        # Your code here
        item = self.stack.pop()

        if item == self.maxes_stack.peek():
            self.maxes_stack.pop()

        return item

    def get_max(self):
        """The last item in maxes_stack is the max item in our stack."""
        # Your code here
        return self.maxes_stack.peek()


ms = MaxStack()
ms.push(20)
ms.push(30)
ms.push(9)
ms.push(102)
ms.push(33)
ms.push(1)
ms.pop()
ms.pop()
ms.pop()
print(ms.get_max())

"""# Optionals"""

"""
Your goal is to define a `Queue` class that uses two stacks. Your `Queue` class
should have an `enqueue()` method and a `dequeue()` method that ensures a
"first in first out" (FIFO) order.
As you write your methods, you should optimize for time on the `enqueue()` and
`dequeue()` method calls.
The Stack class that you will use has been provided to you.
"""


class Song:
    def __init__(self, name, link):
        self.name = name
        self.link = link

    def __repr__(self):
        return f"{self.name}: {self.link}"


s1 = Song("Bob The Builder", "http://www.gogle.co.uk/")
s2 = Song("Eclipse - Pink Floyd 1", "http://www.yashoo.com")
s3 = Song("Bob The Builder 2", "http://www.gogle.co.uk/")
s4 = Song("Eclipse - Pink Floyd 2", "http://www.yashoo.com")
s5 = Song("Bob The Builder 3", "http://www.gogle.co.uk/")
s6 = Song("Eclipse - Pink Floyd 3", "http://www.yashoo.com")
s7 = Song("Bob The Builder", "http://www.gogle.co.uk/")
s8 = Song("Eclipse - Pink Floyd Uncut", "http://www.yashoo.com")


class Stack:
    def __init__(self):
        self.data = []

    def push(self, item):
        self.data.append(item)

    def pop(self):
        if len(self.data) > 0:
            return self.data.pop()
        return "The stack is empty"


class QueueTwoStacks:
    def __init__(self):
        # Your code here
        self.in_stack = Stack()
        self.out_stack = Stack()

    def enqueue(self, item):
        # Your code here
        self.in_stack.push(item)

    def dequeue(self):
        # Your code here
        if len(self.out_stack.data) == 0:
            while len(self.in_stack.data) > 0:
                stack_item = self.in_stack.pop()
                self.out_stack.push(stack_item)
            if len(self.out_stack.data) == 0:
                return "can not dequeue from an empty queue"

        return self.out_stack.pop()


# q = QueueTwoStacks()
# q.enqueue(20)
# q.enqueue(220)
# q.enqueue(201)
# q.enqueue(120)
# q.enqueue(230)
# q.enqueue(320)
# q.enqueue(3)

# l3 = []
# l3.append(q.dequeue())
# l3.append(q.dequeue())
# l3.append(q.dequeue())
# l3.append(q.dequeue())
# l3.append(q.dequeue())
# l3.append(q.dequeue())
# l3.append(q.dequeue())

q = QueueTwoStacks()
q.enqueue(s1)
q.enqueue(s2)
q.enqueue(s3)
q.enqueue(s4)
q.enqueue(s5)
q.enqueue(s6)
q.enqueue(s7)

l3 = []
l3.append(q.dequeue())
l3.append(q.dequeue())
l3.append(q.dequeue())
l3.append(q.dequeue())
l3.append(q.dequeue())
l3.append(q.dequeue())
l3.append(q.dequeue())

print(l3)

# FIFO: first in first out

# create the abstract data type
class Queue:
    def __init__(self):
        # initialize it to a one dimensional array or linked list
        self.queue = []

    """
    Stack methods (enqueue, dequeue, peek, is_empty, size_queue)
    """

    # function to check if the queue is empty O(1)
    def is_empty(self):
        return self.queue == []

    # function to add data to the queue O(1)
    def enqueue(self, data):
        self.queue.append(data)

    # function to remove and return the first item inserted to the queue O(N)
    def dequeue(self):

        # first check to make sure its not an empty queue
        if self.size_queue()!= 0:
            # get the first item in the queue
            data = self.queue[0]
            # remove it
            del self.queue[0]
            # return the item
            return data
        else:
            return -1

    # function to return the first item in the queue without removing it
    # O(1)
    def peek(self):
        return self.queue[0]

    # function get the size of the queue O(1)
    def size_queue(self):
        return len(self.queue)


"""
Using the methods
"""
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print(f'Size: {queue.size_queue()}')
print(f'Dequeue: {queue.dequeue()}')
print(f'Size: {queue.size_queue()}')
print(f'Peeked item: {queue.peek()}')
print(f'Size: {queue.size_queue()}')

"""Make a Queue class using a list!
Hint: You can use any Python list method
you'd like! Try to write each one in as
few lines as possible.
Make sure you pass the test cases too!"""

class Queue:
    def __init__(self, head=None):
        self.storage = [head]

    def enqueue(self, new_element):
        if(self.storage):
            self.storage.append(new_element)
        else:
            self.storage = [new_element]
        return new_element

    def peek(self):
        if(self.storage):
            return self.storage[0]
        else:
            return None

    def dequeue(self):
        if(self.storage):
            return self.storage.pop(0)
        else:
            return None

# Setup
q = Queue(1)
q.enqueue(2)
q.enqueue(3)

# Test peek
# Should be 1
print q.peek()

# Test dequeue
# Should be 1
print q.dequeue()

# Test enqueue
q.enqueue(4)
# Should be 2
print q.dequeue()
# Should be 3
print q.dequeue()
# Should be 4
print q.dequeue()
q.enqueue(5)
# Should be 5
print q.peek()

class Queue:

    def __init__(self):
        """
        Initializing Queue.
        """
        self.queue = []

    def isEmpty(self) -> bool:
        return True if len(self.queue) == 0 else False

    def front(self) -> int:
        return self.queue[-1]

    def rear(self) -> int:
        return self.queue[0]

    def enqueue(self, x: int) -> None:
        self.x = x
        self.queue.insert(0, x)       

    def dequeue(self) -> None:
        self.queue.pop()

from collections import deque
class Queue:

    def __init__(self):
        """
        Initializing Queue.
        """
        self.queue = deque()

    def isEmpty(self) -> bool:
        return True if len(self.queue) == 0 else False

    def front(self) -> int:
        return self.queue[-1]

    def rear(self) -> int:
        return self.queue[0]

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

    def dequeue(self) -> None:
        self.queue.popleft()