2
$\begingroup$

With a stack, you can push and you can pop. There's also a generalization, let's call it a foo, in which key-value pairs are involved. The idea is that instead of just pushing a value, we push a key-value pair, as in L.push(key, value). Similarly, to pop a value, we have to supple a key. As in L.pop(key).

A straightforward implementation can be obtained as follows: choose an implementation for the dictionary data type, and then define that a foo is a dictionary in which the values are linked stacks. So L.push(key, value) is executed by querying the dictionary for the stack associated with the key key and then pushing value onto that stack. Similarly L.pop(key) is executed by querying the dictionary for the stack associated with the key key and then popping the top value.

A different implementation that can be more space-efficient under some circumstances uses a single linked list, whose nodes are key-value pairs. To perform L.pop(key), we search through the linked list until the desired key is found, and then pop that particular node. In fact there's situations where this single-list implementation is actually more time-efficient*; in particular, if you're mainly pushing and popping items in the reverse order, avoiding the cost of hashing the key can meaningfully improve the speed up of the lookup.

(*) You can't improve the big-$O$ time-complexity like this, only the practical running speed.

Anyway, since this data structure appears frequently in some of my amateur research into the foundations of mathematics, I'd be interested in getting a name for it.

Question. Does the "dictionary of stacks" ADT have an accepted name?

$\endgroup$
2
$\begingroup$

The implementation with a linked list is called association list, or alist for short.

I don't think there's a universal term for the interface. I'd call it a dictionary with shadowing of keys (pushing (k,v2) when the data structure already contains (k,v1) shadows the existing binding for k).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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