律師回復(fù)

• 
  智能法律助手

  月幫助201720人

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

  回復(fù)于 2022-12-14 10:12:20