"A stack is certainly the most intuitive data-structure with which to implement a lambda calculus."

This depends on the evaluation order. I think you are talking about call-by-value (eager) or call-by-name orders.

But normal order evaluation with memoization (what human computer would do - write result only once) uses graphs and graph rewriting.