cqueue.py

class CQueue:
    def __init__(self, k=0.5):
        self.q = []
        self.m = 0
        self.k = k

    def enqueue(self, v):
        self.q.append(v)

    def dequeue(self):
        if not self.q:
            return None
        V = self.k * self.q[0]
        for i, v in enumerate(self.q[1:]):
            if self.m + v < V:
                self.m += v
                return self.q.pop(i + 1)
        self.m = 0
        return self.q.pop(0)

[strike]Do you think this can be O(logn) push and O(logn) pop? Some complex data structures and functions are not implemented.[/strike]
Update: it's still O(n) push, and O(1) pop. Simplified my code.

class CQueue:
    def __init__(self, k=0.5):
        self.nodes = []
        self.k = k

    def enqueue(self, v):
        if self.nodes:
            for node in self.nodes:
                if node.get_cap() < v && node.group_list:
                    node.push(v)
                    return
            new_node = CQueueGroup(v, self.k)
            self.nodes.append(new_node)
        else:
            new_node = CQueueGroup(v, self.k)
            self.nodes.append(new_node)

    def dequeue(self):
        while True:
            if not self.nodes:
                return None
            top = self.nodes[0].pop()
            if top:
                return top
            else:
                self.nodes.pop(0)

class CQueueGroup:
    def __init__(self, head, k):
        self.head = head
        self.group_cap = head * k
        self.group_list = [head]

    def push(self, v):
        if self.group_cap - v > 0:
            self.group_cap -= v
            self.group_list.append(v)
            return True
        return False

    def pop(self):
        if not self.q:
            return None
        if len(self.group_list) > 1:
            self.group_cap += self.group_list[1]
            return self.group_list.pop(1)
        else:
            return self.group_list.pop(0)

    def get_cap(self):
        return self.group_cap