Queue Sandbox

# -*- 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)