The difference is in the name. Stack allocation is strictly FIFO [1], so it can be implemented very efficiently with just incrementing and decrementing a stack

The difference is in the name. Stack allocation is strictly FIFO [1], so it can be implemented very efficiently with just incrementing and decrementing a stack pointer, even on architectures that don't directly have an hardware stack. In principle that stack for local variables doesn't even need to be the same stack as the callstack. It is also strictly thread local. On the other hand an heap (which has nothing to do with the heap data structure) is much more complex. [1] At least across activation frames, of course a compiler can statically generate code that reuses frame slots in a non-FIFO way.