class Node:
    def __init__(self,element,pointer = None):
        self.element = element
        self.pointer = pointer
class LinkedQueue:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

    def __len__(self):
        return self.size

    def is_empty(self):
        return self.size == 0

    def first(self):
        if self.is_empty():
            print("Queue is empty.")
        else:
            return self.head.element

    def dequeue(self):
        if self.is_empty():
            print("Queue is empty.")
        else:
            answer = self.head.element
            self.head = self.head.pointer
            self.size -= 1
            if self.is_empty():
                self.tail = None
            return answer

    def enqueue(self, e):
        newest = Node(e, None)
        if self.is_empty():
            self.head = newest
        else:
            self.tail.pointer = newest
        self.tail = newest
        self.size += 1

    def delete(self, i, j):  # delete j
        if j == self.tail:
            self.tail = i
        i.pointer = j.pointer
        j.pointer = None
        self.size -= 1
        return j.element

    def add_first(self, e):
        newest = Node(e, None)
        newest.pointer = self.head
        self.head = newest
        self.size = self.size + 1

        if self.size == 1:
            self.tail = newest

    def contact(self, q):
        self.tail.pointer = q.head
        self.tail = q.tail
        self.size += q.size


def quickSort(reference):
    q = LinkedQueue()
    temp = reference
    while temp != None:
        q.enqueue(temp.element)
        temp = temp.pointer# to the last
    if q.size == 1:
        return q.head
    if q.size == 0:
        return None
    past = reference
    now = reference.pointer
    pivot = reference.element

    left = LinkedQueue()

    while now != None:
        if now.element <= pivot:
            t = q.delete(past,now)
            left.enqueue(t)
            now = past.pointer
        else:
            past = now
            now = past.pointer

    h = q.dequeue()
    left.head = quickSort(left.head)
    q.head = quickSort(q.head)
    q.add_first(h)

    if left.size == 0:
        return q.head
    else:
        left.contact(q)
        return left.head

#use to check
q = LinkedQueue()
q.enqueue(1)
q.enqueue(7)
q.enqueue(3)
q.enqueue(4)
q.enqueue(6)


print(quickSort(q.head).element)