Summer 2003: Algorithm Library Design

Homework 6: Friday, 20.06.03

Project update due Tuesday, 08.07.03
Submit to the supervisor of your project.

Exercise 6 (10 Pts)

The following simple stack class template is not exception safe.

// a stack implemented as a singly-linked list
template <class T>
class Stack {

  // list node
  struct Node {
    T data;
    Node* next;
  };

  // recursive list copy
  Node* copy(Node* orig) {
    Node* cp = 0;
    if (orig) {
      cp = new Node(*orig);
      cp->next = copy(orig->next);
    }
    return cp;
  }

  // head of the list
  Node* head;

public:

  Stack() : head(0) {}
  Stack(const Stack& other) : head(copy(other.head)) {}
  ~Stack() { while (!empty()) pop(); }

  Stack& operator=(const Stack& rhs) {
    while (!empty()) pop();
    head = copy(rhs.head);
    return *this;
  }

  bool empty() const { return head == 0; }

  void push(const T& t) {
    Node* newnode = new Node;
    newnode->next = head;
    head = newnode;
    head->data = t;
  }

  T pop() {
    if (empty()) throw "pop() in empty stack";
    Node* tmp = head;
    head = head->next;
    T value = tmp->data;
    delete tmp;
    return value;
  }
};

(b) Make Stack as exception-safe as you can. Do not change the data structure, singly-linked list, into something else such as an array. Do not use any standard containers. auto_ptrs may be used internally but not as a part of the public interface. (Using auto_ptrs is not necessary here, however.)

Hint: Separate responsibilities: Move memory management into a separate class.

Project update

Provide a first working implementation of your project. Write a report on what new considerations this has brought to your attention concerning the design (if any).