# Queue.py
# Mechanical MOOC
# MIT OCW 6.189 Homework 3
# Exercise 3.6 - Your First Class
# Glenn Richard
# July 21, 2013
import random
 
class Queue:
    class __Node:
        # private class
        def __init__(self, cargo):
            self.cargo = cargo
            self.next = None
    def __init__(self):
        # Initialize an empty Queue.
        # private attributes
        self.__front = None
        self.__back = None
    def insert(self, cargo):
        # Add a new node to the front to contain the cargo.
        node = self.__Node(cargo)
        if self.__front == None:
            # The Queue was empty.
            self.__front = node
        else:
            # The Queue was not empty.
            self.__back.next = node
        self.__back = node
 
    def remove(self):
        # Remove the front node and return its cargo.
        if self.__front == None:
            # The Queue was empty, so return None.
            return None
        # The Queue was not empty, so update the pointers and return the front cargo.
        cargo = self.__front.cargo
        self.__front = self.__front.next
        if self.__front == None:
            self.__back = None
        return cargo
 
    def isEmpty(self):
        # Is the Queue empty?
        return self.__front == None
 
    def __str__(self):
        # Return a string representation of all the cargo in the Queue nodes.
        qList = []
        p = self.__front
        while p != None:
            qList.append(p.cargo)
            p = p.next
        return "front: " + str(qList) + " :back"
 
# Create and test a new Queue by adding and removing random integers.
q = Queue()
for i in range(20):
    n = random.randint(0, 9)
    print("n -> " + str(n))
    if n >= 5:
        x = q.remove()
        print("removed " + str(x))
    else:
        q.insert(n)
        print("inserted " + str(n))
    print(q)

IyBRdWV1ZS5weQojIE1lY2hhbmljYWwgTU9PQwojIE1JVCBPQ1cgNi4xODkgSG9tZXdvcmsgMwojIEV4ZXJjaXNlIDMuNiAtIFlvdXIgRmlyc3QgQ2xhc3MKIyBHbGVubiBSaWNoYXJkCiMgSnVseSAyMSwgMjAxMwppbXBvcnQgcmFuZG9tCgpjbGFzcyBRdWV1ZToKICAgIGNsYXNzIF9fTm9kZToKICAgICAgICAjIHByaXZhdGUgY2xhc3MKICAgICAgICBkZWYgX19pbml0X18oc2VsZiwgY2FyZ28pOgogICAgICAgICAgICBzZWxmLmNhcmdvID0gY2FyZ28KICAgICAgICAgICAgc2VsZi5uZXh0ID0gTm9uZQogICAgZGVmIF9faW5pdF9fKHNlbGYpOgogICAgICAgICMgSW5pdGlhbGl6ZSBhbiBlbXB0eSBRdWV1ZS4KICAgICAgICAjIHByaXZhdGUgYXR0cmlidXRlcwogICAgICAgIHNlbGYuX19mcm9udCA9IE5vbmUKICAgICAgICBzZWxmLl9fYmFjayA9IE5vbmUKICAgIGRlZiBpbnNlcnQoc2VsZiwgY2FyZ28pOgogICAgICAgICMgQWRkIGEgbmV3IG5vZGUgdG8gdGhlIGZyb250IHRvIGNvbnRhaW4gdGhlIGNhcmdvLgogICAgICAgIG5vZGUgPSBzZWxmLl9fTm9kZShjYXJnbykKICAgICAgICBpZiBzZWxmLl9fZnJvbnQgPT0gTm9uZToKICAgICAgICAgICAgIyBUaGUgUXVldWUgd2FzIGVtcHR5LgogICAgICAgICAgICBzZWxmLl9fZnJvbnQgPSBub2RlCiAgICAgICAgZWxzZToKICAgICAgICAgICAgIyBUaGUgUXVldWUgd2FzIG5vdCBlbXB0eS4KICAgICAgICAgICAgc2VsZi5fX2JhY2submV4dCA9IG5vZGUKICAgICAgICBzZWxmLl9fYmFjayA9IG5vZGUKCiAgICBkZWYgcmVtb3ZlKHNlbGYpOgogICAgICAgICMgUmVtb3ZlIHRoZSBmcm9udCBub2RlIGFuZCByZXR1cm4gaXRzIGNhcmdvLgogICAgICAgIGlmIHNlbGYuX19mcm9udCA9PSBOb25lOgogICAgICAgICAgICAjIFRoZSBRdWV1ZSB3YXMgZW1wdHksIHNvIHJldHVybiBOb25lLgogICAgICAgICAgICByZXR1cm4gTm9uZQogICAgICAgICMgVGhlIFF1ZXVlIHdhcyBub3QgZW1wdHksIHNvIHVwZGF0ZSB0aGUgcG9pbnRlcnMgYW5kIHJldHVybiB0aGUgZnJvbnQgY2FyZ28uCiAgICAgICAgY2FyZ28gPSBzZWxmLl9fZnJvbnQuY2FyZ28KICAgICAgICBzZWxmLl9fZnJvbnQgPSBzZWxmLl9fZnJvbnQubmV4dAogICAgICAgIGlmIHNlbGYuX19mcm9udCA9PSBOb25lOgogICAgICAgICAgICBzZWxmLl9fYmFjayA9IE5vbmUKICAgICAgICByZXR1cm4gY2FyZ28KCiAgICBkZWYgaXNFbXB0eShzZWxmKToKICAgICAgICAjIElzIHRoZSBRdWV1ZSBlbXB0eT8KICAgICAgICByZXR1cm4gc2VsZi5fX2Zyb250ID09IE5vbmUKCiAgICBkZWYgX19zdHJfXyhzZWxmKToKICAgICAgICAjIFJldHVybiBhIHN0cmluZyByZXByZXNlbnRhdGlvbiBvZiBhbGwgdGhlIGNhcmdvIGluIHRoZSBRdWV1ZSBub2Rlcy4KICAgICAgICBxTGlzdCA9IFtdCiAgICAgICAgcCA9IHNlbGYuX19mcm9udAogICAgICAgIHdoaWxlIHAgIT0gTm9uZToKICAgICAgICAgICAgcUxpc3QuYXBwZW5kKHAuY2FyZ28pCiAgICAgICAgICAgIHAgPSBwLm5leHQKICAgICAgICByZXR1cm4gImZyb250OiAiICsgc3RyKHFMaXN0KSArICIgOmJhY2siCgojIENyZWF0ZSBhbmQgdGVzdCBhIG5ldyBRdWV1ZSBieSBhZGRpbmcgYW5kIHJlbW92aW5nIHJhbmRvbSBpbnRlZ2Vycy4KcSA9IFF1ZXVlKCkKZm9yIGkgaW4gcmFuZ2UoMjApOgogICAgbiA9IHJhbmRvbS5yYW5kaW50KDAsIDkpCiAgICBwcmludCgibiAtPiAiICsgc3RyKG4pKQogICAgaWYgbiA+PSA1OgogICAgICAgIHggPSBxLnJlbW92ZSgpCiAgICAgICAgcHJpbnQoInJlbW92ZWQgIiArIHN0cih4KSkKICAgIGVsc2U6CiAgICAgICAgcS5pbnNlcnQobikKICAgICAgICBwcmludCgiaW5zZXJ0ZWQgIiArIHN0cihuKSkKICAgIHByaW50KHEp