The Problem
1. Integer numbers are stored in a queue in a random order.
2. All numbers must eventually be removed from the queue and loaded over to a stack.
3. Elements can only be stored in the stack such that at any time the values are placed in
an increasing order from top down, like the disks in the game of Towers of Hanoi. In
particular, the minimum element is always at the top position.
4. (5 pts) No additional storage is allowed, at any given time each number is either in the
queue or in the stack.
Analysis and Design
1. The algorithm follows the following steps:
– if stack is not empty and first in the queue is greater than top in the stack, pop top
and add it to the queue
– else remove first from the queue and push it on the stack
– repeat until queue is empty
2. Both queue and stack are linked lists
3. (20 pts) Implement the Node class supporting the lists as you see it best. Using generic
type is optional. Defining Node methods not needed for the current solution is optional.
Redefine the displayList() method from your HW 3
4. (10 pts) Design additional classes as you need them and as you see it best. There has to
be a Test class containing the main method in your project.
5. (20 pts) Design and implement the queue and stack methods as necessary for linked list
based structures. Give the specifications to document the methods
Implementation and Requirements
1. (20 pts) The implementation must be tested and the result (decreasing storage) verified
on the console, use the displayList( ) method.