How do you design a circular queue with a fixed capacity, and what is the tricky part?
You use a fixed size list and you treat it as a ring. Two pointers do the work. One points at the next place to put an item, and the other points at the next place to take an item from.
So how does the ring work? The list has a fixed length. When you add an item you put it at the position of the front pointer and then you move that pointer one place on. And when you reach the end of the list you wrap round to the start again.
the list has 5 places
index 0 1 2 3 4
[ ] [ ] [a] [ ] [ ]
the front pointer is at 2 and the back pointer is at 2
And the wrapping is done with the modulo operator. The index (self.front + 1) % self.capacity goes to the next place, and when the front pointer is at the last place then the modulo sends it back to zero.
And what is the tricky part? There are two of them, and they are both about telling full from empty.
The first one is that a ring array cannot tell the difference between a full queue and an empty queue by looking at the pointers alone. When the front pointer and the back pointer are equal, the queue is either empty or full. Most designs solve this by giving up one place, so the queue can hold one less than the size of the array.
the design how it tells full from empty
---------------------- -------------------------------------
one place is wasted the count variable says which it is
a flag is kept a separate boolean says which it is
the count variable the number of items is always known
The second tricky part is making sure that the pointers are only moved when there is room, so that you never write over an item that has not been taken out.
And the operations are O of 1 each, which is the target. The push, the pop and the peek are all constant time because every one of them touches a fixed number of places.
So the rule to remember is this. The pointers wrap round with the modulo operator, and you need something extra to tell full from empty.
The last question in this topic shows the code.