6
$\begingroup$

Suppose we have N natural numbers in a queue. ex queue = [3, 14, 1, 20] and an empty stack

We are allowed to make only two actions:

  1. Action "x": Dequeue an element from the queue and push it to the stack.
  2. Action "o": Pop an element from the stack and enqueue it in the queue.

In the above example, the following actions sort the queue in ascending order:

Actions: "xxoxooxxoo"

ex.

  • queue: 3, 14, 1, 20 stack:
  • x
  • queue: 14, 1, 20 stack: 3
  • x
  • queue: 1, 20 stack: 14, 3
  • o
  • queue: 1, 20, 14 stack: 3
  • x
  • queue: 20, 14 stack: 1, 3
  • o
  • queue: 20, 14, 1 stack: 3
  • o
  • queue: 20, 14, 1, 3 stack:
  • x
  • queue: 14, 1, 3 stack: 20
  • x
  • queue: 1, 3 stack: 14, 20
  • o
  • queue: 1, 3, 14 stack: 20
  • o
  • queue: 1, 3, 14, 20 stack:

and the queue is sorted.

Any idea how can I solve this problem with the minimum number of actions?

[EDIT]

Actually, it should be with a minimum number of steps, as there is a dummy solution:

You can just rotate the queue by actions: "xo" (move the first number to the end of the queue) and when you reach the largest number, push it to the stack. Repeat this process until the queue is empty. The stack now contains all the numbers with the top being the smallest number. So you just push them out one by one and you have a sorted queue.

$\endgroup$
11
  • $\begingroup$ What running time are you aiming for? $\endgroup$ – Steven May 28 at 12:42
  • $\begingroup$ @Steven Could be done in O(N^2) or pseudo polynomial (nW) with dynamic programming ? (not sure if it can be done faster) $\endgroup$ – entropyfever May 28 at 12:49
  • $\begingroup$ What is $W\phantom{}$? $\endgroup$ – Steven May 28 at 13:01
  • 1
    $\begingroup$ Not a full solution, just a way to think about it: Call a state in which (a) the stack is empty and (b) we can reach the target sorted state in exactly $2N$ moves 1-easy. If a state consists of 1 or more blocks in the queue, each of which consists of a nonincreasing segment followed by a nondecreasing segment, and such that $\max(B_i) \le \min(B_{i+1})$ for each block $B_i$, then the state is 1-easy (but note this does not exhaust the 1-easy states, so a better characterisation is needed). Call a state in which (a) the stack is empty and (b) we can reach an $i$-easy state $(i+1)$-easy. $\endgroup$ – j_random_hacker May 29 at 6:41
  • 2
    $\begingroup$ Can you tell us where you encountered this task? What's the context or motivation? $\endgroup$ – D.W. May 29 at 22:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.