作者yauhh (哟)
看板Programming
标题Re: [问题] queue删中间的元素花O(1)
时间Fri Aug 31 23:51:01 2012
※ 引述《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)