Efficient implementation of queue - time complexity of enqueue and dequeue

Question

I am currently reading a textbook on data structures/algorithms. One of the exercises is to implement a efficient queue using the python list structure: the time complexity of both enqueue and dequeue needs to be O(1) on average. The book says that the time complexity should only be O(n) for a specific case of dequeue, and the rest of the time it should be O(1). I implemented it such that the rear of the queue is the end of the list and front of the queue is the beginning of the list; when I dequeue an element, I do not delete it from the list, but I simply increment a counter so that the method will know which element in the list represents the front of the queue. Here is my code:

class FasterQueue:
    def __init__(self):
        self.items = []
        self.index = 0
    def enqueue(self, item):
        self.items.append(item)
    def dequeue(self):
        index = self.index
        self.index += 1
        return self.items[index]
    def isEmpty(self):
        return self.items == []
    def size(self):
        return len(self.items)

My question: the book says that there is some case where dequeue should take O(1). I have no idea what case this is because it seems like dequeue will always just be getting the value at a certain index. Is my implementation of the queue invalid or am I missing something else? Or is the textbook just looking for another more common implementation?

Thank you so much for the help.

dequeue should always remove the item from one end of the queue. That's O(1) — JacobIRR
@JacobIRR He's not working with a typical python list, the implementation represents a queue. queues are FIFO, and so dequeue should remove from the start of queue, not the end. — Paritosh Singh
i guess the only thing i can think of is, what happens when you try to dequeue past an "empty" queue so to speak. enqueue once, dequeue twice. — Paritosh Singh
Wouldn't that still be O(1) since the worst case on get item for lists is O(1)... I guess the textbook just made a mistake? — davidim
i think it would probably be an index error actually, however yes, i dont really see any "reason" to have an incredibly long list that keeps consuming memory but dequeues as O(1), but i suspect the book expects you to perhaps tidy up the list when you empty it out or something. — Paritosh Singh

Sam Mason Sam Mason · Accepted Answer · 2019-01-02T18:27:54

making this use some more Python-esque features, I'd do something like:

class FasterQueue:
    def __init__(self):
        self.items = []
        self.index = 0

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

    def dequeue(self):
        # do this first so IndexErrors don't cause us ignore items
        obj = self.items[self.index]
        # release the reference so we don't "leak" memory
        self.items[self.index] = None
        self.index += 1
        return obj

    def isEmpty(self):
        return self.index == len(self.items)

    def size(self):
        return len(self.items)

    def try_shrink(self):
        nactive = len(self.items) - self.index
        if nactive + 2 < self.index // 2:
            self.items = self.items[self.index:]
            self.index = 0

have added a try_shrink method that tries to free up used memory space, and it might be useful to call this at the end of dequeue() — otherwise the list will grow arbitrarily long and waste a large amount of memory. the constants in there aren't amazing, but should prevent it from shrinking too often. this operation would be O(n) and might be what was being alluded to

Efficient implementation of queue - time complexity of enqueue and dequeue

4 Answers