Problem 3. (15 marks) Once a Push() call is invoked on a full stack (stack.size-
ID: 3737715 • Letter: P
Question
Problem 3. (15 marks) Once a Push() call is invoked on a full stack (stack.size- stack.capacity), we increase the capacity of a stack (or a queue, or a hash-table) using IncreaseCapacity) 1. Allocate a new array with 2 x stack.capacity cells; 2. Copy all items from the original array to the new array, delete the old array Analogously to this, once stack.size is small in comparison to stack.capacity, we can decrease the capacity and clear some memory using DecreaseCapacity() 1. Allocate a new array with stack.capacity/2 cells; 2. Copy all items from the original array to the new array, delete the old array Note that both increas eCapacity() and DecreaseCapacity() run in ?(n)-time a. (5 marks) Prove that invoking DecreaseCapacity) whenever stack.size- stack.capacity/2 is unwise. That is, show that starting with stack.size -0, there exists a sequence of n Push/Pop ) instructions whose amortized cost is S2(n) b. (10 marks) Prove that invoking DecreaseCapacity() whenever stack, size = stack·capacity/3 main- tains constant amortized cost. That is, show that any sequence of n PushO/Pop) instructions has amortized cost of O(1). You may assume stack.capacity1 initially Hint: Call an instruction heavy if it invokes either IncreaseCapacity) or DecreaseCapacity); and call it light otherwise. Light instructions always take O(1). Your argument should probably begin by showing that between any two heavy instructions there have to be at least p m light instructions (by considering all 4 possible cases), where m denotes the capacity of the stack between the two heavy instructions and 0Explanation / Answer
SOURCE CODE:
public class StackResizeArray <T> {
T[] content;
int size;
public static void main(String[] args) {
StackResizeArray stack = new StackResizeArray();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(stack.toString());
try {
stack.pop();
stack.pop();
} catch (Exception e) {
e.printStackTrace();
}
System.out.println(stack.toString());
}
public StackResizeArray(){
this.content = (T[]) new Object[1];
this.size = 0;
}
private void resize(int capacity){
T[] copy = (T[]) new Object[capacity];
for (int i = 0; i < size; i ++){
copy[i] = this.content[i];
}
this.content = copy;
}
public void push(T item){
if (this.size == content.length)
resize(2*this.size);
content[size ++] = item;
}
public T pop() throws Exception {
if (size == 0) throw new Exception("given stack is empty!");
T item = content[--size];
content[size] = null;
if (size > 0 && size == content.length / 4)
resize(content.length / 2);
return item;
}
@Override
public String toString(){
StringBuffer sb = new StringBuffer();
for (int i = 0; i < size; i ++){
T t = content[i];
sb.append(t.toString()+" ");
}
return sb.toString();
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.