Win a copy of Learn Spring Security (video course) this week in the Spring forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Interesting recursion

 
Francis Siu
Ranch Hand
Posts: 867
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I have taken a test which contains some interesting questions, such as how to use a single queue to re-arrange some number
The queue contains some numbers that are 5,6,8,4,2 then after using some methods,then the arrangement becomes-->2,4,8,6,5. The constraint is that you can use a variable to do it but not array.
Of course, I solved the problem but I wonder if any ranchers have any other idea to solve above question. ^o^
And I would be appreciate if any ranchers provide some interesting algorithm that can be used to change a stack to become a queue or to change a data structure to become another type of data structure.
It would be better if you could provide JAVA programming language. (C or C++ also fine, but not c# )
thanks for your help
[ November 17, 2004: Message edited by: siu chung man ]
 
somkiat puisungnoen
Ranch Hand
Posts: 1312
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
in java 5.0 have java.util.Queue interface , i don't know it supported requirenebt of or not.

But

i have some idea to re-arrange data in queue.

I'm use List object to implemet Queue and use Collections.sort(List, Comparator); to sort data in List object.
 
Nicholas Cheung
Ranch Hand
Posts: 4982
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I agree with somkiat. In fact, if the standard APIs provide the required functions, why still border to create one?

The sorting function is provided in J2SE 1.4 as well, even you wont need Tiger to solve them.

Nick
 
Francis Siu
Ranch Hand
Posts: 867
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Oo...I create another unclear question
My question is not related to sorting , as I mentioned before, one of the data structure used to store some numbers, how to implement some algorithms in order to change queue to another data structure. For example, a queue is used to store some numbers 5,6,8,4,2, which algorithm is used to change the arragement to be 2,4,8,6,5. You can not use a stack to do it.
Another example is that a stack stores some numbers 5,6,8,4,2, which algorithm is used to change the arragement to be 2,4,8,6,5, you can not use another stack to do.
Both of these example can only use a variable to do it.
Any suggestion and idea is appreciate.
thanks
 
Ernest Friedman-Hill
author and iconoclast
Marshal
Pie
Posts: 24208
35
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The problem is to reverse the contents of the queue. Are there additional constraints on the problem imposed by the fact that this is a queue? In other words, is it a proper queue from which you can only access the first element? Or perhaps a double-ended queue, where you can look at the element at either end? Or is it random access?
 
Francis Siu
Ranch Hand
Posts: 867
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
yes, it is a proper queue from which we can only dequeue from the front (first element) and enqueue to the back(rear). It is not a double-ended queue. We can use a variable(but not array) as a temporary variable to store an element.
Ernest
thanks for your help
 
David Harkness
Ranch Hand
Posts: 1646
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
In two minutes recursion is the only solution using a single temporary variable that pops into my head. Of course, by using recursion you're actually using one temporary variable per element in the queue, so that's kind of cheating (it acts like an open-ended array stretched out across the program stack).

However, I would not say that using an algorithm like this "makes a queue behave like a stack." That would be akin to using Collections.sort(list) and then claiming that a list acts like a sorted list.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic