Scroll Data Structure

Has anybody heard of or used a scroll data structure? Can somebody explain it works?

I saw it in my lecture notes, but no mention of how开发者_开发问答 it worked. It was mentioned alongside sequences stacks and queues

I suspect this isn't a canonical name for a data structure since it's not on the NIST data structures and algorithms page (not that this page represents any such authority on the subject).

However, being described as a stack-queue hybrid from the few slides I could find on Google about it, it doesn't leave too much to the imagination once fusing the two abstract data types and extrapolating from the name "scroll".

Basically, we're talking about a double-ended queue (or double-ended stack, if you prefer) here. You can pop/push (enqueue/dequeue) and peek from either side but cannot access the middle. Think of an actual scroll -- you just unwind the paper to make more space at either end. It's not clear to me if there is an actual "head" node (somewhere in the middle where you can't move either the queue or stack beyond), but I'd suspect not. (After all, you can put a scroll wherever you like in the paper.)

You can look up more on double-ended queues on Google and such and you'll find a plethora of information.

On the other hand, a link very tersely mentions two versions of a "scroll": that as mentioned above and that as mentioned above except you can only dequeue from the 'front'.

This leads me to believe that the 'hybrid' notion is a very loose one, hence the lack of definition which is leaving you a bit queasy. In either case, scrolls are a well understood structure, just by a different name depending on the variant.