二、假設一堆疊（Stack）的推入（Push）順序為：123、234、345、456、567， 並且途中可以隨意彈出（Pop）取值，則下列彈出（Pop）取值之順序有 無可能出現？
345、567、456、234、123
若有可能，請依序將推入（Push）與彈出（Pop）的步驟列出。若無可能， 請解釋原因為何？（25 分）

詳解 (共 1 筆)

詳解 提供者：hchungw

根据栈的后进先出（Last In First Out, LIFO）的特性，我们可以检查给定的弹出顺序是否可能发生。

给定的推入（Push）顺序为：123、234、345、456、567

要达到弹出（Pop）顺序：345、567、456、234、123

我们尝试模拟这个过程：

  1. Push 123
  2. Push 234
  3. Push 345
  4. Pop 345（到目前为止可能）
  5. Push 456
  6. Push 567
  7. Pop 567（到目前为止可能）
  8. Pop 456（到目前为止可能）

现在我们已经弹出了 345, 567, 456，接下来我们需要弹出 234，但在栈顶的是 234 的下一个值 123。由于栈是后进先出，没有办法直接弹出 234 而不先弹出 123。

因此，弹出序列 345、567、456、234、123 是不可能实现的。在栈结构中，一旦一个更晚推入的元素被弹出（在这个情况中是 345），所有在它之前推入并且还未弹出的元素必须在该元素之后弹出，而 234 在 345 之前推入，因此它应该在 345 之后弹出，这与给定的顺序不符。