1 2 + 4 * 5 + 3 −

stack: 14

plan for today:
*1) show how to use a stack to evaluate a RPN expression

*2) go over three ways of reversing a singly linked list

*3) discussion of final
// fix TreeNode class so that there is one less in each array
int print_in_order(TreeNode current)
{
if (current == NULL) return 0;
int i;
int sum = 0;
for (i = 0; i < current.num_elements; i++)
{
sum += print_in_order(current.links[i];
// System.out.println(current.key_values[i] + " ");
}
sum += print_in_order(current.links[i];
return current.num_elements +sum ;
}




4) skip list

5) DFS

2)
void iterative_reverse()
{
 Node p, q, r;

 if(head == NULL)
  return;

 p = head;
 q = p.next;

 p.next = NULL;

 while (q != NULL)
 {
  r = q.next;
  q.next = p;
  p = q;
  q = r;
 }

 head = p;
}


void iterative_reverse_2()
{
 Stack s = new Stack();
 Node cur, prev;
 for (cur = head; cur != NULL; cur=cur.next)
 {
  s.push(cur);
 }
 head = s.pop();
 cur = head;
 while (! s.empty())
 {
  prev = cur;
  cur = s.pop();
  prev.next = cur;
 }
 cur.next = NULL;
 tail = cur;
}

public void reverse()
{
 reverse2(NULL, head);
 Node temp = head;
 head = tail;
 tail = temp;
}

private void reverse2(Node prev, Node current)
{
 if (current == NULL) return;
 reverse2(current, current.next);
 current.next = prev;

}