Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Sorting a queue using same queue

I have been asked this question and I think it's doable, However I am having a hard time coming up with an algorithm to do this. The restrictions is that you can not use any other data structure nor create another queue. Also you only can use enqueue, dequeue and peek (NOT a priority queue).

Thanx for contributing :)

like image 242
3ashmawy Avatar asked Feb 27 '11 15:02

3ashmawy


1 Answers

BubbleSort using a queue:

n <- size of queue
repeat n times
  x <- dequeue item
  repeat (n-1) times
    y <- dequeue item
    if x < y then
      enqueue y
    else
      enqueue x
      x <- y
    end
  end
  enqueue x
end
like image 81
Markus Jarderot Avatar answered Nov 16 '22 01:11

Markus Jarderot