Let $S1$ and $S2$ be two stacks. $S1$ has capacity of 4 elements. $S2$ has capacity of 2 elements. $S1$ already has 4 elements: 100, 200, 300, and 400, whereas $S2$ is empty, as shown below. Only the following three operations are available: PushToS2: Pop the top element from $S1$ and push it on $S2$. PushToS1: Pop the top element from $S2$ and push it on $S1$. GenerateOutput: Pop the top element from $S1$ and output it to the user. Note that the pop operation is not allowed on an empty stack and the push operation is not allowed on a full stack. Which of the following output sequences can be generated by using the above operations?

Initial state: $S_1 = [100, 200, 300, 400]$ (top is $400$, capacity 4), $S_2 = []$ (capacity 2).

• Option A ($100, 200, 400, 300$): To output $100$ first, all 3 elements above it ($400, 300, 200$) must be removed from $S_1$. Since $S_2$ has a capacity of only $2$, it cannot hold all three elements simultaneously. Thus, this sequence is impossible.

• Option B ($200, 300, 400, 100$):

  1. PushToS2 (moves $400$ to $S_2$)

  2. PushToS2 (moves $300$ to $S_2$)

  3. GenerateOutput$\rightarrow 200$

  4. PushToS1 (moves $300$ to $S_1$)

  5. GenerateOutput$\rightarrow 300$

  6. PushToS1 (moves $400$ to $S_1$)

  7. GenerateOutput$\rightarrow 400$

  8. GenerateOutput$\rightarrow 100$

  Valid.

• Option C ($400, 200, 100, 300$):

  1. GenerateOutput$\rightarrow 400$

  2. PushToS2 (moves $300$ to $S_2$)

  3. GenerateOutput$\rightarrow 200$

  4. GenerateOutput$\rightarrow 100$

  5. PushToS1 (moves $300$ to $S_1$)

  6. GenerateOutput$\rightarrow 300$

  Valid.

• Option D ($300, 200, 400, 100$):

  1. PushToS2 (moves $400$ to $S_2$)

  2. GenerateOutput$\rightarrow 300$

  3. GenerateOutput$\rightarrow 200$

  4. PushToS1 (moves $400$ to $S_1$)

  5. GenerateOutput$\rightarrow 400$

  6. GenerateOutput$\rightarrow 100$

  Valid.