Stack or Not?

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

It's not a stack because it's not LIFO, you have complete control of where the items are get/set it's just a normal list imho.

Answer 2

It might look like an ADT, but it just sounds like an array.

Answer 3

IMO it's a stack as long as it supports Push and Pop. It doesn't matter if it also supports other actions.

Answer 4

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.

Answer 5

If its not a LIFO object it can't be qualified as a Stack. I would say its simply a List with Push Pop functionality which again is nothing but AddAtEnd() and RemoveFromEnd()

Answer 6

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 7

Your data structure can be used as a stack.. or as an array/list..
Stack is just a specialized form of a list.. and your implementation appears to negate that specialness.. so I would lean towards calling it a list instead of a stack.

Answer 8

Actually if you can only Pop and Push elements you can still see it as Stack. A more flexible stack.