Re: [問題] queue刪中間的元素花O(1)
※ 引述《wsx02 ()》之銘言：
: 原題 http://ppt.cc/Qc4_
: 大意是說要做一個特殊的queue
: enqueue, dequeue, 刪中間的元素都花O(1)
: 我一開始的想法是用array 因為可以(front+tail)/2當index直接去存取
: 然後後面的元素不要去搬動 要是搬動就等於花O(n/2)=O(n)的時間去刪中間的元素
: 可是這樣在一連串的刪除中間的元素之後會亂掉 (front+tail)/2不見得是middle
: 還是要用linked list? 有辦法做到刪中間的元素花O(1)嗎?
: 請問有人有好的想法做出這種queue嗎?
: 謝謝
用一個deque(雙向queue),H,代表前段,並用一個queue,T,代表後段.
deque二個enqueue稱e1,e2,二個dequeue稱d1,d2.
要有一個二元狀態值,B,用1,2,1,2,1,2,...這樣切換,
1代表H,T數目相等.2代表H數目比T多一個.
這整個是一個特殊queue,S,
S = {H = {C = {}, e1, e2, d1, d2},
T = {C = {}, enqueue, dequeue},
B = {C = 1, := 1, := 2, == }}.
三個操作: enqueue, dequeue, extract_mid定義如下,
S.enqueue: if (B == 1) H.e1(T.dequeue),
B := 2,
T.enqueue.
if (B == 2) T.enqueue,
B := 1.
S.extract_mid: if (B == 1) E := H.d2,
H.e1(T.dequeue),
B := 2,
return E.
if (B == 2) B := 1,
return H.d2.
S.dequeue: if (B == 1) H.e1(T.dequeue),
B := 2,
return H.d1.
if (B == 2) B := 1,
return H.d1.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 36.226.94.128
※ 編輯: yauhh 來自: 36.226.94.128 (09/01 00:02)
Programming 近期熱門文章
PTT數位生活區 即時熱門文章
