# Using Double Ended Queues (Deques) for Transpose Sequences

This is an interesting question that may be more interesting than helpful. Let's say I want to copy two of its comment ( `DQ1_a`

and `DQ1_b`

) in the copies ( `DQ2_a`

and `DQ2_b`

).

``````DQ1_a= <A,B,C,D,E,F>
DQ1_b= <G,H,I,J,K,L,M>
```

```

But we want to exchange "strands" for `D<->J`

. Thus, we want to get

``````DQ2_a= <A,B,C,(D or J),K,L,M>
DQ2_b= <G,H,I,(J or D),E,F>
```

```

`or`

exists because it depends on whether it includes elements denoting an exchange or not.

`Question 1`

: Find the algorithm that ends up with the transposed data structure `DQ2_*`

, starting with the score data `DQ1_*`

and the items exchanged `ex=(D<->J); ex[a]=D; ex[b]=J`

. Allowed operations are deque - `left_push,left_pop,right_push,right_pop,deque_empty`

(the latter returns whether empty or not).

Decision:

``````left_item  <- left_pop(DQ1_a)
while (left_item!=ex[a]):
right_push(DQ2_a,left_item)
left_item<-left_pop(DQ1_a)

right_item <- right_pop(DQ1_b)
while (right_item!=ex[b]):
left_push(DQ2_b,right_item)
right_item<-right_pop(DQ1_b)

# if not inclusive
right_push(DQ2_a,left_item)
left_push(DQ2_b,right_item)
# else
#right_push(DQ2_b,left_item)
#left_push(DQ2_a,right_item)

left_item  <- left_pop(DQ1_b)
while (not deque_empty(DQ1_b)):
right_push(DQ2_a,left_item)
left_item<-left_pop(DQ1_a)

right_item <- right_pop(DQ1_a)
while (not deque_empty(DQ1_a)):
left_push(DQ2_b,right_item)
right_item<-rightt_pop(DQ1_a)
```

```

`Question 2`

: This is what hits me. Given a set `DQ1_*`

(more than 2) - you need to copy them to `DQ2_*`

using the exchange list

``````ex={s: s is a given set of exchanges of the form: (ith element of DQ1_x)<->(jth element of DQ1_y)}
```

```

Any better solutions to this problem are appreciated!

+3

source to share

All Articles