a problem about deque, double ended queue

The easier version:

A sequence of push with 1, 2, 3, ..., N is done, each push could be either push_back or push_front. Given the resulting sequence of numbers, can you find a sequence of push ops that generates such a sequence?

Solution: Obviously N can only be the first or the last in the resulting sequence and you can recurse from there.

Slightly harder version:
You have push_front, push_back and pop_front, can some sequence of (1, 2, ..., N) be realized?

Solution: Consider the time you push in N, either front or back. This is the last push, and the rest have to be pop_back. Now if you push N in front, then N must be popped last, so N must appear last in the display sequence. The other case is that you push N back, then all you have are pops and you can only pop_back, so N must be push_back, then immediately pop_back.

Case 1: N is push_front, then it must be the last item in the sequence is N. So we can work with the rest 1,...,N-1 now.

Case 2: N is push_back, then it must be the next op is pop_back, as there are no more push. And the item got popped must be N. Now consider N-1, if N-1 is a push_front, then N-1 must appear in the end of the sequence removing N, else N-1 is push_back and it must then be popped back immediately. In that case N-1 must be to the left of N.

Now we are almost there. Look at the sequence, locate N. From the pos where N appears, to the end, it must be increasing, because they are all push_front. (if not they will appear to the left of N) , then they got pop_back.

Then we locate N-1, if it is to the right of N, then it must be the last. Else it is to the left of N, then the sequence from N-1 to the right, excluding N, must be increasing, for the same reason.

The algorithm:
mark[0..N-1] = 0
last = N (the pos where N could occur if it is push_front, hence popped last)
pos = N
for i = N down to 1 {
  if  (s[--last] == i) then { mark[last] = 1; }
  else while (--pos >= 0) { if (s[pos] == i) break; }  // implicitly skipped mark[pos] = 1
  if (pos < 0) break;
  else mark[pos] = 1;
}
// All pos from 0 to N-1 must have been marked for a feasible sequence
assert( all mark[0..N-1] are 1);


The harder version:

In addition to push, you now have pop, and there are four operations: push_back, push_front, pop_back, pop_front. The push still follows the order of 1, 2, 3, ..., N as the numbers they push, although each could either be push_back or push_front. The pops will interleave the pushes and in the end all numbers pushed will get popped. So you get a sequence which is a permutation of 1,...,N. The question asks you to reconstruct an op sequence to realize the output of the pops.

It seems for all N<=4, any permutation can be realized. For N=5, seems 5 1 3 2 4 cannot be realized. The reason?

When 5 is popped, all 1, 2, 3, 4 have already in the deque, the only thing that can happen afterwards are pops, no push any more. 5 is either the first or the last, w.l.o.g. we can assume it is first. Then 1 is either second or last, suppose it is second, then there is nothing in between 1 and 5, so 2, 3, 4 are to the right of 1. Then we can only have 1, 2, 3, 4, but no pop can give 1, 3, 2, 4. The case that 1 is last is similar, you have 4 3 2 1 and cannot give 1 3 2 4 either.

I think I have some idea about the algorithm now.

First the output of N marks the end of push, and the rest have to be pop. To be a valid pop cluster, the cluster has to have min element as its left or right edge, and the rest recurse. Before that, we have seen a sequence of output smaller than N, and the first one must be a left or right element, the next one, if larger, can be adjacent to it predecessor, else it is smaller and has to take an opposite edge. Along this line, we somehow could reconstruct a sequence by ignoring all pops, and this might help us find the pushes, then the pops.