class Stack(object):
    """
    A basic array-based implementation of a stack.
    """

    def __init__(self):
        self.items = []

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

    def pop(self):
        if self.is_empty():
            return None
        return self.items.pop()

    def is_empty(self):
        return self.items == []


class Queue(object):
    """
    A basic array-based implementation of a queue.
    """

    def __init__(self):
        self.items = []

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        return self.items.pop(0)

    def is_empty(self):
        return self.items == []


class Node(object):
    """
    An element in a linked list.
    """

    def __init__(self, item=None, next_node=None):
        self.item = item
        self.next_node = next_node

    def __repr__(self):
        return repr(self.item)


class LinkedStack(object):
    """
    Implement a stack ADT based on a singly linked list.
    """

    def __init__(self):
        self.head = None

    def push(self, item):
        new_node = Node(item, self.head)
        self.head = new_node

    """
    'yeah make a pop method that just removes the starting value ....
    now do this step that needs you to have the pop method return the value
    that's getting popped" 
        roll of thunder hear me cry.  
    """
    def pop(self):
        returnValue = self.head.item
        self.head = self.head.next_node
        return returnValue

    def is_empty(self):
        return self.head is None

def main():
    test_linked_queue_duncan_version()

def test_linked_stack_duncan_version():
    testing_stack = LinkedStack()
    print("testing_stack : "+str( testing_stack ) )
    #print("testing_stack.peek() = " + str(testing_stack.peek()))
    #print("testing_stack.stackSize() = " + str(testing_stack.stackSize()) +"\n")
    print("testing_stack.is_empty() = " + str(testing_stack.is_empty()) +"\n")

    incoming_value = 1
    print(f"adding {incoming_value} to testing_stack...")
    testing_stack.push( incoming_value )

    print("testing_stack : "+str( testing_stack ) +"\n")
    #print("testing_stack.peek() = " + str(testing_stack.peek()))
    #print("testing_stack.stackSize() = " + str(testing_stack.stackSize()) + "\n")
    print("testing_stack.is_empty() = " + str(testing_stack.is_empty()) + "\n")

    incoming_value = 2
    print(f"adding {incoming_value} to testing_stack...")
    testing_stack.push( incoming_value )

    print("testing_stack : "+str( testing_stack ) +"\n")
    #print("testing_stack.peek() = " + str(testing_stack.peek()))
    #print("testing_stack.stackSize() = " + str(testing_stack.stackSize()) + "\n")
    print("testing_stack.is_empty() = " + str(testing_stack.is_empty()) + "\n")

    print("i'm going to start popping values now ok???")
    while not testing_stack.is_empty():
        print("\t testing_stack.pop() = " + str(testing_stack.pop()))
    print("program is finalized. have a happy day <3")


def test_stack_duncan_version():
    testing_stack = Stack()

    print("adding element 1 to stack...")
    testing_stack.push(1)
    print("adding element 2 to stack...")
    testing_stack.push(2)
    print("adding element 3 to stack...")
    testing_stack.push(3)

    print("testing_stack.pop() = " + str(testing_stack.pop()))
    print("testing_stack.is_empty() = " + str(testing_stack.is_empty()))

# first in first out
class LinkedQueue(object):
    def __init__(self):
        self.head = None
        self.tail = None

    # Write an enqueue method to add an item to the queue.
    def enqueue(self, item):
        new_node = Node(item, self.tail)

        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next_node = new_node
            self.tail = new_node

    # Write a dequeue method to remove an item from the queue.
    def dequeue(self):
        returnValue = self.head.item
        self.head = self.head.next_node
        return returnValue

    def is_empty(self):
        return self.head is None

def test_linked_queue_duncan_version():
    testing_queue = LinkedQueue()

    print("testing_queue.is_empty() = " + str(testing_queue.is_empty()) + "\n")

    temp_value = 1
    print(f"adding {temp_value} to testing_queue...")
    testing_queue.enqueue(1)

    temp_value = 2
    print(f"adding {temp_value} to testing_queue...")
    testing_queue.enqueue(2)

    temp_value = 3
    print(f"adding {temp_value} to testing_queue...")
    testing_queue.enqueue(3)

    temp_value = 4
    print(f"adding {temp_value} to testing_queue...")
    testing_queue.enqueue(4)


    print("\n")
    temp_value = 1

    print(f"testing_queue.is_empty: {testing_queue.is_empty()}")
    while (testing_queue.is_empty() is False) and (temp_value < 5):
        print(f"dequeueing {temp_value} from testing_queue...")
        print(f"testing_queue.dequeue: {testing_queue.dequeue()}")
        temp_value += 1

"""
Create a DoublyLinkedNode class. Like the Node class, 
it should have a field for storing data, but it should
 have both “previous” and “next” references instead of
  just a “next” reference.
"""
class doubly_linked_node(object):
    def __init__(self, item=None, next_node=None, previous_node=None):
        self.item = item
        self.next_node = next_node
        self.previous_node = previous_node

    def __repr__(self):
        return repr(self.item)

"""
Create a LinkedDeque class with both a head and a tail reference.
 Write a constructor so that it is initially empty.
"""
class LinkedDeque(object):
    def __init__(self):
        self.head = None
        self.tail = None

    """
    Implement an add_back method that takes an item and adds
     it to the back of the deque. (You might find that your
      implementation is very similar to code you wrote earlier.)
    """
    def add_back(self, item):
        new_node = Node(item)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next_node = new_node
            new_node.previous_node = self.tail
            self.tail = new_node

    """
    Implement an add_front method that takes an item and 
    adds it to the front of the deque. (You might find that
     your implementation is very similar to that for add_back. 
     That is okay for now; we have not yet seen any techniques
      for cleanly dealing with this kind of DRY problem.)
    """
    def add_front(self, item):
        new_node = Node(item)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.next_node = self.head
            self.head.previous_node = new_node
            self.head = new_node

    """
    Implement a remove_front method that removes and returns an
     item from the front of the deque.
    """
    def remove_front(self):
        returnValue = self.head.item
        self.head = self.head.next_node
        return returnValue

    """
    Implement a remove_back method that removes and returns an 
    item from the back of the deque.
    """
    def remove_back(self):
        returnValue = self.tail.item
        self.tail = self.tail.previous_node
        return returnValue

    """
    Write an is_empty method.
    """
    def is_empty(self):
        return self.head is None

    def print_linked_list(self):
        current_node = self.head
        while current_node is not None:
            print(current_node.item)
            current_node = current_node.next_node


def test_linked_deque_duncan_version():
    testing_linked_deque = LinkedDeque()
    testing_linked_deque.add_front(1)
    testing_linked_deque.add_front(2)
    testing_linked_deque.add_front(3)

    testing_linked_deque.print_linked_list()

if __name__ == "__main__":
    main()