Issue 4: The Optimizing a Queue Challenge

A calm sea does not make a skilled sailor.
- African proverb  



Last week, we implemented a Stack and a Queue class for exercise purposes. A Queue is a list of objects that operate on a first-in, first-out basis. However, we noticed that the time it took to process a Queue increased linearly as the number of objects inside the Queue increased. This led us to a challenge: Can we design a Queue where the processing time is constant?

In order to complete this challenge, it is necessary for us to analyze two things. What method increases the processing time, and how can we adjust the method so that it behaves differently?

As it turns out, calling .pop() on a list is significantly faster than calling .pop(0). The reasoning behind this is due to how lists work inherently. Removing an element from the end of a list is easy, but removing an element from the beginning will require every single element to be shifted.

Thus, the implication is very straight forward - Always call .pop() and never .pop(0). However, the complication is that by definition: removing an object from a Queue results in the removal of the first object, and not the last.

This conveys to us that we must design our algorithm in a way such that attempting to remove an object from a Queue results in the removal of the last element, but at the same time, the last element must be the first object.

It is then a necessity that we should swap the first element with the last element, before calling .pop(). Luckily, swapping two elements is very simple. My proposed algorithm is as follow:

• A variable is needed to keep track of our "front". This variable will tell us the index of the element that is to be removed next. Our "front" will begin at index 0.
• A variable is needed to keep track of our "back". This variable will tell us the index of the element that we have just swapped our "front" with. Our "back" will begin at index -1.
• If we try to add more items to the Queue in the middle of our algorithm, it will give us problems. A easy way out is to add a "buffer" that keeps track of newly added items until our algorithm has finished with the removal of all the items in the original Queue.

1. When enqueuing onto an empty Queue, our "front" remains at index 0, but our "back" increases by 1.
2. When we attempt to dequeue from a newly enqueued Queue, our "front" element is swapped with our "back" element. The last element is then removed from the Queue. "front" is increased by 1, while "back" is now the previous "front"
3. When attempting to enqueue after any attempts of dequeue has been made, all objects will be appended to our "buffer" instead.
4. Eventually, our "front" will become greater than or equal to last index. This signifies that we have reached the end of our list. 
5. Upon reaching the end of our list, any further dequeues can be completed without swapping.
6. When the list becomes empty, our "buffer" is transfered over into our Queue, and all indicators are reset. (i.e. "front" becomes 0 again, and "back" becomes the last index.)

Here is a visual example of each step outlined above:

>>> q = Queue()
>>> q._data
[]
>>> q._front
0
>>> q._back
-1
>>> q.enqueue(0)
>>> q.enqueue(1)
>>> q.enqueue(2)
>>> q.enqueue(3)
>>> q._data
[0, 1, 2, 3]
>>> q._front
0
>>> q._back
3
>>> q.dequeue()
0
>>> q._data
[3, 1, 2]
>>> q._front
1
>>> q._back
0
>>> q._dequeuing
True
>>> q.enqueue(4)
>>> q._data
[3, 1, 2]
>>> q._front
1
>>> q._back
0
>>> q._buffer
[4]
>>> q.dequeue()
1
>>> q._data
[3, 2]
>>> q._front
2
>>> q._back
1
>>> q._eol
True
>>> q.dequeue()
2
>>> q._data
[3]
>>> q.dequeue()
3
>>> q.is_empty()
False
>>> q._data
[4]
>>> q._buffer
[]
>>> q._front
0
>>> q._back
0

I verified this algorithm with the testqueue.py and timequeue.py provided for us. testqueue.py passed successfully in under 0.001 seconds, and timequeue.py gave me the following results:

Running time on 100000 items: 0.056036949157714844
Running time on 200000 items: 0.056036949157714844
Running time on 300000 items: 0.0570378303527832
Running time on 400000 items: 0.05903792381286621
Running time on 500000 items: 0.0570368766784668
Running time on 600000 items: 0.057038068771362305
Running time on 700000 items: 0.057038068771362305
Running time on 800000 items: 0.05803799629211426
Running time on 900000 items: 0.057038068771362305
Running time on 1000000 items: 0.057038068771362305

(I increased the number of items to make the difference more noticeable)

Here is my complete code for reference. I hope it helped!

       


class Queue:
    '''A list on a first in first out basis.
    
    Challenge: Optimize Queue so that execution time of enqueue and dequeue
    does not grow linearly. You must actually remove the object from the Queue.
    You cannot simply "hide it".
    
    
    The Problem: Attempting to pop/add an item at beginning of a list takes
    significantly longer than trying to pop/add at the end.
    
    Implication: We should only pop/add items at the end of the list.
    
    Concept:

    Example Queue: _data = [0, 1, 2, 3, 4, 5]
    
    We keep track of a front and back index
    _front = 0 # item is 0
    _back = 5 # item is 5
    
    We keep track of a buffer incase we are enqueuing in between dequeues
    _dequeuing = false
    _buffer = []
    
    We need to keep track of whether we reached the end of the list
    _eol = false
    
    When you enqueue before dequeuing, the _back is moved to the very end:
    _data.append(6) # [0, 1, 2, 3, 4, 5, 6]
    _back = len(_data) - 1 # index 6, item is 6
    
    When you dequeue, we want to swap the front and the back.
    _data = [6, 1, 2, 3, 4, 5, 0].pop()
    _back = _front # item is 6, index is 0
    
    Since we are poping the front, the front is now technically at index 1
    _front = front + 1 # index 1, item is 1
    _data = [6, 1, 2, 3, 4, 5]
    
    The first dequeue requires us to indicate this
    _dequeuing = true
    
    Another regular pop
    _data = [6, 5, 2, 3, 4, 1].pop()
    _back = _front # Item is 5, index is 1
    _front = _front + 1 # index 2, item 2
    _data = [6, 5, 2, 3, 4]
    
    Enqueuing in the middle of dequeuing adds to the buffer
    _data = [6, 5, 2, 3, 4]
    _buffer = [7]
    
    Dequeue #3
    _data = [6, 5, 4, 3, 2].pop()
    _back = _front # index 2, item 4
    _front = _front + 1 # index 3, item 3
    _data = [6, 5, 4, 3]
    
    Enqueueing again
    _buffer = [7, 8]
    
    Dequeue #4 reaches the end
    _front == len (_data) - 1
    i.e. _front = _back + 1
    
    _data = [6, 5, 4, 3].pop()
    _data = [6, 5, 4]
    
    Now we can just pop only.
    _eol = true
    
    furthur dequeues:
    
    if _eol == true:
        _data.pop()
        
    When the queue is empty, we put in the buffer and reset everything
    
    _data = _buffer
    _buffer = []
    _dequeuing = false
    _eol = false
    '''
    
    
    def __init__(self: "Queue") -> None:
        '''Initalize an empty Queue
        
        >>> q = Queue()
        >>> q._data
        []
        >>> q._front
        0
        >>> q._back
        -1
        >>> q.enqueue(0)
        >>> q.enqueue(1)
        >>> q.enqueue(2)
        >>> q.enqueue(3)
        >>> q._data
        [0, 1, 2, 3]
        >>> q._front
        0
        >>> q._back
        3
        >>> q.dequeue()
        0
        >>> q._data
        [3, 1, 2]
        >>> q._front
        1
        >>> q._back
        0
        >>> q._dequeuing
        True
        >>> q.enqueue(4)
        >>> q._data
        [3, 1, 2]
        >>> q._front
        1
        >>> q._back
        0
        >>> q._buffer
        [4]
        >>> q.dequeue()
        1
        >>> q._data
        [3, 2]
        >>> q._front
        2
        >>> q._back
        1
        >>> q._eol
        True
        >>> q.dequeue()
        2
        >>> q._data
        [3]
        >>> q.dequeue()
        3
        >>> q.is_empty()
        False
        >>> q._data
        [4]
        >>> q._buffer
        []
        >>> q._front
        0
        >>> q._back
        0
        '''
        self._data = []
        self._front = 0
        self._back = -1
        self._buffer = []
        self._dequeuing = False
        self._eol = False
    
    def enqueue(self: "Queue", x: object) -> None:
        '''Place x at the back of the Queue'''
        
        # When you enqueue before dequeuing, the _back is moved to the very end
        if not self._dequeuing:
            self._back = self._back + 1
            self._data.append(x)
        else:
            # Enqueuing in the middle of dequeuing adds to the buffer
            self._buffer.append(x)
        
    def dequeue(self: "Queue") -> object:
        '''Remove and return the object at the front of the Queue'''
        if self.is_empty():
            raise Exception ("Queue is empty.")
        
        # Record when we begin to dequeue
        self._dequeuing = True
        
        
        # If we are not at the end of the list, we dequeue by swaping
        if not self._eol:
            # When you dequeue, we want to swap the front and the back.
            self._data[self._front], self._data[-1] = self._data[-1], \
                self._data[self._front]
            
            self._back = self._front
            self._front = self._front + 1
        # Otherwise, we need to only pop from the end   
            
        return_buffer = self._data.pop()
        
        # Check whether we're at the end of the list
        if self._front >= len (self._data) - 1:
            self._eol = True
        
        if self.is_empty():
            # When the queue is empty, we put in the buffer and reset variables
            self._data = self._buffer
            self._buffer = []
            self._eol = False
            self._dequeuing = False
            self._front = 0
            self._back = len(self._data) - 1 
            if self._back < 0:
                self._back = 0
        return return_buffer
        
    def is_empty(self: "Queue") -> bool:
        '''Return whether or not the Queue has no objects'''
        return len(self._data) == 0
        
    def front(self: "Queue") -> object:
        '''Return the object at the front of the Queue'''
        return self._data[self._front]
    
if __name__ == "__main__":
    import doctest
    doctest.testmod()

As a foot note, I noticed that my writing style is very casual, whereas some people write in a very formal manner. Being that this is a blog, would you prefer that I write casually or formally? Please let me know!