$1.$ Draw the following figures:

a$.$ Draw a figure similar to that on p$.245$ of your text, showing the stack after the following sequence of operations:

$```$

StackAllocatr s $=$ new StackAllocatr$(12)$;

s$.$push$(3)$;

s$.$push$(3)$;

s$.$push$(2)$;

$```$

b$.$ Draw a figure similar to that on p$.251$ of your text, showing the heap after the following sequence of operations:

$```$

HeapAllocatr h $=$ new HeapAllocatr$(12)$;

int x $=$ h$.$newH$(2)$;

int y $=$ h$.$hewH$(4)$;

h$.$deleteH$($x$)$;

int z $=$ h$.$newH$(3)$;

$```$

This is one of the simplest mechanisms for heap management: first fit, with a free

list in last$-$in$-$first$-$out order. Consider a HeapManager m with a memory array of

$10$ words, and look at the following sequence of calls:

p$1=$m$*$ allocate $(4)$;

p$2=$m$.$allocate $(2)$;

m$*$ deallocate $($p$1)$;

p$3=$m$.$allocate $(1)$;

The following illustration shows an initial, empty memory array of $10$ words. The

heap manager maintains a variable called freestart, which is a link to the head

of the linked list of free blocks. Initially, the entire memory array is one big free

block:

Every block in the heap, whether allocated or free, has its length in its first word.

For free blocks, the second word is also used. It is the address of the next free block

in the free list. The value $-1$ is used to represent the null link, the link from the last

block in the list.

The running program now makes its first allocation, p$1=$m$.$ allocate $(4).$ The

heap manager finds that the first $($and only$)$ block in the free list is large enough.

In fact, it is too large. The heap manager allocates five words $($the requested four

plus one for the length word$)$ and returns the remainder to the free list. The address

returned to the running program is $1,$ the first of the four requested words.