The "pushdown store," or "stack," is a storage structure that operates much like a set of plates stacked on a spring in a cafeteria. All storage locations are initially empty. An item of data is added to the top of the stack by a "push" instruction, which pushes any previously stored items farther down in the stack. Only the topmost item on the stack is accessible at any moment, and it is fetched and removed from the stack by a "pop" instruction.

Let's consider strings of integers that are an even number of characters in length; half the characters are positive integers, and the other half are zeros. We process these strings through a pushdown store as

$410$

Relations, Functions, and Matrices

follows: As we read from left to right, the push instruction is applied to any nonzero integer, and a zero causes the pop instruction to be applied to the stack, thus printing the popped integer. Thus, processing the string $12030040$ results in an output of $2314,$ and processing $12304000$ results in an output of $3421.($A string such as $10020340$ cannot be handled by this procedure because we cannot pop two integers from a stack containing only one integer.$)$ Both $2314$ and $3421$ can be thought of as permutations,

$([1,2,3,4],[2,3,1,4])$ and $,([1,2,3,4],[3,4,2,1])$

respectively, on the set $A=\{1,2,3,4\}.$

a$.$ What permutation of $A=\{1,2,3,4\}$ is generated by applying this procedure to the string $12003400?$

b$.$ Name a permutation of $A=\{1,2,3,4\}$ that cannot be generated from any string where the digits $1,2,3,$ and $4$ appear in order, no matter where the zeros are placed.