Resizing of the circular queue using dynamic array

Question

I'm analyzing the following code for a long time, but still, I'm not getting this one function's one line which is as follows:

void ResizeQueue(struct DynArrayQueue* q) {
    int size = q->capacity;
    q->capactiy = q->capacity * 2;
    q->array = realloc(q->array, q->capacity);
    if (!q->array) {
        printf("Memory error");
        return;
    }

    // The doubt lines:
    if (q->front > q->rear) {
        for (int i = 0; i < q->front; i++) {
            q->array[i + size] = q->array[i];
        }
        q->rear = q->rear + size;
    }
}

My doubt to this above code is that, at what point in this dynamic array implementation of circular queue, the front become greater then the rear one?

Weather Vane · Accepted Answer · 2019-03-25 18:27:17Z

4

The reason is because it is a circular buffer. Suppose a buffer is length 8, here are two scenes A and B where 4 data items are in the buffer, using - to indicate irrelevant data and d to indicate buffered data:

index   0   1   2   3   4   5   6   7

A data  -   d   d   d   d   -   -   -
          begin        end

B data  d   d   -   -   -   -   d   d
           end                begin

So because - by definition of a circular buffer - the data wraps, the head might be lower than the tail, or the tail might be lower than the head.

Look what happens to buffer B when its length is doubled

index   0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15
B data  d   d   -   -   -   -   d   d   -   -   -   -   -   -   -   -
           end                begin

Now it should be plain why the data needs to be moved so it is like this:

index   0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15
B data  d   d   -   -   -   -   -   -   -   -   -   -   -   -   d   d
           end                                                begin

with the pointer or index adjusted accordingly.

Alternatively the data could be adjusted to look like this:

index   0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15
B data  -   -   -   -   -   -   d   d   d   d   -   -   -   -   -   -
                              begin        end

edited Mar 25, 2019 at 18:27

answered Mar 25, 2019 at 18:12

Weather Vane

34.8k7 gold badges43 silver badges63 bronze badges

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

8 Comments

vinodkumar wagh Over a year ago

very nicely explained, Got it, thank you very much!

AShelly Over a year ago

I don't think your last diagram is correct - the code leaves "begin = front" in place at 6, and moves the data from 0..5 into 8..13

Weather Vane Over a year ago

@AShelly the last line of the answer says "with the pointer or index adjusted accordingly."

AShelly Over a year ago

ok, but in the OP's code the move loop is for(int i = 0 ; i<q->front ; i++) - the first portion, not for (i=q-<front;i<size;i++) which would move the second portion.. I suppose an efficient implementation would chose whichever of those two ranges was smaller

Weather Vane Over a year ago

@AShelly the edit now shows the same part of the buffer moved as OP's code: there are two ways to adjust it.

|

AShelly · Accepted Answer · 2019-03-25 18:14:19Z

0

So the "front" is the read pointer, the next thing to be read. The "rear" is the write pointer, the last thing inserted.

Any time a circular queue has more than capacity elements inserted, rear wraps around to the beginning, and front > rear becomes true. That mechanism is what makes this a circular buffer.

If this resize code is called after that happens, it copies everything before the front read pointer into the new space at the end, and updates rear to point into that space.

(I think it would also be correct if it only copied elements upto rear. As written, it's copying stale elements.)

answered Mar 25, 2019 at 18:14

AShelly

35.9k17 gold badges98 silver badges163 bronze badges

Collectives™ on Stack Overflow

Resizing of the circular queue using dynamic array

2 Answers 2

8 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

8 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related