CODEWITHSUNDEEP
scala
user1002579
user1002579

Reputation: 129

Enqueue method of the queue implementation using an array in Scala

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.

Upvotes: 1

Views: 843

Answers (2)

huynhjl
huynhjl

Reputation: 41646

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.

Upvotes: 2

Didier Dupont
Didier Dupont

Reputation: 29528

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

  1. 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
  2. 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.
  3. 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

Upvotes: 2

Related Questions