Wrap-around Indexing in Deques
If you’ve ever had to write an implementation of a queue using a circular array, you’d be familiar with this formula:
Here, last is the index of the last element in your queue and N is the size of length of the underlying array for your queue. This formula allows you to calculate a position for your new element without throwing an index error by “wrapping around” the right-end of the array to the left-end. For instance, if N = 5 and the current r = 4, then the new r = 0.
If you’d like to implement a deque (double-ended queue) using a circular array, you’ll need another formula to wrap around the left-end of your array to the right-end for your
push method. I derived a formula to use in that case:
For example, if N = 5 and the current f = 0, then the new f = 4.
Note: in both formulas, before using the new index you should have checked if the new index is available. One way to do this is by checking if the number of elements in your data structure equals the length of the circular array. Hope this helps!