A CapnStackSparrow is an extended stack that supports four main operations: the standard Stack operations push(x) and pop() and the following non-standard operations: • max(): returns the maximum value stored on the Stack. • ksum(k): returns the sum of the top k elements on the Stack. The zip file gives an implementation SlowSparrow that implements these operations so that push(x) and pop() each run in ?(1) time, but max() and ksum(k) run in ?(?) time. For this question, you should complete the implementation of FastSparrow that implements all four operations in ?(1) (amortized) time per operation. As part of your implementation, you may use any of the classes in the Java Collections Framework and you may use any of the source code provided with the Java version of the textbook. Don't forget to also implement the size() and iterator() methods. Think carefully about your solution before you start coding. Here are two hints: 1. don't use any kind of SortedSet or SortedMap, these all require Ω(log?) time per operation. 2. think about how the maximum on the stack changes as new elements are pushed. Understanding this will help you design your data structure. /////////////////////////////////////////////////////////////////////////////// public interface CapnStackSparrow extends Iterable { public void push(Integer x); public Integer pop(); public Integer max(); public long ksum(int k); public int size(); } import java.util.ArrayList; import java.util.Iterator; public class SlowSparrow implements CapnStackSparrow { protected ArrayList ds; public SlowSparrow() { ds = new ArrayList<>(); } public void push(Integer x) { ds.add(x); } public Integer pop() { if(size() <= 0) return null; else return ds.remove(ds.size()-1); } public Integer max() { Integer m = null; for (int x : ds) { if (m == null || x > m) { m = x; } } return m; } public long ksum(int k) { long sum = 0; for(int i=0; i iterator() { return ds.iterator(); } package comp2402a2; import java.util.Iterator; public class FastSparrow implements CapnStackSparrow { public FastSparrow() { // TODO: Your code goes here } public void push(Integer x) { // TODO: Your code goes here } public Integer pop() { // TODO: Your code goes here return null; } public Integer max() { // TODO: Your code goes here return null; } public long ksum(int k) { // TODO: Your code goes here return 0; } public int size() { // TODO: Your code goes here return -1; } public Iterator iterator() { // TODO: Your code goes here return null; } }
A CapnStackSparrow is an extended stack that supports four main operations: the standard Stack operations push(x) and pop() and the following non-standard operations:
• max(): returns the maximum value stored on the Stack.
• ksum(k): returns the sum of the top k elements on the Stack.
The zip file gives an implementation SlowSparrow that implements these operations so that push(x) and pop() each run in ?(1) time, but max() and ksum(k) run in ?(?) time. For this question, you should complete the implementation of FastSparrow that implements all four operations in ?(1) (amortized) time per operation. As part of your implementation, you may use any of the classes in the Java Collections Framework and you may use any of the source code provided with the Java version of the textbook. Don't forget to also implement the size() and iterator() methods. Think carefully about your solution before you start coding. Here are two hints:
1. don't use any kind of SortedSet or SortedMap, these all require Ω(log?) time per operation.
2. think about how the maximum on the stack changes as new elements are pushed. Understanding this will help you design your data structure.
///////////////////////////////////////////////////////////////////////////////
public interface CapnStackSparrow extends Iterable<Integer> {
public void push(Integer x);
public Integer pop();
public Integer max();
public long ksum(int k);
public int size();
}
import java.util.ArrayList;
import java.util.Iterator;
public class SlowSparrow implements CapnStackSparrow {
protected ArrayList<Integer> ds;
public SlowSparrow() {
ds = new ArrayList<>();
}
public void push(Integer x) {
ds.add(x);
}
public Integer pop() {
if(size() <= 0)
return null;
else
return ds.remove(ds.size()-1);
}
public Integer max() {
Integer m = null;
for (int x : ds) {
if (m == null || x > m) {
m = x;
}
}
return m;
}
public long ksum(int k) {
long sum = 0;
for(int i=0; i<k && i<ds.size(); i++)
sum += ds.get(ds.size() - 1 - i);
return sum;
}
public int size() {
return ds.size();
}
public Iterator<Integer> iterator() {
return ds.iterator();
}
package comp2402a2;
import java.util.Iterator;
public class FastSparrow implements CapnStackSparrow {
public FastSparrow() {
// TODO: Your code goes here
}
public void push(Integer x) {
// TODO: Your code goes here
}
public Integer pop() {
// TODO: Your code goes here
return null;
}
public Integer max() {
// TODO: Your code goes here
return null;
}
public long ksum(int k) {
// TODO: Your code goes here
return 0;
}
public int size() {
// TODO: Your code goes here
return -1;
}
public Iterator<Integer> iterator() {
// TODO: Your code goes here
return null;
}
}
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
