Is Stack with PushAt/PopAt still a Stack?

Question

Lets say I have a Data Structure similar to Stack but in addition to usual Push/Pop it also has functions such as PushAt/PopAt both of which takes an integer as input and adds/returns the item at that particular location in data structure.

Now Stack is suppose to be LIFO. Does this data structure qualify as "Stack"?

Answer 1

In HP RPN calculators and in Postscript/PDF, other operators than push and pop exist:

• swap or exch for permuting top of stack and next element,
• roll as an extension of swap

Their main data structure is still considered a stack.

pushAt and popAt can be written only with pop/push and roll. So your data structure can still be named stack.

Answer 2

Technically not. LIFO means (as you know) last-in, first-out. If the last element going in isn't the first to come out, it doesn't satisfy the "semantic interface" (or contract) of a stack.

However, since it seems like you are only adding additional methods and not modify the existing ones your data structure could be used interchangeably with a stack if it is being used like one, i.e. pushAt() and popAt() are never called (for instance because they are "hidden" by passing it as a Stack to a function).

So in that sense your version is a stack in the same way that a list is a stack in Java, for example. It can be used as one, but it can also do other things.