Lecture 20: ADT Case study

Note: this is somewhat contentious, as friends kind of break encapsulation. Can you think of a way to implement this without friend?

Overloading stream operators

• friend function declaration:

  class Time {
  public:
      friend std::ostream &operator<<(std::ostream &out, const Time &t);
  ... etc
  

• The implementation doesn’t use the keyword friend, but it can magically access the private members::

  std::ostream &operator<<(std::ostream &out, const Time &t) {
      out << t.hours << ':' << t.minutes << ':' << t.seconds;
      return out;
  }
  

Operator overloading check-in 1/2

The primary purpose of operator overloading is to:

Operator overloading check-in 2/2

The << operator can’t be overloaded as a member function because:

A common ADT: Stacks

• What makes a class an abstract data type?
  • It has a valid domain (set of values)
  • It has operations that can be performed on it
  • It hides the implementation details
• Our Time class is a (simple) ADT, but it’s pretty boring
• Let’s look at a more interesting one: stacks

Stacks

• Just like it sounds, a stack is a data storage structure that lets you:
  • put stuff on the top of the stack
  • take stuff off the top of the stack
• This is called LIFO (last in, first out)
• In computer science, stacks are used for:
  • the function call stack, aka “the stack”
  • undo operations in most programs
  • bash command history (up arrow)
  • The “back” button in your browser

Specifying the ADT

• We need to specify the domain and operations for our stack ADT
• Domain:
  • a homogenous base type, like int or std::string
  • grows and shrinks dynamically, some reasonable max capacity
• Operations:
  • create an empty stack
  • check if the stack is empty/full (empty/full)
  • add/remove an element to the “top” of the stack (push/pop)
  • Look at the top element without removing (peek)

Sample interface

class StringStack {
public:
    StringStack(int capacity);
    ~StringStack();

    bool empty() const;
    bool full() const;
    void push(const std::string &s);
    std::string pop();
    std::string peek() const;
private:
    ???
};

Sample usage

Let’s implement browser history using our stack ADT:

StringStack history(10); // max 10 pages
history.push("https://www.mymru.ca/");
history.push("https://stackoverflow.com/");
history.push("https://www.funnycatvideos.com/");

// go back to the previous page
load_url(history.pop());

// hover over the back button
if (history.empty())
    show_message("First page, can't go back\n");
else:
    show_message("Click to go back to: " + history.peek());

StringStack implementation V1

• Based on its usage and public interface, how is StringStack implemented?
• Option 1: Arrays

  class StringStack {
  public:
  ...
  private:
      int capacity;
      std::string *stack;
      ???
  }
  

• Problem: remember how arrays need shifting to add to the “head”?
• Solution: who cares which end is the head!

Complete private section for V1

class StringStack {
public:
...
private:
    int capacity;
    std::string *stack; // pointer to the array
    int top; // index of the top element
}

• top is the index of the top element
• What should top be if the stack is empty?

StringStack implementation V2

• Adding/removing elements at the head is easy for linked lists
• Option 2: Linked list

  class StringStack {
  public:
  ...
  private:
      struct Node {
          std::string data;
          Node *next;
      };
      Node *head; // pointer to the head node
      ???
  

• Problem: there’s no inherent capacity for a linked list
• Solution: add a counter to keep track of number of elements

Complete private section for V2

class StringStack {
public:
...
private:
    struct Node {
        std::string data;
        Node *next;
    };
    Node *head; // pointer to the head node
    int capacity;
    int size; // number of elements in the stack
}

• The Node struct is private because it’s an implementation detail

Constructors/destructors

Note: using namespace std; shouldn’t go in the header file, but it’s okay in .cpp

// Array version (V1)
StringStack::StringStack(int capacity) {
    string *stack = new string[capacity];
    this->capacity = capacity;
    top = -1;
}

StringStack::~StringStack() {
    delete[] stack;
}

// Linked list version (V2)
StringStack::StringStack(int capacity) {
    head = NULL;
    this->capacity = capacity;
    size = 0;
}

StringStack::~StringStack() {
    Node *curr = head;
    while (curr) {
        Node *next = curr->next;
        delete curr;
        curr = next;
    }
}

empty, full, and peek

// Array version (V1)
bool StringStack::empty() const {
    return top == -1;
}

bool StringStack::full() const {
    return top == capacity - 1;
}

std::string StringStack::peek() const {
    if (empty())
        return "";
    return stack[top];
}

// Linked list version (V2)
bool StringStack::empty() const {
    return size == 0;
}

bool StringStack::full() const {
    return size == capacity;
}

std::string StringStack::peek() const {
    if (empty())
        return "";
    return head->data;
}

push and pop

// Array version (V1)
void StringStack::push(const std::string &s) {
    if (full())
        return;
    stack[++top] = s;
}

std::string StringStack::pop() {
    if (empty())
        return "";
    return stack[top--];
}

// Linked list version (V2)
void StringStack::push(const std::string &s) {
    if (full())
        return;
    Node *new_node = new Node;
    new_node->data = s;
    new_node->next = head;
    head = new_node;
    size++;
}

std::string StringStack::pop() {
    if (empty())
        return "";
    std::string data = head->data;
    Node *next = head->next;
    delete head;
    head = next;
    size--;
    return data;
}

Summary

• The linked list implementation is more complex, but with one big advantage: no max capacity
• In fact, keeping track of the size adds to the complexity
• The array implementation could dynamically resize whenever you try to push to a full stack, but this is also introducing complexity
• Which one is better? Depends on your use case!

Coming up Next

• Assignment 4 🎉 - refactoring Assignment 3 to use an ADT
• Lab Exercise: Designing an ADT
• Next lecture: Something totally different: recursion!

Textbook Chapter 14