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 :)
Sort(Q,n):
for i = 0 to n-1
min = findMin(Q, n-i, n)
reorder(Q, min, n)
end for
findMin(Q, k, n):
min = infinity
for i = 1 to n
curr = dequeue(Q)
if curr < min && i<=k
min = curr
end if
enqueue(Q,curr)
end for
return min
reorder(Q, min, n):
for i = 1 to n
curr = dequeue(Q)
if (curr != min) // I'm assuming that there is a way to differentiate between any two items, this isn't hard to enforce
enqueue(Q, curr)
end if
end for
enqueue(Q,min)
Ascending sort, runs in O(n^2) time, in space O(1) (i.e. the queue is O(n) space, and extra space required by the algorithm is O(1))
Explanation:
Essentially, we iterate through the queue n times, each time the iteration costs 2n.
On each iteration, we go through the entire queue and pick the minimum within the relevant number of items. So at first the relevant number of items is n, since we want the minimum of them all. The next iteration we want the minimum of the first n-1 items, and then n-2 items, etc. Since the algorithm will stack these minimums at the end.
Once we found the minimum, we need to iterate over the whole stack again in order to snatch it and stack it on the end.
The main idea here, is that a dequeue followed by an enqueue of that same element will allow us to iterate over the queue and check minimum/maximum while preserving order.
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
end markers, to make the boundaries clearer.
O(1)memory?peekonly return the head of the queue, or can you use it to find the value of any position the queue?