# 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
n -> 1
inserted 1
front: [1] :back
n -> 0
inserted 0
front: [1, 0] :back
n -> 1
inserted 1
front: [1, 0, 1] :back
n -> 5
removed 1
front: [0, 1] :back
n -> 5
removed 0
front: [1] :back
n -> 3
inserted 3
front: [1, 3] :back
n -> 8
removed 1
front: [3] :back
n -> 8
removed 3
front: [] :back
n -> 1
inserted 1
front: [1] :back
n -> 9
removed 1
front: [] :back
n -> 2
inserted 2
front: [2] :back
n -> 9
removed 2
front: [] :back
n -> 5
removed None
front: [] :back
n -> 3
inserted 3
front: [3] :back
n -> 9
removed 3
front: [] :back
n -> 0
inserted 0
front: [0] :back
n -> 1
inserted 1
front: [0, 1] :back
n -> 2
inserted 2
front: [0, 1, 2] :back
n -> 0
inserted 0
front: [0, 1, 2, 0] :back
n -> 8
removed 0
front: [1, 2, 0] :back