  The (classical) problem of characterizing and enumerating permutations that
can be sorted using two stacks connected in series is still largely open. In
the present paper we address a related problem, in which we impose restrictions
both on the procedure and on the stacks. More precisely, we consider a greedy
algorithm where we perform the rightmost legal operation (here "rightmost"
refers to the usual representation of stack sorting problems). Moreover, the
first stack is required to be $\sigma$-avoiding, for some permutation $\sigma$,
meaning that, at each step, the elements maintained in the stack avoid the
pattern $\sigma$ when read from top to bottom. Since the set of permutations
which can be sorted by such a device (which we call $\sigma$-machine) is not
always a class, it would be interesting to understand when it happens. We will
prove that the set of $\sigma$-machines whose associated sortable permutations
are not a class is counted by Catalan numbers. Moreover, we will analyze two
specific $\sigma$-machines in full details (namely when $\sigma=321$ and
$\sigma=123$), providing for each of them a complete characterization and
enumeration of sortable permutations.
