# 可持久化雙向隊列 Persistent Deque 序

## 即時雙向隊列 (Realtime)

• REAL-TIME DEQUES, MULTIHEAD TURING MACHINES and PURELY FUNCTIONAL PROGRAMMING, Tyng-Runey Chuang and Benjamin Goldberg, 1993

### 定義

\begin{aligned} |B| \ge |S| \ge 1, \; \text{and} \; 3|S| \ge |B| \end{aligned}

### 轉移狀態

• $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 \}$

• $\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$

1. $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 2. \textit{new}S = (p_1, p_2, \cdots, p_m)^\triangleleft 反轉成 S = ()^\triangleleft$$\textit{aux}S = (p_1, p_2, \cdots, p_m)^\triangleright$
3. $\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 4. B = (q_1, q_2, \cdots, q_{m+1})^\triangleright 放入為 \textit{new}S = (q_1, q_2, \cdots, q_{m+1})^\triangleleft$$B = ()^\triangleright$
5. $\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$

### 隊列操作說明

• pushFront/pushBack計算完的雙向隊列大小小於等於 4 時，採用攤平的方式操作，強制不進入上述轉移條件。反之，直接在相應的堆疊上操作。
• popFront/popBack計算完的雙向隊列大小小於 4 時，採用攤平的方式操作，強制不進入上述轉移條件。反之，直接在相應的堆疊上操作。