stack-sortable

Recall a stack (data structure), or a LIFO (last in first out) data structure. Given a permutation, it is stack sortable if there is some sequence of stack operations that sorts the permutation.

Examples

ex: 4 1 3 2 is stack-sortable:
- push 4
- push 1
- pop 1
- 1
- push 3
- push 2
- pop 2
- 1 2
- pop 3
- 1 2 3
- pop 4
- 1 2 3 4

nonex: 2 3 1
and it turns out that all permutations of 1, 2, 3 are stack-sortable except for this one

Properties

A permutation is stack-sortable if and only if it is 2, 3, 1 - avoidant