律師回復

• 
  智能法律助手

  月幫助201720人

  先說一般結論 從初始輸入序列1, 2, ..., n通過一個棧得到輸出序列p1, p2, ..., pn的充分必要條件是：不存在這樣的i, j, k滿足i再說證明 充分條件 如果不存在這樣的序列i, j, k滿足i ..., pj, ..., pk, ..., pi, ... (pj 不存在這樣的輸出序列 ..., pi, ..., pj, ..., pk, ... （或簡單地，對于輸入序列123，不存在輸出序列312） 從中可以看出，pi后進先出，滿足棧的特點，因為pi最大，所以pi在pj和pk之后進棧，并且在pj和pk之前出棧，這同時說明在pk之前進入的pj不可能在pk之后出來，也滿足先進后出的特點，所以構成一個棧。 必要條件 如果初始輸入序列是1, 2, ..., n并進棧，又同時存在這一的i, j, k滿足i ..., pj, ..., pk, ..., pi, ... (pj 存在這這樣的輸出序列： ..., pi, ..., pj, ..., pk, ... 從中可以看出，pi先進后出，滿足棧的特點，然而在pk之前進入的pj卻在pk之前出來，不滿足先進后出的特點。因此前面假設其是棧不成立，本例得政。 原問題：《判斷一個序列是不是棧的輸出序列.pdf》

  回復于 2022-12-14 10:12:20