Why is the (non-generic) Stack class implemented as a circular buffer? (and what does that mean exactly)?

StackOverflow https://stackoverflow.com/questions/16955883

  •  31-05-2022
  •  | 
  •  

Question

The non-generic Stack class states "Stack is implemented as a circular buffer."

I don't understand the application of a circular buffer to a Stack use case. I also don't understand how stack could be implemented as as circular buffer.

Wikipedia says this:

The useful property of a circular buffer is that it does not need to have its elements shuffled around when one is consumed. (If a non-circular buffer were used then it would be necessary to shift all elements when one is consumed.) In other words, the circular buffer is well suited as a FIFO buffer while a standard, non-circular buffer is well suited as a LIFO buffer.

Circular buffering makes a good implementation strategy for a queue that has fixed maximum size.

So...how is stack implemented as circular buffer, and why?

Was it helpful?

Solution

I suspect that is a copy/paste/edit error in the documentation; looking in reflector, it is not implemented as a circular buffer; for example push is (after the resize code) basically:

this._array[this._size++] = obj;

peek is:

return this._array[this._size - 1];

and pop is:

object value = this._array[--this._size];
this._array[this._size] = null;
return value;

Note it doesn't use any kind of offset/wrap-around - so it is not actually using a circular buffer. Your instinct looks right, but the documentation looks wrong.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top