1
$\begingroup$

It seems to be a popular opinion that "the right way" to implement undo/redo is "using a stack." (particularly in the context of an algorithms and data structures interview.)

Here's a GeeksForGeeks article as one reference on this view.

A common variation on this problem is "suppose we want to be able to do many undo or redo operations in a row." (I would argue this feature could be implied in the original question, but it seems that is not the popular view.)

I asked a group about how to solve this and the overwhelming answer from those with a traditional CS background was "use two stacks."

My question here is: Is there any benefit two using two stacks over using an array with a pointer?

It seems to me two stacks is isomorphic to an array with two pointers, but we really only need one pointer so that would be a more efficient approach.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ I don't understand why you'd want or need two stacks, or how they would help. I've never heard the "use two stacks" advice. It may be hard to answer this without knowing their justification. What justification did they provide? Can you provide a reference to where that claim appears? Or, alternative, maybe it's better to just ask how to accommodate many undo/redo operations in a row and let people here answer as they may. You might need to give a bit more context: why have you rejected the simple one-stack solution? $\endgroup$
    – D.W. ♦
    Jan 22, 2022 at 1:14
  • $\begingroup$ @D.W. Thanks. One person suggested two stacks “models the problem better.” I thought it was a fair enough response although it seems to be let’s say a nonclassical optimization rule $\endgroup$
    – John Vandivier
    Jan 22, 2022 at 14:36

1 Answer 1

Reset to default
1
$\begingroup$

A stack can be, and usually is, implemented using an array and a top-of-stack pointer. It isn't an alternative to an array, but just another (more abstract) way of talking about the array and the specific access pattern needed for this task.

The reason for using two stacks is probably that the undo and redo information for the same change may have different sizes. The most memory-efficient approach is to store only the one that you need, and store it directly on the stack (in the array) rather than allocating a heap object for each change. That means you may end up pushing more or less data than you popped, so you need two pointers.

Improve this answer
$\endgroup$
1
  • $\begingroup$ thanks for the response! I’m not sure why the idea that undo/redo can have different sizes leads us to have two stacks. They should always sum to the same number of events (you can only undo+redo up to the latest action) so again it seems isomorphic to an array with a pointer (that is not always pointing to the end of the array) maybe there is some hidden assumption that arrays are fixed size? For sure we will push more than pop, don’t see how that indicates two pointers. W two stacks we can desync state inappropriately $\endgroup$
    – John Vandivier
    Jan 22, 2022 at 14:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.