標題: [ICT] 關於Stack的問題 [打印本頁]

---

作者: HSH    時間: 2014-1-17 02:02 PM     標題: 關於Stack的問題

下面這題想了許久，仍不知怎麼下手，不知有無快速的判斷方法，希望各位小卒指點一下，謝謝！

Question:
使用堆疊(Stack)，並可用任意交叉方式行Push及Pop的動作
當資料輸入順序為1,2,3,4,5,6
則資料輸出順序不可能為下列何者？
(A) 3,2,1,4,5,6
(B) 3,4,1,2,5,6
(C) 1,3,2,5,4,6
(D) 3,2,5,6,4,1

Ans: (B)

[ 本帖最後由 HSH 於 2014-1-17 02:06 PM 編輯 ]

---

作者: tony625    時間: 2014-1-18 09:24 PM

think of a stack is a container, push is put thing into it, pop is take out thing from it.

take (A) as example
sequence -- stack -- output (when pop)
push 1 -- |1|X|X|X|X|X| -- n/a
push 2 -- |1|2|X|X|X|X| -- \ /
push 3 -- |1|2|3|X|X|X| -- \ /
pop -- |1|2|X|X|X|X| -- 3
pop -- |1|X|X|X|X|X| -- 3,2
pop -- |X|X|X|X|X|X| -- 3,2,1
push 4 -- |4|X|X|X|X|X| -- \ /
pop -- |X|X|X|X|X|X| -- 3,2,1,4
push 5 -- |5|X|X|X|X|X| -- \ /
pop -- |X|X|X|X|X|X| -- 3,2,1,4,5
push 6 -- |6|X|X|X|X|X| -- \ /
pop -- |X|X|X|X|X|X| -- 3,2,1,4,5,6

to understand it , try it on (C) and (D) as your self exercises ,
finally try your best on (B) as it is impossible to have a sequence .

[ 本帖最後由 tony625 於 2014-1-18 09:29 PM 編輯 ]

---

作者: HSH    時間: 2014-1-26 10:42 AM

Thanks a lot. Let me try it!!!

(C)
push 1 → pop 1 → push 2 → push 3 → pop 3 → pop 2 → push 4 → push 5 → pop 5 → pop 4 → push 6 → pop 6
The sequence is 132546

(D)
push 1 → push 2 → push 3 → pop 3 → pop 2 → push 4 → push 5 → pop 5 → push 6 → pop 6 → pop 4 → pop 1
The sequence is 325641

(B)
push 1 → push 2 → push 3 → pop 3 → push 4 → pop 4 → pop 2 → pop 1 → push 5 → pop 5 → push 6 → pop 6
The sequence should be 342156, but the answer is 341256.

Therefore, the choice (B) is wrong. Is that right???

---

作者: tony625    時間: 2014-1-26 03:42 PM

you got it

---

歡迎光臨 小卒資訊論壇 (http://lsforum.net/board/)

Powered by Discuz! 6.0.0