Design an implementation of an abstract data type that supports the following op

Question

Design an implementation of an abstract data type that supports the following operations: Insert(x): the insertion should be performed even if x is already in the data structure. In other words, the data structure should hold duplicates. Remove(y): remove any element from the data structure and assign it to y. Again, any element will do. If there are several copies of the same element only one of them should be removed. This abstract data type is called a pool (or a bag). It is useful for storing jobs, for example. New jobs are generated and inserted into the pool, and when a worker becomes available a job is removed. All the operations should take O (1) time. [E]

Explanation / Answer

public interface Bag

{ public void insert(Object item);

public boolean remove(Object target);

}

public class ObjectArrayBag implements Bag

{

private Object[] items;

private int numItems;

public ObjectArrayBag() {

numItems = 0;

items = new Object[100];

}

public void insert(Object item) {

items[numItems ] = item;

numItems++; // This is hold the duplicate data

}

public boolean remove(int target) {
int index = 0;
while ((index < numItems) && (target != items[index]))
index++;
if (index == numItems)
return false;
else {
numItems--;
items[index] = items[numItems];
return true;
}
}

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.