Recitation 09: Stacks and Queues

• Handout [Annotated]
• Drawings

Interfaces

Although we will be discussing data structures in both in abstract terms as well as the actual implementation, adherence to the interface is extremely important. When using these data structures, your code should not rely on any of the internal workings. There are some significant motivations for writing code like this. One is that when you are simply using a data structure in your program, you just want to be able to use it--you don't want it to be necessary to understand every aspect of the implementation. Another is that the implementation can be changed (improved) and as long as the interface is unchanged, your code will not break.

Structs

So far, we've only dealt with primitive types (int, bool, ...) and arrays. We can also create our own types, known as structs. Structs are a way of packaging multiple values together under one variable name. This is probably best illustrated with an example. Suppose we want to store some information about a person. We could create a struct such as:
struct person_data {
  string name;
  int height; // in kg.
  int weight; // in m.
};
typedef struct person_data person;
The syntax for this looks pretty similar to what we've seen so far. We name the struct and put all of the fields in between braces. Each field is declared as a type with a name. Note that the ending brace has a semi-colon afterwards. Also, I can't assign default values to fields, e.x. int height = 0; would not be valid. We've seen the typedef notation before too. In this case, we simply use it for convenience, giving us more succinct type names.

Now, suppose I want to work with a struct like this. Here is an example:

  person *p = alloc(person);
  p->name = "Bob";
  p->height = 68;
  p->weight = 200;
  println(p->name);

First, we have to allocate memory for the struct. We use this struct->field notation to access the various elements of the struct. This is the same for when we assign values as when we access values. The -> performs two jobs: it navigates to the correct data within the struct and dereferences the pointer.

Now, we can work with a struct just like any other datatype. Suppose we wanted to write a function that computes a person's BMI. The function might look like this:

  int bmi (person p) {
    int square_height = p->height * p->height;
    return p->weight / square_height;
  }

It is also often convenient to create a helper function to initialize the new struct in the first place. For example:

  person *person_new (string name, int height, int weight) {
    person *p = alloc(person);
    p->name = name;
    p->height = height;
    p->weight = weight;
    return p;
  }

If you have any comments or see any errors, please let me know.