The moose likes Java in General and the fly likes Interesting recursion Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login

Win a copy of Java Interview Guide this week in the Jobs Discussion forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "Interesting recursion" Watch "Interesting recursion" New topic

Interesting recursion

Francis Siu
Ranch Hand

Joined: Jan 04, 2003
Posts: 867
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 ]

Francis Siu
somkiat puisungnoen
Ranch Hand

Joined: Jul 04, 2003
Posts: 1312
in java 5.0 have java.util.Queue interface , i don't know it supported requirenebt of or not.


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.

Java Developer, Thailand
Nicholas Cheung
Ranch Hand

Joined: Nov 07, 2003
Posts: 4982
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.


SCJP 1.2, OCP 9i DBA, SCWCD 1.3, SCJP 1.4 (SAI), SCJD 1.4, SCWCD 1.4 (Beta), ICED (IBM 287, IBM 484, IBM 486), SCMAD 1.0 (Beta), SCBCD 1.3, ICSD (IBM 288), ICDBA (IBM 700, IBM 701), SCDJWS, ICSD (IBM 348), OCP 10g DBA (Beta), SCJP 5.0 (Beta), SCJA 1.0 (Beta), MCP(70-270), SCBCD 5.0 (Beta), SCJP 6.0, SCEA for JEE5 (in progress)
Francis Siu
Ranch Hand

Joined: Jan 04, 2003
Posts: 867
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.
Ernest Friedman-Hill
author and iconoclast

Joined: Jul 08, 2003
Posts: 24199

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?

[Jess in Action][AskingGoodQuestions]
Francis Siu
Ranch Hand

Joined: Jan 04, 2003
Posts: 867
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.
thanks for your help
David Harkness
Ranch Hand

Joined: Aug 07, 2003
Posts: 1646
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.
I agree. Here's the link:
subject: Interesting recursion
It's not a secret anymore!