Is it possible to uniformly shuffle N items into a deque of size N where you can only modify the first or last elements? I had a question about random shuffling. Given a sorted list, is it possible to design an algorithm to return a uniformly random arrangement of the items in a deque with the following operations:

read from list and add to front of deque
read from list and add to back of deque
remove from front of deque and add to back
remove from back of deque and add to front

I am trying to figure out an algorithm to do this without the aid of any other arrays or memory (i.e. outside of the original list of size N and the deque, there is no additional memory). After experimenting with it, I'm doubting it's possible to obtain a truly uniformly random arrangement of the items, but I'd love to be proven wrong. Any guidance would be appreciated.
The final algorithm:
for each new element k:
    perform a random cyclic shift of the sequence on the deque
    insert k to the end of the deque
    perform an inverse cyclic shift

Now, why does it work? (There is probably a simpler way to put it; this is how I understand this)
We generate a random permutation $p$ (we would need additional memory for that, but I'll explain how to avoid it). We replace each input number $a_i$ with pair $(a_i, p_i)$. Now it suffices to sort the pairs based on the second element. It works because different permutations correspond to different orders of elements after sorting.
To perform the sorting, we simply emulate insertion sort:

Let $[p_1, \ldots, p_m]$ be the current numbers in deque, and they are in sorted order.
Then another number $k$ arrives, such that $p_1 &lt; \cdots &lt; p_i &lt; k &lt; p_{i+1} &lt; \cdots &lt; p_m$.
We perform the cyclic shift: $[p_{i+1}, \ldots, p_m, p_1, \ldots, p_i]$.
We insert $k$ in the back: $[p_{i+1}, \ldots, p_m, p_1, \ldots, p_i, k]$
We perform an inverse cyclic shift: $[p_1, \ldots, p_i, k, p_{i+1}, \ldots, p_m]$

To avoid storing the permutation, notice that it suffices to decide the relevant order of elements at the moment of insertion. I.e. for each element, you randomly determine its position among existing elements in the deque and perform the shifts as described.