Stack A has the entries a, b, c (with a on top). Stack B is empty. An entry…

Concept

A stack follows the last-in, first-out (LIFO) rule: the most recently pushed entry is the first one popped. When several entries from one stack are pushed onto a second stack, the second stack later prints those entries in reverse of their push order.

Because an entry popped from Stack B must be printed, the relative order of entries already in Stack B cannot be rearranged.

Application

1. To print c before a and b, neither a nor b can be printed while removing them from Stack A; both must be pushed to Stack B.

2. Push a to Stack B. Then push b. Stack B is now top-to-bottom [b, a].

3. Pop c from Stack A and print it. Stack A is now empty, while b remains above a in Stack B.

4. The next pop from Stack B must print b, and the following pop prints a. Thus every output that starts with c must continue as c, b, a.

5. The ordering c, a, b asks Stack B to print a while b is still above it, which violates LIFO. Therefore c, a, b cannot be produced.

Cross-check

• b, a, c can be produced by pushing a to Stack B, printing b, printing a from Stack B, and then printing c.

• b, c, a can be produced by pushing a to Stack B, printing b and c from Stack A, and then printing a from Stack B.

• a, b, c can be produced by printing each entry directly as it is popped from Stack A.

• c, a, b conflicts with the forced top-to-bottom order [b, a] in Stack B after c is printed.

Result

The permutation c, a, b is not possible.