Are stacks and queues allowed to be iterated over, conceptually?
It “feels wrong” for some reason but I can't come up with a reason why it would be bad to see through the whole thing that's stacked/queued. Obviously no taking the element out of there, or inserting a new one somewhere in-between.
Are my senses off or is there a good explanation about why you should or shouldn't be allowed to iterate through stack/queue contents in a read-only manner?
"Stack" and "queue" are terms which are sometimes used to mean two different things, logical and physical.
In a strict sense, they are logical concepts, and by definition, they are only accessed a certain way, either by reading head or the tail of a FIFO or LIFO stream.
In a practical sense, they are physical data structures. For example, in c#, there are Stack<T> and Queue<T> classes available (along with concurrent-friendly versions of the same). For practical purposes, these classes have enumerators that allow to see all of the contents, as well as indexer properties that allow random access to any element in any order.
There are some contexts where this should not be done. For example, let's say you have invented a new language that is optimized for reading databases. A resultset might be exposed as a read-once queue that iterates over a database-side cursor. In this case, random access of the items in the queue would be a serious problem, because you can't move your database-side cursor backwards.
Another example-- the CPU's call stack. It is a LIFO structure that you literally cannot access randomly because each item in the stack is a different size, and there is no way to figure out what size it is without reverse engineering each subroutine. Code is able to use this stack effectively only because each subroutine knows how to deallocate its own stack frame.
So at a logical level, you are right-- queues and stacks are read in a certain way, by definition. On a physical level, sometimes it is fine to use random access, but sometimes it is not fine, and sometimes it is not possible.
There are situations where it would make absolute sense to iterate through a queue. Let’s say there’s a queue of tasks, but the user cancelled one action, and now you want to delete all entries in the queue related to that action. Probably the same for a stack. You usually inspect just the top of the stack, but there’s no law saying you can’t be interested in all items if the stack.
And in these examples, removing items would also be quite reasonable. But there is of course the question what the creator of the stack or queue class allows you to do easily, and preferably without any horrible hacks. (Objective-C used to implement them both as plain mutable arrays, so you could access everything if you wanted to).
Usage Standpoint
Most of the time from a usage standpoint, I think our predominant concerns in reasoning about a codebase is concerned with write patterns, not reads. So even a queue or stack which provides read-access through the entire container via iterators often still provides the lion's share of the benefits of reasoning about code using it, as it offers the guarantee at a glance that we won't suddenly finding elements being removed to/from the middle, e.g. There's a great deal of clarity to be found in merely constraining write ability.
But at least in my domain, it often has little benefit to clarity and often serves as a hindrance if a queue or stack structure fails to provide the ability to iterate over its elements for read-only access. Many of our use cases involve building a stack or queue and then, after we're done building it, iterating over the results and treating it like a read-only sequence (often even a random-access sequence we read in a parallel loop which is impossible to do with the container if it can only read in serial FIFO/LIFO patterns without popping everything off of it first and transferring the results to a random-access container).
That's a very common case requirement in what I've encountered at least and not an obscure one. So to have to, in such use cases, build a queue or stack and then read and pop each element until the container is empty tends to be quite inefficient both for the programmer and the hardware; it also turns what could otherwise be a read-only operation just wanting to read the contents of the container into a write operation which requires modifying it.
A Proposal of How To Think About It To Make It Feel More Right
To require popping to read the container is generally going to make the code harder to understand, not easier, with more places in your code superfluously modifying data it wouldn't otherwise have to modify and less code merely reading it for immutable access[*]. So even if it seems to feel wrong and a violation of LIFO/FIFO access patterns to provide iterators for a queue or stack when you can effectively provide them, I'd keep this in mind that you might be introducing more code needlessly mutating data in your codebase which can make it more difficult to understand, multithread, and test if you don't.
- Remember that it's mostly reducing writes in our codebase, not reads, that tends to add to the clarity of the code. Exchanging more write operations for less read-only operations when you're completely free to do either tends to be a counter-productive trade-off except possibly in some very obscure cases.
Implementation Standpoint
That said, as pointed out in the John Wu's answer, there are far more implementation reasons to constrain even the read access of a queue or stack even though I just tried to propose why it might often hinder usability.
As another example besides his, a concurrent queue or stack might -- in order to provide the most efficient and atomic LIFO/FIFO push/pops -- require constraining reads in a similar fashion. There the most efficient implementation might require the people implementing the write operations to be able to make guarantees about what the readers can't access as they are modifying the data structure. It's a lot easier to implement a concurrent queue or stack efficiently if we're guaranteed that user can only push and pop from it, not read from it in ways outside of popping off the top/front element.
So I think there are far more implementation reasons to limit reads as well to LIFO/FIFO patterns, but I don't think it adds that much clarity to most codebases to impose such constraints on the users when the implementation doesn't benefit from it. At least in most of the cases I've encountered, that would serve more as an obstacle than something that lets us reason about the code using the queue or stack more easily.
Abstraction Standpoint
Another thing to keep in mind though also in favor of constraining reads is for generalized code where you might have a variety of queue/stack implementations offering the same interface. That common interface might only be able to provide a subset of what any single implementation is able to provide for them to all uniformly conform to the same interface.
I don't think there's anything "wrong" with it. In my experience, you choose to work with a stack or queue instead of a list because it supports that pattern you need to use for processing the data. That said, finding out if something is in the queue will certainly be a scan operation - contains() is just going to iterate over the data under the hood. I suspect the reason it feels "wrong" is that use case doesn't seem to emerge frequently in the situations where we choose to use a stack or queue. I think when I do use those patterns, it's more about managing order of operations and less about finding out what might be in line already.
