Re: [問題] linked list& array

[yauhh (喲)]

※ 引述《jimmy5566 (jimmy)》之銘言：
: 有個問題覺得怪怪的
: 想釐清一下
: 就是stack和queue都可以用array和linked list來製作
: 那linked list可以用array和stack來製作嗎?
: 麻煩了~謝謝

從你的問答中可以看到一些事情,第一,你思考的可能是單純的對立關係:
如果這邊這些可以用那邊的東西實作,則那邊的東西應該也可以用這邊的東西實作.
雖然事實可能不是這麼單純. 不過,如果你還是學生,恭喜你,你有足夠的自由空間
可以做這樣的思考,好處是一來別人可能不會想這種事情,所以你有投入時間思考
這問題的機會,二來是社會現實還不夠近逼甚至傾軋得你不得想這個問題.

從你的問答中所看到的第二個情況,你可能還沒熟識 stack, queue,
array, linked list 的特徵. 有些資料結構會很認真把這些項目抽象化,
像 Horowitz 先生的那本經典的資料結構教科書,會直接用ADT表達.
你可以先看看那樣的書.

你可以仔細想想這些資料結構或資料格式的特徵:

Array: 一堆 key-value 配對, 所有的 key 是連續整數.

Linked list: 一堆有限數目的物件,任何一個對另一個有前後關係.

Stack: 與 linked list 類似之處是有限數目的物件,物件有前後關係.
       並且加上 stack 自己的限制,只有一個端點可以將新物件加進去
       產生另一個 stack, 或是把存在的物件拿走,剩下的也是 stack.

queue: ...

如果要解 "用 stack 製作 linked list" 這樣的問題,你可以先把 linked list
所擁有的特徵抓出來,像是二個物件之間有前後關係,以及它還可以刪掉一些中間
的物件,剩下的也構成一個 linked list. 再來看看 stack 提供了哪些特徵
可以達到 linked list 所需要的功能: 新增, 刪除, 隨意位置刪除, 前進定位,
回溯等等, 看用 stack 該怎麼組合可以做得到.

例如,令有一堆 stack S[1..N], 任何一個 stack S[i] 的規格為:

        S[i].push(D) => S[i]'       ;; S[i]'是S[i]加了一項物件D
        S[i]'.pop => { D, S[i] }    ;; 同上,而pop之後取出資料並得到另一stack

你可以說以下這樣的結構擁有 linked list 一部份的特徵:

        LL = S[1].push(S[2].push(S[3].push(...S[N].push(nil)))...)

因為

        LL.next = S[1].pop = { D[1], LL' = S[2] }
        LL'.next = S[2].pop = { D[2], LL'' = S[3] }
        ...

這樣就是 linked list 前進並定位的功能.

第三個所見到的事情,很明顯,有蠻多人會拒絕認真回答你的問題.
不過,仔細 Google, 用正確的關鍵字尋找,仍可以找得到有人問過這樣的問題:
像是 "用 stack 可不可以做出 linked list", 然後他得到的回答是:
"要問就先檢查是不是問對問題." 一般來說,人可能都用 C++ 背景知識
回答你說:哎呀,不可能做得到的啦. 不過,既然你沒有說你是在思考 C++ 的東西,
你也可以把所謂 array 當作抽象結構來思考. 誰管你怎麼想,這就是學習.
不過最後回歸到特定電腦語言領域中的時候,就要把現實的範圍限制加上去.
我想這些是你該釐清的.


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 218.160.212.40
→ loveme00835:你真的很屌...回得出這個
→ loveme00835:stack 可以實作 linked list, 那stack
→ loveme00835:要用什麼實作? 難道用 linked list?
→ adrianshum:樓上大概沒看懂原po的意思.你把linked
→ adrianshum:list 看成是一種實作那當然覺得別扭.原
→ adrianshum:po想說的,就是你可以把 array/linked
→ adrianshum:list 想成一種interface 一種協定.
→ adrianshum:那麼, 底層用任何的stack impl 來達成y
→ adrianshum:這協定, 就是原po 要解決的問題
→ loveme00835:這個叫做介面配接, 不叫實作
→ loveme00835:而原PO問的就是"製作"
→ yauhh:要怎麼解釋當然隨你高興囉,不過,別以為全世
→ yauhh:界只有C語言才叫作程式語言
→ yauhh:沒有人規定array只准是C的記憶體對應array,
→ yauhh:甚至也沒有人規定array非得是隨機存取.
推 dryman:推，我比較好奇要如何做insert..