CODEWITHSUNDEEP
data-structuresqueuecircular-buffer
Surya Teja Vemparala
Surya Teja Vemparala

Reputation: 499

Circular Queue using Dynamic Array

I'm learning data structures from a "Fundamentals of Data structures in C" by Sahni. In the topic, Circular Queue using Dynamic Array, the author has mentioned below point,

Let capacity be the initial capacity of the circular queue,We must first increase the size of the array using realloc,this will copy maximum of capacity elements on to the new array. To get a proper circular queue configuration, we must slide elements in the right segment(i.e, elements A and B) to the right end of the array(refer diagram 3.7.d). The array doubling and the slide to the right together copy at most 2 * capacity -2 elements.

I understand array doubling copies at most capacity elements. But how does array doubling and slide to right copy at most 2 * capacity -2 elements?? enter image description here

Upvotes: 1

Views: 2528

Answers (1)

Deepak Tatyaji Ahire
Deepak Tatyaji Ahire

Reputation: 5311

Let us try to justify worst case scenario:

For a queue with capacity = N, there are maximum N-1 elements present in the queue.

So, when we double the queue size, we need to copy all these N-1 elements to new queue, and at max there can be N-1 shifts(for elements).

So in total, 2*(N-1) = 2*N - 2

Upvotes: 0

Related Questions