algorithm - How can you simulate an array with two unbounded stacks and a small amount of memory? -

i going through past slides of 1 of courses being offered in university.

here slide mentions question: http://www.cse.psu.edu/~asmith/courses/cse565/f10/www/lec-notes/cse565-f10-lec-03.pptx.pdf

however, not sure if correctly understand question , clueless on solution.

any pointers on problem , how think it?

to simulate array need allow indexed lookup.

insert:

given 2 unbounded stacks, call them foo , bar, can keep inserting foo.

lookup:

when user tries lookup element, pop stack.size - index times bar. next pop give element user looking for. @ point can peek instead of pop because array not delete elements on lookup.

now can either push elements onto foo bar or push rest of elements bar onto foo. in latter case, need reverse indexing.

delete:

to implement delete can mark element deleted. if user ever tries inserting element @ index can pop , push new element. whereas on lookup should return whatever represents empty index.