Two stacks, p and q, contain nodes of identical ordered structure ElementType (e.g. long, double, String, etc), with the earliest values in the ordering being at the tops of the stacks. A third stack, r, is available and is initially empty. It is possible to produce the complete ordered set of nodes in stack p, with the earliest value at the top using the following algorithm:
Stack p, q, r ElementType topp, topq, topr
WHILE (NOT p.empty() AND NOT q.empty()) DO topp = p.pop() topq = q.pop() IF (topp <= topq) THEN r.push(topp) q.push(topq) ELSE r.push(topq) p.push(topp) ENDIF END
WHILE NOT p.empty() DO topp = p.pop() r.push(topp) END
WHILE NOT q.empty() DO topq =q.pop() r.push(topq) END
WHILE NOT r.empty() DO topr = r.pop() p.push(topr) END
By employing an appropriate STACK ADT and choice of suitable test data, write the above program.
It is already prett much written. You can implement the queues with LinkedLists, fill them up with Random values and run your test. Of course, it would be simpler and more clear to just combine the two queues, then do a sort...
Previous Topic
