Doc file include the complete Java Code solution-
Project 1: We can store k stacks in a single array if we use the data structure suggested in Figure
1 shown below, for the case k = 3. We push and pop from each stack as suggested in connection
with Figure 2 below. However, if pushing onto stack i causes TOP(i) to equal BOTTOM(i – 1),
we first move all the stacks so that there is an appropriate size gap between each adjacent pair of
stacks. For example, we might make the gaps above all stacks equal, or we might make the gap
above stack i proportional to the current size of stack i (on the theory that larger stacks are likely
to grow sooner, and we want to postpone as long as possible the next reorganization).
1. On the assumption that there is a procedure reorganize to call when stacks collide, write
code for the five stack operations.
2. On the assumption that there is a procedure MakeNewTops that computes newtop[i], the
"appropriate" position for the top of stack i, for 1 , i , k, write the procedure reorganize.
Hint. Note that stack i could move up or down, and it is necessary to move stack i before
stack j if the new position of stack j overlaps the old position of stack i. Consider stacks
1, 2 , . . . , k in order, but keep a stack of "goals," each goal being to move a particular
stack. If on considering stack i, we can move it safely, do so, and then reconsider the
stack whose number is on top of the goal stack. If we cannot safely move stack i, push i
onto the goal stack.
3. What is an appropriate implementation for the goal stack in (2)? Do we really need to
keep it as a list of integers, or will a more succinct representation do?
4. Implement MakeNewTops in such a way that space above each stack is proportional to
the current size of that stack.
The implementation of this stack management software should be as structured as possible.
CSEN 5303 Object-Oriented Design and Programming
Description of project -
Project 1: We can store k stacks in a single array if we use the data structure suggested in Figure
1 shown below, for the case k = 3. We push and pop from each stack as suggested in connection
with Figure 2 below. However, if pushing onto stack i causes TOP(i) to equal BOTTOM(i – 1),
we first move all the stacks so that there is an appropriate size gap between each adjacent pair of
stacks. For example, we might make the gaps above all stacks equal, or we might make the gap
above stack i proportional to the current size of stack i (on the theory that larger stacks are likely
to grow sooner, and we want to postpone as long as possible the next reorganization).
Figure 1
Figure 2
2
1. On the assumption that there is a procedure reorganize to call when stacks collide, write
code for the five stack operations.
2. On the assumption that there is a procedure MakeNewTops that computes newtop[i], the
"appropriate" position for the top of stack i, for 1 , i , k, write the procedure reorganize.
Hint. Note that stack i could move up or down, and it is necessary to move stack i before
stack j if the new position of stack j overlaps the old position of stack i. Consider stacks
1, 2 , . . . , k in order, but keep a stack of "goals," each goal being to move a particular
stack. If on considering stack i, we can move it safely, do so, and then reconsider the
stack whose number is on top of the goal stack. If we cannot safely move stack i, push i
onto the goal stack.
3. What is an appropriate implementation for the goal stack in (2)? Do we really need to
keep it as a list of integers, or will a more succinct representation do?
4. Implement MakeNewTops in such a way that space above each stack is proportional to
the current size of that stack.
The implementation of this stack management software should be as structured as possible.