Roughly.. Make a plot showing the running time (y-axis) vs. the number of push o
ID: 3888926 • Letter: R
Question
Roughly.. Make a plot showing the running time (y-axis) vs. the number of push operations (xaxis). Implement a Stack whose size can grow as elements are inserted into the stack. You will build three different implementations of this Stack. Two of these implementations will be array-based. Each of these two should take an initial capacity for the stack in the constructor. The only difference between these implementations will be what happens when the Stack is full. For the first implementation, ArrayStack, you should increase the size of the array by a constant amount. For the second implementation, DoublingArrayStack, you should double the size of the array. Finally, for the third implementation, you should implement a Stack using a Linked List.
Explanation / Answer
internal algorithm to increase the size of an array:
there are 2 methods : 1.add(object)
2.increasecapacity();
i will show program in three steps:
1.class classname{
private object[] objArray=new object[10];
private int elementcount=0;
public void add(object obj){
2 step: if(elementcount==objArray.length){
increasecapacity();
objarray[]=obj;
elementcount++;
}
3step: public void increasecapacity()[
int newcapacity=objArray.length*2;
object[] nextArray=new object[newcapacity];
for(i=0;i,objArray.length;i++){
nextArray[i]=objArray[i];
]
objArray=nextArray
}
impementation of stack using linkedlist:
create program in four steps:
1.public classnode{
public int data;
public node next;
public node(int data)//constructor for node
this.data=data;
}
for displaying node: public void dispalynode(){
system.out.print(data);
}
}
2step: inserting,deleting,dispalylist of elements:
public clas linklist{
private nodefirst=null;
public void insertfirst(int data){
node n =new node(data);
n.next=first;
first=n;
}
public node deletefirst(){
node temp=first;
first=first.next;
return temp;
}
public void dispalylist(){
node current=first;
while(current!=null){
current.dispalynode();
current=current.next;
}
}
public boolean isEmpty(){
retuen(first==null);
}
}
3step:
performing push and pop operations :
public class linkliststack{
linllist li=new linklist();
public void push(int data){
li.insertfirst(data);
}
public void pop(){
while(!li.isEmpty()){
li.deletefirst();
}
}
public void dispalystack(){
system.out.println(" ");
li.dispalylist();
}
4step:
performing operations:
public class linkstackdemo{
public static void main(string[] args){
linkliststack st=new linkliststack();
st.push(50);
st.pop();
st.push(30);
st.displaylist();
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.