ITPEC FE Morning October 2018 Question 6

C, B, D, A — every element leaves when it is on top of the stack, so the order can be produced.

Input arrives A, B, C, D; at each step push the next input or pop the top.

• •Push A, B, C; pop C, then pop B; the stack holds A
• •Push D and pop it; the stack holds A
• •Pop A: output C, B, D, A

A sequence is impossible when it needs an element that has a later-pushed element still above it.

Answer (c)

Why not others:

• •(a) A, D, B, C — to output D after A, B and C must be pushed first; C then sits on top of B, so B cannot come out before C
• •(b) B, D, A, C — to output D after B, C is pushed on top of A, so A cannot come out before C
• •(d) D, C, A, B — D first means A, B and C are all stacked with B above A, so after D and C the next pop is B, not A

Key rule: From a stack, once an element is output, every element pushed before it that is still waiting must come out in reverse order of arrival.

Algorithm and Programming · AI-written, may contain errors