Once a Push() call is invoked on a full stack (stack.size = stack.capacity), we
ID: 3737773 • Letter: O
Question
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 × 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 IncreaseCapacity() and DecreaseCapacity() run in ?(n)-time.
Prove that invoking DecreaseCapacity() whenever stack.size = stack.capacity/3 maintains constant amortized cost. That is, show that any sequence of n Push()/Pop() instructions has amortized cost of O(1). You may assume stack.capacity = 1 initially.
I've already seen this answered on chegg, but the formatting is terrible and I couldn't understand how they got the answer. Please be very clear!! (I don't need any pseudocode)
Explanation / Answer
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package cheggquestions;
/**
*
* @author Prashant Tomer
*/
import java.util.*;
public class Dynamicstack {
int stack[]=new int[5];
int scapacity=stack.length;
int newarray[];
int top=-1;
static int size=0;
void push(int b)
{
if(top==scapacity-1) //if records are greater than the capacity then increase capacity
{
IncreaseCapacity();
}
else
top=top+1;
stack[top]=b;
}
void pop()
{
System.out.println(stack[top]+"is deleted");
top=top-1;
}
void DecreaseCapacity()
{
if(size<scapacity)
{
newarray=new int[scapacity/2];
System.arraycopy(stack, 0, newarray, 0,scapacity/2 );
//stack=null;
}
}
void IncreaseCapacity()
{
newarray=new int[2*scapacity];
//newarray[i]=a[i];
System.arraycopy(stack,0, newarray,0, stack.length); //this just copy whole data of stack to newarray
//stack=null;
//System.out.println(" Stack Overflow");
//System.exit(0);
}
void display()
{
int i;
System.out.println(" Stacks Records are:");
System.out.println(" --------------------");
for(i=top;i>=0;i--)
{
System.out.println(stack[i]);
}
System.out.println(" --------------------");
}
public static void main(String aa[])
{
Dynamicstack stack=new Dynamicstack();
stack.push(10); //Here pushing 6 elements that is greater than the capacity of stack array
++size;
stack.push(1);
++size;
stack.push(5);
++size;
//stack.DecreaseCapacity();
//stack.DecreaseCapacity();
stack.push(10);
stack.push(1);
stack.push(5);
stack.display();
//stack.pop();
//stack.display();
}
}
O/P:
Stacks Records are:
--------------------
5
10
5
1
10
--------------------
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.