How to keep track of changes done to concurrent stacks?

Question

I am writing a small RPN calculator that works on some stacks concurrently. For example, if I have two functions:

add-int(a: int, b: int): a b +
add-float(a: float, b: float): a b +

and I have two stacks with the following:

Int [1 2 3]
Float [4.0 5.5]

I can just do:

add-int add-float

and the new stacks will be:

Int [1 5]
Float [9.5]

Everything works well there, but if I were to add parametric polymorphism with this function:

add-num(a: num, b: num): a b +

Then it would not work as one would expect. Is it going to add the two integers or the two floats? or perhaps one from each?

To solve the issue, I added a new stack Num that keeps the address of every number pushed into the other stacks to keep a sense of history, but it created two new issues.

First, memory addresses take a lot of space, sometimes more than the data itself, and this would only get worse if I were to add new number types like ratios and complex.

Second, what if I wanted to pop a number that is on top of the stack for its type but way behind in the Num stack.

For example:

> 1 2 3.14 4.0 5/5  -- This is the expression.
Int [1 2]  -- These are the stacks.
Float [3.14 4.0]
Ratio [5/5]
Num [&Int[0] &Int[1] &Float[0] &Float[1] &Ratio[0]]

> add-int  -- Then I do this.

If I call the function above, there is no issue popping the two integers, but what about deleting the two pointers in the Num stack? It can get pretty expensive to look for the element and remove it every single time a number is popped.

I have realized that this approach is not pretty effective in terms of space consumption and performance, so is there an alternative, more efficient way of keeping track of the changes done to these stacks?

Answer 1

I would use doubly-linked lists instead of opaque stacks for this.

Node = {
    type : "INT" or "FLOAT"
    value : int or float
    prev-generic : pointer to Node
    next-generic : pointer to Node
    prev-specific : pointer to Node
    next-specific : pointer to Node
}

Now you can keep three lists: a list of ints (using the specific pointers), a list of floats (using the specific pointers), and a list of both (using the generic pointers). If you keep track of the head of each list, you can treat them as stacks (pushing and popping in $O(1)$), and a popped node can also be deleted from both stacks in $O(1)$ just like in a normal doubly-linked list.