Stacks and Queues

1. What will be printed when the following code executes?

   Stack<String> stack = new AStack<>();
   Queue<String> queue = new AQueue<>();
   
   stack.push("A");
   stack.push("B");
   stack.push("C");
   stack.pop();
   stack.push("D");
   
   while (!stack.isEmpty()) {
     queue.enqueue(stack.pop());
   }
   
   while (!queue.isEmpty()) {
     System.out.print(queue.dequeue());
   }

          

2. Our texbook’s LQueue class maintains both a front and rear reference. Which of these corresponds to the head of the list? Which of these corresponds to the tail of the list? (The answer is not arbitrary. Only one of the two alternatives can be implemented efficiently.)

          

3. Consider the following partial implementation of a circular-array-based queue:

AQueue(int capacity) {
  front = 0;
  size = 0;
  queueArray = (E[]) new Object[capacity];
}

// Put "it" in queue
public boolean enqueue(E it) {
  if (length() == queueArray.length) {
    resize();
  }
  int rear = (front + size) % queueArray.length;
  queueArray[rear] = it;
  size++;

  return true;
}

// Remove and return front value
public E dequeue() {
  if (length() == 0) {
    throw new NoSuchElementException();
  }
  E it = queueArray[front];
  queueArray[front] = null;
  front = (front + 1) % queueArray.length;
  size--;
  return it;
}

AQueue queue = new AQueue<String>(4);
queue.enqueue("A");
queue.enqueue("B");
queue.enqueue("C"); 
// HERE



queue.dequeue();
// HERE



queue.enqueue("D");
queue.enqueue("E");
// HERE

Analyzing List Algorithms

Analyze each of the methods below according to the instructions in the Javadoc comments. In each case you will be comparing the performance of java.util.ArrayList with java.util.LinkedList. Recall that java.util.LinkedList is implemented using a doubly-linked list that maintains both a head and tail reference.

1. /*
    * What is the big-Theta running time of this method, assuming that list is
    * 
    * 
    * an ArrayList:
    * 
    * 
    * a LinkedList:
    * 
    * 
    */
   public static int sumByIndex(List<Integer> list) {
   
       int sum = 0;
       for (int i = 0; i < list.size(); i++) {
           sum += list.get(i);
       }
       return sum;
   }

2. 
   /*
    * What is the big-Theta running time of this method, assuming that list is
    * 
    * 
    * an ArrayList:
    * 
    * 
    * a LinkedList:
    * 
    * 
    */
   public static int sumWithIterator(List<Integer> list) {
   
       int sum = 0;
       for (int curValue : list) {
           sum += curValue;
       }
       return sum;
   
   }

3. 
   /*
    * What is the big-Theta running time of this method, assuming that toList
    * is initially empty, and that both lists are of type
    * 
    * 
    * ArrayList:
    * 
    * 
    * LinkedList:
    * 
    * 
    */
   public static void copy(List<Integer> fromList,
                           List<Integer> toList) {
   
       for (int item : fromList) {
           toList.add(item);
       }
   
   }

   
   

4. /*
    * What is the big-Theta running time of this method, assuming that toList
    * is initially empty, and that both lists are of type
    * 
    * 
    * ArrayList:
    * 
    * 
    * LinkedList:
    * 
    * 
    */
   public static void copyReverseA(List<Integer> fromList, 
                                   List<Integer> toList) {
   
       for (int item : fromList) {
           toList.add(0, item);
       }
   
   }

5. /*
    * What is the big-Theta running time of this method, assuming that toList
    * is initially empty, and that both lists are of type
    * 
    * 
    * ArrayList:
    * 
    * 
    * LinkedList:
    * 
    * 
    */
   public static void copyReverseB(List<Integer> fromList, 
                                   List<Integer> toList) {
       int value;
       for (int i = fromList.size() - 1; i >= 0; i--) {
           value = fromList.get(i);
           toList.add(value);
       }
   
   }