Question

JAVA PROGRAM:

public class Stack {

private DList mList;

public Stack() { setList(new DList<>()); }

private int indexOfTop() { return getList().isEmpty() ? -1 : getList().getSize() - 1; }

public E peek() { return getList().get(indexOfTop()); }

public E pop() { return getList().remove(indexOfTop()); }

public Stack push(E pData) { getList().append(pData); return this; }

private DList getList() { return mList; }

private void setList(DList pList) { mList = pList;

}

Q1

Because Stack encapsulates an instance variable which is of the class DList, storing one or more objects of class E, there is a relationship between Stack and class E. Which type of relationship is it ?

a. Dependency

b. Aggregation

c. Generalization/Inheritance

d. Composition

Q2.

2. See Ex 19 in the second midterm exam, where we used a DList list to store the elements of the Stack data structure. What would be the worst case time complexities of the three standard Stack operations/methods: peek(), push(), and pop(), respectively ?

a. O(1), O(1), O(1)

b. O(1), O(2), O(2)

c. O(1), O(n), O(n)

d. O(lg n), O(lg n), O(lg n)

e. O(n), O(n), O(n)

f. O(n lg n), O(n lg n), O(n lg n)

g. O(lg n), O(n lg n), O(n lg n)

h. We cannot determine this without knowing what the class of E will be when a Stack object is instantiated

Answer 1

Q 1) It is a has-A type of relationship. Stack class has a DList so it is a composition answer is d

Q2) Push pop operations in stack occur from the same side of the list, that is top. So length of the list wouldn't matter even in worst case scenario. Even the peek method is retrieving top most element without removing it. So even that is independent of length of list. Worst case of all three is O(1)

Answer is a