Enqueue method of the queue implementation using an array in Scala

Question

def enqueue(elem: T): Unit = {      
    A(rear) = elem
    rear += 1
    size += 1
    if (size == 0) {
        front = 0 
        rear = 0
        }
    if (size == A.length) {
        grow()
        }   
    }

I am implementing a queue using an array and I have some problem in enqueue method, but I couldn't figure out where the mistake exactly is. So can you please give me some hints on where I did a mistake. In the code above size is the number of elements in the arrayqueue, grow is the function that doubles the array when it is full. Thank you in advance.

Didier Dupont · Accepted Answer · 2011-10-19 07:22:11Z

You're not telling anything about what gets wrong so this is a shot in the dark, and not discussing the chosen data structure.

The test size == 0 seems useless, the size will not be zero just after an enqueue. However what you do is telling on what you do when a dequeue happens, likely return the element at front and increment front, and decrement size.

So a few remark

It is surprising to call grow preventively, for the next call to enqueue that might never happen. You should probably do it at the very start of enqueue when you lack space
Your data move to the right of the array as you dequeue and enqueue again. So even in a queue with very few items (size is small), the items can be at the right edge of the array, and you may run out of space. The test for grow (or at least for doing something) should be on rear rather than on size.
As a consequence you may have to grow, or at least do something, even if the array has much more space than needed. If the array is nearly full, you should grow indeed (even if there is some space left, otherwise you risk the enqueue/dequeue cycles to keep copying all the values and have your performances go O(N)) But if there is a lot of free space, you should simply move the elements back to the start of the array.

Summary: at the start of enqueue, if rear is at array length, you must

if size is less than say half the space, copy the elements to the start of the array, front=0, rear = size
if size is bigger, allocate a new array and copy the elements at the start of the new array

huynhjl · Accepted Answer · 2011-10-19 07:25:57Z

2

If you are going to test for size == 0, you should do that first.

It may help you if you document the invariants of your class and the pre-conditions and post-conditions of your methods to ensure that each methods is preserving the key properties of you queue implementation internals. See http://en.wikipedia.org/wiki/Design_by_contract.

An invariant could be something like size is always less or equal to the array length or size >= 0.

answered Oct 19, 2011 at 7:25

huynhjl

41.7k14 gold badges108 silver badges159 bronze badges

1 Comment

Didier Dupont Over a year ago

+1 for invariants and contracts, great advice from CS 101 and all the way beyond.

Collectives™ on Stack Overflow

Enqueue method of the queue implementation using an array in Scala

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related