Circular Array-Based Queue Insert Class Method - Python

Question

I am trying to implement the insert method of a circular array-based queue, however am unable to update the rear of the queue. Here is my code:

def __init__(self, max_size):

"""
        -------------------------------------------------------

        Initializes an empty queue. Data is stored in a fixed-size list.
        Use: cq = Queue(max_size)
        -------------------------------------------------------
        Parameters:
            max_size - maximum size of the queue (int > 0)
        Returns:
            a new Queue object (Queue)
        -------------------------------------------------------
        """
        assert max_size > 0, "Queue size must be > 0"

        self._max_size = max_size
        self._values = [None] * self._max_size
        self._front = 0
        self._rear = 0
        self._count = 0
def insert(self, value):

        '''-------------------------------------------------------
        Adds a copy of value to the rear of the queue.
        Use: cq.insert( value )
        -------------------------------------------------------
        Parameters:
            value - a data element (?)
        Returns:
            None
        -------------------------------------------------------'''
        assert (self._count < self._max_size), 'queue is full'
        self._values.append(deepcopy(value))
        self._count += 1
        self._rear = (self._rear - 1) % self._count
        return

Any suggestions?

edit: here is the remove implementation:

def remove(self):

        '''-------------------------------------------------------
        Removes and returns value from the queue.
        Use: v = cq.remove()
        -------------------------------------------------------
        Returns:
            value - the value at the front of the queue - the value is
                removed from the queue (?)
        -------------------------------------------------------'''
        assert (self._count > 0), 'Cannot remove from an empty queue'
        value = self._values[self._front]
        self._front = (self._front + 1) % self._count
        self._count += -1
        return value

Please explain what you mean by "unable to update the rear of the queue". Does that mean that you're adding more to the queue than its max_size? You didn't include any function that removes from the queue; do you have one? (It may help to read up on providing a minimal reproducible example.) You may also benefit from taking the tour, and reading up on How to Ask. — Scott Mermelstein
– Scott Mermelstein, Commented Oct 16, 2018 at 19:47
@ScottMermelstein What I mean is that when a value is added to the queue, self._rear is not updated properly. The value I insert is not added to the rear of the queue — sgill0
– sgill0, Commented Oct 16, 2018 at 19:54
General advice - try printing the value of self._rear after you set it, so you can see if it's behaving the way you expect. Then you can look and see if self._values[self._rear] (not self._rear) is the value you expect it to be. Offhand, I would question strongly if your % self._count does what you expect it to. — Scott Mermelstein
– Scott Mermelstein, Commented Oct 16, 2018 at 20:00

Aaron · Accepted Answer · 2018-10-16 21:45:20Z

1

When you add items by appending, you are extending your list beyond the max length that you pre-allocated it to. You then update self._rear as if you were going to use it as the insert index, but never actually use it for anything. I have implemented your code with only very minor changes beyond variable names (in order to make more sense to me), and utilizing self._rear (now: self._write_cursor) in the way I believe you intended.

class CQ: #Circular Queue
    def __init__(self, maxsize): 
        self._maxsize = maxsize
        self._write_cursor = 0
        self._read_cursor = 0
        self._len = 0
        self._values = [None] * maxsize

    def insert(self, item):
        if self._len < self._maxsize:
            self._values[self._write_cursor] = item
            self._write_cursor = (self._write_cursor + 1) % self._maxsize
            self._len = self._len + 1
        else:
            raise IndexError('can\'t push to full queue')

    def remove(self):
        if self._len > 0:
            out = self._values[self._read_cursor]
            self._read_cursor = (self._read_cursor + 1) % self._maxsize
            self._len -= 1
            return out
        else:
            raise IndexError('can\'t pop from empty queue')

edited Oct 16, 2018 at 21:45

answered Oct 16, 2018 at 21:31

Aaron

11.2k1 gold badge27 silver badges43 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Aaron Over a year ago

@ScottMermelstein I see where your're coming from. I tend to associate "push" and "pop" with any lifo data structure, and generally don't bother to make the change when it's fifo like here.

Collectives™ on Stack Overflow

Circular Array-Based Queue Insert Class Method - Python

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related