from .singly_linked_list import LinkedList
from .stack import Stack
"""
A queue is a data structure whose primary purpose is to store and
return elements in First In First Out order.

1. Implement the Queue class using an array
   as the underlying storage structure.Make sure the Queue tests pass.
2. Re-implement the Queue class, this time using the linked list implementation
   as the underlying storage structure.
   Make sure the Queue tests pass.
3. What is the difference between using an array vs. a linked list when
   implementing a Queue?

Stretch: What if you could only use instances of your Stack class to implement
the Queue? What would that look like? How many Stacks would you need? Try it!
"""
"""
Using arrays:
class Queue:
    def __init__(self):
        self.size = 0
        self.storage = []

    def __len__(self):
        count = 0
        for i in self.storage:
            count += 1
        return count

    def enqueue(self, value):
        self.storage.append(value)

    def dequeue(self):
        if len(self.storage) != 0:
            out = self.storage.pop(0)
            return out
        else:
            return None
"""

"""
class Queue:
    # Using linked list
    def __init__(self):
        self.size = 0
        self.storage = LinkedList()

    def __len__(self):
        return self.size

    def enqueue(self, value):
        self.storage.add_to_tail(value)
        self.size += 1

    def dequeue(self):
        if self.size != 0:
            out = self.storage.remove_head()
            self.size -= 1
            return out
        else:
            return None
"""


class Queue:
    # using stacks
    def __init__(self):
        self.size = 0
        self.incoming = Stack()
        self.outgoing = Stack()

    def __len__(self):
        return self.size

    def enqueue(self, value):
        """Adds an element to the top of the outgoing stack"""

        # put everything on the incoming stack, sequentially
        while self.outgoing.storage.head is not None:
            self.incoming.push(
                self.outgoing.storage.tail.get_value()
            )
            self.outgoing.pop()

        # add new value to outgoing stack
        self.outgoing.push(value)
        self.size += 1

        # move all older values back to outgoing stack
        while self.incoming.storage.head is not None:
            self.outgoing.push(
                self.incoming.storage.tail.get_value()
            )
            self.incoming.pop()

    def dequeue(self):
        if self.size != 0:
            out = self.outgoing.pop()
            self.size -= 1
            return out
        else:
            return None
