Your first task is to implement a dynamic navigation stack.

A navigation stack is actually 2 stacks with additional backward and forward operations mimicking the behavior of recording events to allow undo and redo operations. This class requires you to implement two stacks using a single array (one stack starting at each end) allowing pushes and pops from each stack.

The objects in these stacks are stored in a single array. The capacity of the array may be changed depending on the sum of the number of objects stored in the two stacks according to the following two rules:

• If an object is being pushed onto a stack where the array is already full (the sum of the number of objects in both stacks equals the array capacity), the capacity of the array is doubled.
• If, after removing an object from a stack, the sum of the number of objects remaining in the two stacks is 1/4 the capacity of the array or less, then the capacity of the array is halved. The capacity of the array may not be reduced below the initially specified capacity.

Member Methods:

• DynamicNavStack(int cap): This constructor takes as an argument the initial capacity of the array and allocates memory for that array. If the argument is either 0 or a negative integer, set the initial capacity of the array to the default capacity (=2). Other member variables are assigned as appropriate.
• DynamicNavStack(): This constructor should use the other constructor with an initial capacity set to default value(=2).
• int size(): Returns the number of all elements in both undo and redo stacks.
• E undoTop(): Return the top element of the undo stack. Return null if the undo stack is empty. Do not delete the element.
• E redoTop(): Return the top element of the redo stack. Return null if the redo stack is empty. Do not delete the element.
• boolean isEmpty(): Return true if there are no elements in both stacks.
• int capacity(): Return the current capacity of the array.
• boolean canUndo(): Return true if the undo stack is not empty and false otherwise.
• boolean canRedo(): Return true if the redo stack is not empty and false otherwise.
• void push(E e): Push the element e on top of the undo stack and empty the redo stack. This might require growing or shrinking the array according to the rules mentioned at the beginning of this project description.
• E undo(): if the undo stack is not empty, pop the top element off of the undo stack, push it onto the redo stack, and return the element. Otherwise, return null.
• E redo(): if the redo stack is not empty, pop the top element off of the redo stack, push it onto the undo stack, and return the element. Otherwise, return null.