Is the rear item in a Queue the last item added or the item at the end of a Queue?

Question

My professor wrote a Queue class that uses arrays. I was giving it multiple test cases and got confused with one specific part. I want to figure out if the last item added is the rear of the queue. Lets say I enqueued 8 elements:

[1, 2, 3, 4, 5, 6, 7, 8]

Then I dequeued. And now:

[None, 2, 3, 4, 5, 6, 7, 8]

I enqueued 9 onto the Queue and it goes to the front. However, when I called my method that returns the rear item of the queue, q.que_rear, it returned 8. I thought the rear item would be 9? Since it was the last item added.

Here is how I tested it in case anyone is confused:

>>> q = ArrayQueue()
>>> q.enqueue(1)
>>> q.enqueue(2)
>>> q.enqueue(3)
>>> q.enqueue(4)
>>> q.data
[1, 2, 3, 4, None, None, None, None]
>>> q.dequeue()
1
>>> q.enqueue(5)
>>> q.enqueue(6)
>>> q.enqueue(7)
>>> q.enqueue(8)
>>> q.data
[None, 2, 3, 4, 5, 6, 7, 8]
>>> q.enqueue(9)
>>> q.data
[9, 2, 3, 4, 5, 6, 7, 8]
>>> q.que_rear()
Rear item is 8

EDIT I just want to know what’s supposed to be the “rear of the Queue”? The last element added, or the element at the end of the list? In this case I showed, is it supposed to be 8 or 9?

Here is my code:

class ArrayQueue:
    INITIAL_CAPACITY = 8
    def __init__(self):
        self.data = [None] * ArrayQueue.INITIAL_CAPACITY
        self.rear = ArrayQueue.INITIAL_CAPACITY -1
        self.num_of_elems = 0
        self.front_ind = None

    # O(1) time
    def __len__(self):
        return self.num_of_elems

    # O(1) time
    def is_empty(self):
        return len(self) == 0

    # Amortized worst case running time is O(1)
    def enqueue(self, elem):
        if self.num_of_elems == len(self.data):
            self.resize(2 * len(self.data))

        if self.is_empty():
            self.data[0] = elem
            self.front_ind = 0
            self.num_of_elems += 1
        else:
            back_ind = (self.front_ind + self.num_of_elems) % len(self.data)
            self.data[back_ind] = elem
            self.num_of_elems += 1

    def dequeue(self):
        if self.is_empty():
            raise Exception("Queue is empty")
        elem = self.data[self.front_ind]
        self.data[self.front_ind] = None
        self.front_ind = (self.front_ind + 1) % len(self.data)
        self.num_of_elems -= 1

        if self.is_empty():
            self.front_ind = None
        # As with dynamic arrays, we shrink the underlying array (by half) if we are using less than 1/4 of the capacity
        elif len(self) < len(self.data) // 4:
            self.resize(len(self.data) // 2)
        return elem

    # O(1) running time
    def first(self):
        if self.is_empty():
            raise Exception("Queue is empty")
        return self.data[self.front_ind]

    def que_rear(self):
        if self.is_empty():
            print("Queue is empty")
        print("Rear item is",  self.data[self.rear])

    # Resizing takes time O(n) where n is the number of elements in the queue
    def resize(self, new_capacity):
        old_data = self.data
        self.data = [None] * new_capacity
        old_ind = self.front_ind

        for new_ind in range(self.num_of_elems):
            self.data[new_ind] = old_data[old_ind]
            old_ind = (old_ind + 1) % len(old_data)
        self.front_ind = 0

Answer 1

The que_rear function seems to be added post-hoc in an attempt to understand how the internal circular queue operates. But notice that self.rear (the variable que_rear uses to determine what the "rear" is) is a meaningless garbage variable, in spite of its promising name. In the initializer, it's set to the internal array length and never gets touched again, so it's just pure luck if it prints out the rear or anything remotely related to the rear.

The true rear is actually the variable back_ind, which is computed on the spot whenever enqueue is called, which is the only time it matters what the back is. Typically, queue data structures don't permit access to the back or rear (if it did, that would make it a deque, or double-ended queue), so all of this is irrelevant and implementation-specific from the perspective of the client (the code which is using the class to do a task as a black box, without caring how it works).

Here's a function that gives you the actual rear. Unsurprisingly, it's pretty much a copy of part of enqueue:

def queue_rear(self):
    if self.is_empty():
        raise Exception("Queue is empty")

    back_ind = (self.front_ind + self.num_of_elems - 1) % len(self.data)
    return self.data[back_ind]

Also, I understand this class is likely for educational purposes, but I'm obliged to mention that in a real application, use collections.dequeue for all your queueing needs (unless you need a synchronized queue).

Interestingly, CPython doesn't use a circular array to implement the deque, but Java does in its ArrayDeque class, which is worth a read.