CSC236 Data Structures - Problem Set Answers: Stacks

Problem Set Answers: Stacks

a.   2                                   b.   5
     2                                        x = 1
     3                                        y = 5
     3

c.   3                                   d.   7 6 5 5 1 0
     5
     1
     0
     x = 0
     y = 5
     z = 0

a.   topIndex = 0                       b.   topIndex = 4
     ch = C                                  ch = C
     array = B C D F O                       array = X Y Z A B
     stack before: B C                       stack before: X Y Z A B
     stack after: B                          can't push; stack already full

c.   topIndex = 4                       d.    topIndex = -1
     ch = X                                   ch = C
     array = D J K P X                        array = R V M H A
     stack before: D J K P                    stack before: empty
     stack after: D J K P X                   can't pop; stack already empty

   T item;
   while (!astack.isEmpty()) {
      item = astack.top();
      astack.pop();
      auxstack.push(item);
   }
   while (!auxstack.isEmpty()) {
      item = auxstack.top();
      auxstack.pop();
      System.out.println(item);
      astack.push(item);
   }

   T item;
   int counter = 0;
   while (!astack.isEmpty()) {
      item = astack.top();
      astack.pop();
      auxstack.push(item);
      counter++;
   }
   while (!auxstack.isEmpty()) {
      item = auxstack.top();
      auxstack.pop();
      astack.push(item);
   }

public int size() {
   return topIndex + 1;
}

public int size() {
   int count = 0;
   LLnode<T> temp = top;
   while (temp != null) {
      count++;
      temp = temp.getLink();
   }
   return count;
}

public static void copy(ArrayBoundedStack<T> oldst, ArrayBoundedStack<T> newst) {
   T value;
   ArrayBoundedStack<T> tempst = new ArrayBoundedStack<T>();
   while (!newst.isEmpty())
      value = newst.top();
      newst.pop();
   while (!oldst.isEmpty()) {
      value = oldst.top();
      oldst.pop();
      tempst.push(value);
   }
   while (!tempst.isEmpty()) {
      value = tempst.top();
      tempst.pop();
      newst.push(value);
      oldst.push(value);
   }
}

public ArrayBoundedStack<T> copy() {
   ArrayBoundedStack<T> copy = new ArrayBoundedStack<T>(elements.length);
   copy.topIndex = topIndex;
   int i;
   for (i = 0 ; i <= topIndex ; i++)
      copy.elements[i] = elements[i];
   return copy;
}

public LinkedStack<T> copy() {
   LinkedStack<T> copy = new LinkededStack<T>();
   if (top == null)
      return copy;
   LLNode<T> curr = top;
   copy.top = new LLNode<T>(top.info());
   curr = top.getLink();
   LLNode<T> prev = copy.top;
   LLNode<T> newcurr;
   while (curr != null) {
      newcurr = new LLNode<T>(curr.getInfo()));
      prev.setLink(newcurr);
      curr = curr.getLink();
      prev = newcurr;
   }
   return copy;
}

public static int sumneg(ArrayBoundedStack<Integer> st) {
   int value;
   int sum = 0;
   ArrayBoundedStack<Integer> tempst = new ArrayBoundedStack<Integer>();
   while (!st.isEmpty()) {
      value = st.top();
      st.pop();
      tempst.push(value);
      if (value < 0)
         sum = sum + value;
   }
   while (!tempst.isEmpty()) {
      value = tempst.top();
      tempst.pop();
      st.push(value);
   }
   return sum;
}

public static void deletea(ArrayBoundedStack<Character> st) {
   ArrayBoundedStack<Character> tempst = new ArrayBoundedStack<Character>();
   char chval;
   while (!st.isEmpty()) {
      chval = st.top();
      st.pop();
      if (chval != 'A')
         tempst.push(chval);
   }
   while (!tempst.isEmpty()) {
      chval = tempst.top();
      tempst.pop();
      st.push(chval);
   }
}

public static void replaces(ArrayBoundedStack<Character> st, char oldch, char newch) {
   ArrayBoundedStack<Character> tempst = new ArrayBoundedStack<Character>();
   char ch;
   while (!st.isEmpty()) {
      ch = st.top();
      st.pop();
      tempst.push(ch);
   }
   while (!tempst.isEmpty()) {
      ch = tempst.top();
      tempst.pop();
      if (ch == oldch)
         ch = newch;
      st.push(ch);
   }
}

public void replace(T told, T tnew) {
   int i;
   for (i = 0 ; i <= topIndex ; i++) {
      if (elements[i].equals(told))
         elements[i] = tnew;
   }
}

public void replace(T told, T tnew) {
   LLNode curr = top;
   while (curr != null) {
      if (curr.getInfo().equals(told))
         curr.setInfo(tnew);
   }
}

public void displayBack() {
   int i;
   for (i = 0 ; i <= topIndex ; i++)
      System.out.println(elements[i]);
   }
}