完成了一般隊列,接下來就是雙向隊列,這個時候操作就沒有強烈的單調方向性質,需要同時維護兩種入隊、出隊的情況。
沿用可持久化隊列的思路。在隊列時,我們評估情況為前後各一半,預估反轉的結果,均攤每一個操作費用,一旦前半部為空,立即使用反轉完的結果。而雙向的情況更為複雜,我們若按照隊列的方式,那麼在 pop-back 的時候,預估的結果反而成為了阻礙,因為要再反轉一次回來。為此調整鬆弛反轉的限制。
即時雙向隊列 (Realtime)
- REAL-TIME DEQUES, MULTIHEAD TURING MACHINES and PURELY FUNCTIONAL PROGRAMMING, Tyng-Runey Chuang and Benjamin Goldberg, 1993
定義
定義雙向隊列為 $Q = \left \langle L, \; R \right \rangle$
在操作過程中,可以鏡像狀態,令較大的那一個為 $B$,較小的為 $S$,意即 $\left \langle B, \; S \right \rangle = \left \langle L, \; R \right \rangle$ 或者 $\left \langle B, \; S \right \rangle = \left \langle R, \; L \right \rangle$。需滿足
$$\begin{aligned} |B| \ge |S| \ge 1, \; \text{and} \; 3|S| \ge |B| \end{aligned}$$若違反上述條件,立即進入 轉移狀態,將三分之一的 $B$ 搬入 $S$,此時兩者具有近似的大小。在轉移中,我們可能在過程中將其中一方增減,完成轉移後必要滿足條件式。
轉移狀態
令起始轉移狀態為 $\left \langle S, \; B \right \rangle$,其中
- $S = (p_1, p_2, \cdots, p_m)^\triangleleft$
- $B = (q_1, q_2, \cdots, q_{3m+k})^\triangleright$
- $k \in \left \{ 1, 2, 3\right \}$
目標狀態 $\left \langle \textit{new}S, \; \textit{new}B \right \rangle$
- $\textit{new}S = (p_1, p_2, \cdots, p_m, q_1, q_2, \cdots, q_{m+1})^\triangleleft$
- $\textit{new}B = (q_{m+2}, q_{m+3}, \cdots, q_{3m+k})^\triangleright$
必須均攤在 $m$ 次操作內完成,而舊有的 $S$ 可能在轉移中被 pop 到空集合,需要標記複製成功的次數,直到 $\textit{new}S$ 已經匹配了前半部的 $S$。
- $B = (q_1, q_2, \cdots, q_{3m+k})^\triangleright$ 拆分成
$B = (q_1, q_2, \cdots, q_{m+1})^\triangleright$ 和 $\textit{aux}B = (q_{m+2}, q_{m+2}, \cdots, q_{3m+k})^\triangleleft$ - $\textit{new}S = (p_1, p_2, \cdots, p_m)^\triangleleft$ 反轉成
$S = ()^\triangleleft$ 和 $\textit{aux}S = (p_1, p_2, \cdots, p_m)^\triangleright$ - $\textit{aux}B = (q_{m+2}, q_{m+2}, \cdots, q_{3m+k})^\triangleleft$ 反轉成
$\textit{aux}B = ()^\triangleleft$ 和 $\textit{new}B = (q_{m+2}, q_{m+2}, \cdots, q_{3m+k})^\triangleright$ - $B = (q_1, q_2, \cdots, q_{m+1})^\triangleright$ 放入為
$\textit{new}S = (q_1, q_2, \cdots, q_{m+1})^\triangleleft$ 和 $B = ()^\triangleright$ - $\textit{aux}S = (p_1, p_2, \cdots, p_m)^\triangleright$ 也放入為
$\textit{new}S = (p_1, p_2, \cdots, p_m, q_1, q_2, \cdots, q_{m+1})^\triangleleft$ 和 $\textit{aux}S = ()^\triangleright$
步驟 1 和 2 同時操作,總數至多為 $2m+3$。步驟 3 可以和 4 或 5 其中一種同時操作,總數至多為 $2m+3$,因此操作數為 $4m+6$。均攤在 $m$ 次操作內,得到常數因子為 4。
隊列操作說明
即使說明了轉移方程,主要的問題還是卡在做到 push/pop
pushFront
/pushBack
若計算完的雙向隊列大小小於等於 4 時,採用攤平的方式操作,強制不進入上述轉移條件。反之,直接在相應的堆疊上操作。popFront
/popBack
若計算完的雙向隊列大小小於 4 時,採用攤平的方式操作,強制不進入上述轉移條件。反之,直接在相應的堆疊上操作。
額外維護的指針告訴我們複製的 $S$ 狀態,而 $B$ 也會在過程中被 pop 出去,因此 $\textit{new}B$ 有時會需要代入 $\text{Take}$ 操作。